Debian Codegraph @

closure-library/closure/goog/math/matrix.js

raw
1 // Copyright 2007 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview Class for representing matrices and static helper functions.
17 */
18
19 goog.provide('goog.math.Matrix');
20
21 goog.require('goog.array');
22 goog.require('goog.asserts');
23 goog.require('goog.math');
24 goog.require('goog.math.Size');
25 goog.require('goog.string');
26
27
28
29 /**
30 * Class for representing and manipulating matrices.
31 *
32 * The entry that lies in the i-th row and the j-th column of a matrix is
33 * typically referred to as the i,j entry of the matrix.
34 *
35 * The m-by-n matrix A would have its entries referred to as:
36 * [ a0,0 a0,1 a0,2 ... a0,j ... a0,n ]
37 * [ a1,0 a1,1 a1,2 ... a1,j ... a1,n ]
38 * [ a2,0 a2,1 a2,2 ... a2,j ... a2,n ]
39 * [ . . . . . ]
40 * [ . . . . . ]
41 * [ . . . . . ]
42 * [ ai,0 ai,1 ai,2 ... ai,j ... ai,n ]
43 * [ . . . . . ]
44 * [ . . . . . ]
45 * [ . . . . . ]
46 * [ am,0 am,1 am,2 ... am,j ... am,n ]
47 *
48 * @param {!goog.math.Matrix|!Array<!Array<number>>|!goog.math.Size|number} m
49 * A matrix to copy, a 2D-array to take as a template, a size object for
50 * dimensions, or the number of rows.
51 * @param {number=} opt_n Number of columns of the matrix (only applicable if
52 * the first argument is also numeric).
53 * @struct
54 * @constructor
55 * @final
56 */
57 goog.math.Matrix = function(m, opt_n) {
58 if (m instanceof goog.math.Matrix) {
59 this.array_ = m.toArray();
60 } else if (
61 goog.isArrayLike(m) &&
62 goog.math.Matrix.isValidArray(
63 /** @type {!Array<!Array<number>>} */ (m))) {
64 this.array_ = goog.array.clone(/** @type {!Array<!Array<number>>} */ (m));
65 } else if (m instanceof goog.math.Size) {
66 this.array_ = goog.math.Matrix.createZeroPaddedArray_(m.height, m.width);
67 } else if (goog.isNumber(m) && goog.isNumber(opt_n) && m > 0 && opt_n > 0) {
68 this.array_ = goog.math.Matrix.createZeroPaddedArray_(
69 /** @type {number} */ (m), opt_n);
70 } else {
71 throw new Error('Invalid argument(s) for Matrix contructor');
72 }
73
74 this.size_ = new goog.math.Size(this.array_[0].length, this.array_.length);
75 };
76
77
78 /**
79 * Creates a square identity matrix. i.e. for n = 3:
80 * <pre>
81 * [ 1 0 0 ]
82 * [ 0 1 0 ]
83 * [ 0 0 1 ]
84 * </pre>
85 * @param {number} n The size of the square identity matrix.
86 * @return {!goog.math.Matrix} Identity matrix of width and height {@code n}.
87 */
88 goog.math.Matrix.createIdentityMatrix = function(n) {
89 var rv = [];
90 for (var i = 0; i < n; i++) {
91 rv[i] = [];
92 for (var j = 0; j < n; j++) {
93 rv[i][j] = i == j ? 1 : 0;
94 }
95 }
96 return new goog.math.Matrix(rv);
97 };
98
99
100 /**
101 * Calls a function for each cell in a matrix.
102 * @param {goog.math.Matrix} matrix The matrix to iterate over.
103 * @param {function(this:T, number, number, number, !goog.math.Matrix)} fn
104 * The function to call for every element. This function
105 * takes 4 arguments (value, i, j, and the matrix)
106 * and the return value is irrelevant.
107 * @param {T=} opt_obj The object to be used as the value of 'this'
108 * within {@code fn}.
109 * @template T
110 */
111 goog.math.Matrix.forEach = function(matrix, fn, opt_obj) {
112 for (var i = 0; i < matrix.getSize().height; i++) {
113 for (var j = 0; j < matrix.getSize().width; j++) {
114 fn.call(opt_obj, matrix.array_[i][j], i, j, matrix);
115 }
116 }
117 };
118
119
120 /**
121 * Tests whether an array is a valid matrix. A valid array is an array of
122 * arrays where all arrays are of the same length and all elements are numbers.
123 * @param {!Array<!Array<number>>} arr An array to test.
124 * @return {boolean} Whether the array is a valid matrix.
125 */
126 goog.math.Matrix.isValidArray = function(arr) {
127 var len = 0;
128 for (var i = 0; i < arr.length; i++) {
129 if (!goog.isArrayLike(arr[i]) || len > 0 && arr[i].length != len) {
130 return false;
131 }
132 for (var j = 0; j < arr[i].length; j++) {
133 if (!goog.isNumber(arr[i][j])) {
134 return false;
135 }
136 }
137 if (len == 0) {
138 len = arr[i].length;
139 }
140 }
141 return len != 0;
142 };
143
144
145 /**
146 * Calls a function for every cell in a matrix and inserts the result into a
147 * new matrix of equal dimensions.
148 * @param {!goog.math.Matrix} matrix The matrix to iterate over.
149 * @param {function(this:T, number, number, number, !goog.math.Matrix): number}
150 * fn The function to call for every element. This function
151 * takes 4 arguments (value, i, j and the matrix)
152 * and should return a number, which will be inserted into a new matrix.
153 * @param {T=} opt_obj The object to be used as the value of 'this'
154 * within {@code fn}.
155 * @return {!goog.math.Matrix} A new matrix with the results from {@code fn}.
156 * @template T
157 */
158 goog.math.Matrix.map = function(matrix, fn, opt_obj) {
159 var m = new goog.math.Matrix(matrix.getSize());
160 goog.math.Matrix.forEach(matrix, function(value, i, j) {
161 m.array_[i][j] = fn.call(opt_obj, value, i, j, matrix);
162 });
163 return m;
164 };
165
166
167 /**
168 * Creates a new zero padded matix.
169 * @param {number} m Height of matrix.
170 * @param {number} n Width of matrix.
171 * @return {!Array<!Array<number>>} The new zero padded matrix.
172 * @private
173 */
174 goog.math.Matrix.createZeroPaddedArray_ = function(m, n) {
175 var rv = [];
176 for (var i = 0; i < m; i++) {
177 rv[i] = [];
178 for (var j = 0; j < n; j++) {
179 rv[i][j] = 0;
180 }
181 }
182 return rv;
183 };
184
185
186 /**
187 * Internal array representing the matrix.
188 * @type {!Array<!Array<number>>}
189 * @private
190 */
191 goog.math.Matrix.prototype.array_;
192
193
194 /**
195 * After construction the Matrix's size is constant and stored in this object.
196 * @type {!goog.math.Size}
197 * @private
198 */
199 goog.math.Matrix.prototype.size_;
200
201
202 /**
203 * Returns a new matrix that is the sum of this and the provided matrix.
204 * @param {goog.math.Matrix} m The matrix to add to this one.
205 * @return {!goog.math.Matrix} Resultant sum.
206 */
207 goog.math.Matrix.prototype.add = function(m) {
208 if (!goog.math.Size.equals(this.size_, m.getSize())) {
209 throw new Error(
210 'Matrix summation is only supported on arrays of equal size');
211 }
212 return goog.math.Matrix.map(
213 this, function(val, i, j) { return val + m.array_[i][j]; });
214 };
215
216
217 /**
218 * Appends the given matrix to the right side of this matrix.
219 * @param {goog.math.Matrix} m The matrix to augment this matrix with.
220 * @return {!goog.math.Matrix} A new matrix with additional columns on the
221 * right.
222 */
223 goog.math.Matrix.prototype.appendColumns = function(m) {
224 if (this.size_.height != m.getSize().height) {
225 throw new Error(
226 'The given matrix has height ' + m.size_.height + ', but ' +
227 ' needs to have height ' + this.size_.height + '.');
228 }
229 var result =
230 new goog.math.Matrix(this.size_.height, this.size_.width + m.size_.width);
231 goog.math.Matrix.forEach(
232 this, function(value, i, j) { result.array_[i][j] = value; });
233 goog.math.Matrix.forEach(m, function(value, i, j) {
234 result.array_[i][this.size_.width + j] = value;
235 }, this);
236 return result;
237 };
238
239
240 /**
241 * Appends the given matrix to the bottom of this matrix.
242 * @param {goog.math.Matrix} m The matrix to augment this matrix with.
243 * @return {!goog.math.Matrix} A new matrix with added columns on the bottom.
244 */
245 goog.math.Matrix.prototype.appendRows = function(m) {
246 if (this.size_.width != m.getSize().width) {
247 throw new Error(
248 'The given matrix has width ' + m.size_.width + ', but ' +
249 ' needs to have width ' + this.size_.width + '.');
250 }
251 var result = new goog.math.Matrix(
252 this.size_.height + m.size_.height, this.size_.width);
253 goog.math.Matrix.forEach(
254 this, function(value, i, j) { result.array_[i][j] = value; });
255 goog.math.Matrix.forEach(m, function(value, i, j) {
256 result.array_[this.size_.height + i][j] = value;
257 }, this);
258 return result;
259 };
260
261
262 /**
263 * Returns whether the given matrix equals this matrix.
264 * @param {goog.math.Matrix} m The matrix to compare to this one.
265 * @param {number=} opt_tolerance The tolerance when comparing array entries.
266 * @return {boolean} Whether the given matrix equals this matrix.
267 */
268 goog.math.Matrix.prototype.equals = function(m, opt_tolerance) {
269 if (this.size_.width != m.size_.width) {
270 return false;
271 }
272 if (this.size_.height != m.size_.height) {
273 return false;
274 }
275
276 var tolerance = opt_tolerance || 0;
277 for (var i = 0; i < this.size_.height; i++) {
278 for (var j = 0; j < this.size_.width; j++) {
279 if (!goog.math.nearlyEquals(
280 this.array_[i][j], m.array_[i][j], tolerance)) {
281 return false;
282 }
283 }
284 }
285
286 return true;
287 };
288
289
290 /**
291 * Returns the determinant of this matrix. The determinant of a matrix A is
292 * often denoted as |A| and can only be applied to a square matrix.
293 * @return {number} The determinant of this matrix.
294 */
295 goog.math.Matrix.prototype.getDeterminant = function() {
296 if (!this.isSquare()) {
297 throw new Error('A determinant can only be take on a square matrix');
298 }
299
300 return this.getDeterminant_();
301 };
302
303
304 /**
305 * Returns the inverse of this matrix if it exists or null if the matrix is
306 * not invertible.
307 * @return {goog.math.Matrix} A new matrix which is the inverse of this matrix.
308 */
309 goog.math.Matrix.prototype.getInverse = function() {
310 if (!this.isSquare()) {
311 throw new Error('An inverse can only be taken on a square matrix.');
312 }
313 if (this.getSize().width == 1) {
314 var a = this.getValueAt(0, 0);
315 return a == 0 ? null : new goog.math.Matrix([[1 / Number(a)]]);
316 }
317 var identity = goog.math.Matrix.createIdentityMatrix(this.size_.height);
318 var mi = this.appendColumns(identity).getReducedRowEchelonForm();
319 var i = mi.getSubmatrixByCoordinates_(
320 0, 0, identity.size_.width - 1, identity.size_.height - 1);
321 if (!i.equals(identity)) {
322 return null; // This matrix was not invertible
323 }
324 return mi.getSubmatrixByCoordinates_(0, identity.size_.width);
325 };
326
327
328 /**
329 * Transforms this matrix into reduced row echelon form.
330 * @return {!goog.math.Matrix} A new matrix reduced row echelon form.
331 */
332 goog.math.Matrix.prototype.getReducedRowEchelonForm = function() {
333 var result = new goog.math.Matrix(this);
334 var col = 0;
335 // Each iteration puts one row in reduced row echelon form
336 for (var row = 0; row < result.size_.height; row++) {
337 if (col >= result.size_.width) {
338 return result;
339 }
340
341 // Scan each column starting from this row on down for a non-zero value
342 var i = row;
343 while (result.array_[i][col] == 0) {
344 i++;
345 if (i == result.size_.height) {
346 i = row;
347 col++;
348 if (col == result.size_.width) {
349 return result;
350 }
351 }
352 }
353
354 // Make the row we found the current row with a leading 1
355 this.swapRows_(i, row);
356 var divisor = result.array_[row][col];
357 for (var j = col; j < result.size_.width; j++) {
358 result.array_[row][j] = result.array_[row][j] / divisor;
359 }
360
361 // Subtract a multiple of this row from each other row
362 // so that all the other entries in this column are 0
363 for (i = 0; i < result.size_.height; i++) {
364 if (i != row) {
365 var multiple = result.array_[i][col];
366 for (var j = col; j < result.size_.width; j++) {
367 result.array_[i][j] -= multiple * result.array_[row][j];
368 }
369 }
370 }
371
372 // Move on to the next column
373 col++;
374 }
375 return result;
376 };
377
378
379 /**
380 * @return {!goog.math.Size} The dimensions of the matrix.
381 */
382 goog.math.Matrix.prototype.getSize = function() {
383 return this.size_;
384 };
385
386
387 /**
388 * Return the transpose of this matrix. For an m-by-n matrix, the transpose
389 * is the n-by-m matrix which results from turning rows into columns and columns
390 * into rows
391 * @return {!goog.math.Matrix} A new matrix A^T.
392 */
393 goog.math.Matrix.prototype.getTranspose = function() {
394 var m = new goog.math.Matrix(this.size_.width, this.size_.height);
395 goog.math.Matrix.forEach(
396 this, function(value, i, j) { m.array_[j][i] = value; });
397 return m;
398 };
399
400
401 /**
402 * Retrieves the value of a particular coordinate in the matrix or null if the
403 * requested coordinates are out of range.
404 * @param {number} i The i index of the coordinate.
405 * @param {number} j The j index of the coordinate.
406 * @return {?number} The value at the specified coordinate.
407 */
408 goog.math.Matrix.prototype.getValueAt = function(i, j) {
409 if (!this.isInBounds_(i, j)) {
410 return null;
411 }
412 return this.array_[i][j];
413 };
414
415
416 /**
417 * @return {boolean} Whether the horizontal and vertical dimensions of this
418 * matrix are the same.
419 */
420 goog.math.Matrix.prototype.isSquare = function() {
421 return this.size_.width == this.size_.height;
422 };
423
424
425 /**
426 * Sets the value at a particular coordinate (if the coordinate is within the
427 * bounds of the matrix).
428 * @param {number} i The i index of the coordinate.
429 * @param {number} j The j index of the coordinate.
430 * @param {number} value The new value for the coordinate.
431 */
432 goog.math.Matrix.prototype.setValueAt = function(i, j, value) {
433 if (!this.isInBounds_(i, j)) {
434 throw new Error(
435 'Index out of bounds when setting matrix value, (' + i + ',' + j +
436 ') in size (' + this.size_.height + ',' + this.size_.width + ')');
437 }
438 this.array_[i][j] = value;
439 };
440
441
442 /**
443 * Performs matrix or scalar multiplication on a matrix and returns the
444 * resultant matrix.
445 *
446 * Matrix multiplication is defined between two matrices only if the number of
447 * columns of the first matrix is the same as the number of rows of the second
448 * matrix. If A is an m-by-n matrix and B is an n-by-p matrix, then their
449 * product AB is an m-by-p matrix
450 *
451 * Scalar multiplication returns a matrix of the same size as the original,
452 * each value multiplied by the given value.
453 *
454 * @param {goog.math.Matrix|number} m Matrix/number to multiply the matrix by.
455 * @return {!goog.math.Matrix} Resultant product.
456 */
457 goog.math.Matrix.prototype.multiply = function(m) {
458 if (m instanceof goog.math.Matrix) {
459 if (this.size_.width != m.getSize().height) {
460 throw new Error(
461 'Invalid matrices for multiplication. Second matrix ' +
462 'should have the same number of rows as the first has columns.');
463 }
464 return this.matrixMultiply_(/** @type {!goog.math.Matrix} */ (m));
465 } else if (goog.isNumber(m)) {
466 return this.scalarMultiply_(/** @type {number} */ (m));
467 } else {
468 throw new Error(
469 'A matrix can only be multiplied by' +
470 ' a number or another matrix.');
471 }
472 };
473
474
475 /**
476 * Returns a new matrix that is the difference of this and the provided matrix.
477 * @param {goog.math.Matrix} m The matrix to subtract from this one.
478 * @return {!goog.math.Matrix} Resultant difference.
479 */
480 goog.math.Matrix.prototype.subtract = function(m) {
481 if (!goog.math.Size.equals(this.size_, m.getSize())) {
482 throw new Error(
483 'Matrix subtraction is only supported on arrays of equal size.');
484 }
485 return goog.math.Matrix.map(
486 this, function(val, i, j) { return val - m.array_[i][j]; });
487 };
488
489
490 /**
491 * @return {!Array<!Array<number>>} A 2D internal array representing this
492 * matrix. Not a clone.
493 */
494 goog.math.Matrix.prototype.toArray = function() {
495 return this.array_;
496 };
497
498
499 if (goog.DEBUG) {
500 /**
501 * Returns a string representation of the matrix. e.g.
502 * <pre>
503 * [ 12 5 9 1 ]
504 * [ 4 16 0 17 ]
505 * [ 12 5 1 23 ]
506 * </pre>
507 *
508 * @return {string} A string representation of this matrix.
509 * @override
510 */
511 goog.math.Matrix.prototype.toString = function() {
512 // Calculate correct padding for optimum display of matrix
513 var maxLen = 0;
514 goog.math.Matrix.forEach(this, function(val) {
515 var len = String(val).length;
516 if (len > maxLen) {
517 maxLen = len;
518 }
519 });
520
521 // Build the string
522 var sb = [];
523 goog.array.forEach(this.array_, function(row, x) {
524 sb.push('[ ');
525 goog.array.forEach(row, function(val, y) {
526 var strval = String(val);
527 sb.push(goog.string.repeat(' ', maxLen - strval.length) + strval + ' ');
528 });
529 sb.push(']\n');
530 });
531
532 return sb.join('');
533 };
534 }
535
536
537 /**
538 * Returns the signed minor.
539 * @param {number} i The row index.
540 * @param {number} j The column index.
541 * @return {number} The cofactor C[i,j] of this matrix.
542 * @private
543 */
544 goog.math.Matrix.prototype.getCofactor_ = function(i, j) {
545 return (i + j % 2 == 0 ? 1 : -1) * this.getMinor_(i, j);
546 };
547
548
549 /**
550 * Returns the determinant of this matrix. The determinant of a matrix A is
551 * often denoted as |A| and can only be applied to a square matrix. Same as
552 * public method but without validation. Implemented using Laplace's formula.
553 * @return {number} The determinant of this matrix.
554 * @private
555 */
556 goog.math.Matrix.prototype.getDeterminant_ = function() {
557 if (this.getSize().area() == 1) {
558 return this.array_[0][0];
559 }
560
561 // We might want to use matrix decomposition to improve running time
562 // For now we'll do a Laplace expansion along the first row
563 var determinant = 0;
564 for (var j = 0; j < this.size_.width; j++) {
565 determinant += (this.array_[0][j] * this.getCofactor_(0, j));
566 }
567 return determinant;
568 };
569
570
571 /**
572 * Returns the determinant of the submatrix resulting from the deletion of row i
573 * and column j.
574 * @param {number} i The row to delete.
575 * @param {number} j The column to delete.
576 * @return {number} The first minor M[i,j] of this matrix.
577 * @private
578 */
579 goog.math.Matrix.prototype.getMinor_ = function(i, j) {
580 return this.getSubmatrixByDeletion_(i, j).getDeterminant_();
581 };
582
583
584 /**
585 * Returns a submatrix contained within this matrix.
586 * @param {number} i1 The upper row index.
587 * @param {number} j1 The left column index.
588 * @param {number=} opt_i2 The lower row index.
589 * @param {number=} opt_j2 The right column index.
590 * @return {!goog.math.Matrix} The submatrix contained within the given bounds.
591 * @private
592 */
593 goog.math.Matrix.prototype.getSubmatrixByCoordinates_ = function(
594 i1, j1, opt_i2, opt_j2) {
595 var i2 = opt_i2 ? opt_i2 : this.size_.height - 1;
596 var j2 = opt_j2 ? opt_j2 : this.size_.width - 1;
597 var result = new goog.math.Matrix(i2 - i1 + 1, j2 - j1 + 1);
598 goog.math.Matrix.forEach(result, function(value, i, j) {
599 result.array_[i][j] = this.array_[i1 + i][j1 + j];
600 }, this);
601 return result;
602 };
603
604
605 /**
606 * Returns a new matrix equal to this one, but with row i and column j deleted.
607 * @param {number} i The row index of the coordinate.
608 * @param {number} j The column index of the coordinate.
609 * @return {!goog.math.Matrix} The value at the specified coordinate.
610 * @private
611 */
612 goog.math.Matrix.prototype.getSubmatrixByDeletion_ = function(i, j) {
613 var m = new goog.math.Matrix(this.size_.width - 1, this.size_.height - 1);
614 goog.math.Matrix.forEach(m, function(value, x, y) {
615 m.setValueAt(x, y, this.array_[x >= i ? x + 1 : x][y >= j ? y + 1 : y]);
616 }, this);
617 return m;
618 };
619
620
621 /**
622 * Returns whether the given coordinates are contained within the bounds of the
623 * matrix.
624 * @param {number} i The i index of the coordinate.
625 * @param {number} j The j index of the coordinate.
626 * @return {boolean} The value at the specified coordinate.
627 * @private
628 */
629 goog.math.Matrix.prototype.isInBounds_ = function(i, j) {
630 return i >= 0 && i < this.size_.height && j >= 0 && j < this.size_.width;
631 };
632
633
634 /**
635 * Matrix multiplication is defined between two matrices only if the number of
636 * columns of the first matrix is the same as the number of rows of the second
637 * matrix. If A is an m-by-n matrix and B is an n-by-p matrix, then their
638 * product AB is an m-by-p matrix
639 *
640 * @param {goog.math.Matrix} m Matrix to multiply the matrix by.
641 * @return {!goog.math.Matrix} Resultant product.
642 * @private
643 */
644 goog.math.Matrix.prototype.matrixMultiply_ = function(m) {
645 var resultMatrix = new goog.math.Matrix(this.size_.height, m.getSize().width);
646 goog.math.Matrix.forEach(resultMatrix, function(val, x, y) {
647 var newVal = 0;
648 for (var i = 0; i < this.size_.width; i++) {
649 newVal += goog.asserts.assertNumber(this.getValueAt(x, i)) *
650 goog.asserts.assertNumber(m.getValueAt(i, y));
651 }
652 resultMatrix.setValueAt(x, y, newVal);
653 }, this);
654 return resultMatrix;
655 };
656
657
658 /**
659 * Scalar multiplication returns a matrix of the same size as the original,
660 * each value multiplied by the given value.
661 *
662 * @param {number} m number to multiply the matrix by.
663 * @return {!goog.math.Matrix} Resultant product.
664 * @private
665 */
666 goog.math.Matrix.prototype.scalarMultiply_ = function(m) {
667 return goog.math.Matrix.map(this, function(val, x, y) { return val * m; });
668 };
669
670
671 /**
672 * Swaps two rows.
673 * @param {number} i1 The index of the first row to swap.
674 * @param {number} i2 The index of the second row to swap.
675 * @private
676 */
677 goog.math.Matrix.prototype.swapRows_ = function(i1, i2) {
678 var tmp = this.array_[i1];
679 this.array_[i1] = this.array_[i2];
680 this.array_[i2] = tmp;
681 };