| // Copyright 2007 The Closure Library Authors. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS-IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| /** |
| * @fileoverview Class for representing matrices and static helper functions. |
| */ |
| |
| goog.provide('goog.math.Matrix'); |
| |
| goog.require('goog.array'); |
| goog.require('goog.math'); |
| goog.require('goog.math.Size'); |
| goog.require('goog.string'); |
| |
| |
| |
| /** |
| * Class for representing and manipulating matrices. |
| * |
| * The entry that lies in the i-th row and the j-th column of a matrix is |
| * typically referred to as the i,j entry of the matrix. |
| * |
| * The m-by-n matrix A would have its entries referred to as: |
| * [ a0,0 a0,1 a0,2 ... a0,j ... a0,n ] |
| * [ a1,0 a1,1 a1,2 ... a1,j ... a1,n ] |
| * [ a2,0 a2,1 a2,2 ... a2,j ... a2,n ] |
| * [ . . . . . ] |
| * [ . . . . . ] |
| * [ . . . . . ] |
| * [ ai,0 ai,1 ai,2 ... ai,j ... ai,n ] |
| * [ . . . . . ] |
| * [ . . . . . ] |
| * [ . . . . . ] |
| * [ am,0 am,1 am,2 ... am,j ... am,n ] |
| * |
| * @param {!goog.math.Matrix|!Array<!Array<number>>|!goog.math.Size|number} m |
| * A matrix to copy, a 2D-array to take as a template, a size object for |
| * dimensions, or the number of rows. |
| * @param {number=} opt_n Number of columns of the matrix (only applicable if |
| * the first argument is also numeric). |
| * @struct |
| * @constructor |
| * @final |
| */ |
| goog.math.Matrix = function(m, opt_n) { |
| if (m instanceof goog.math.Matrix) { |
| this.array_ = m.toArray(); |
| } else if (goog.isArrayLike(m) && |
| goog.math.Matrix.isValidArray( |
| /** @type {!Array<!Array<number>>} */ (m))) { |
| this.array_ = goog.array.clone(/** @type {!Array<!Array<number>>} */ (m)); |
| } else if (m instanceof goog.math.Size) { |
| this.array_ = goog.math.Matrix.createZeroPaddedArray_(m.height, m.width); |
| } else if (goog.isNumber(m) && goog.isNumber(opt_n) && m > 0 && opt_n > 0) { |
| this.array_ = goog.math.Matrix.createZeroPaddedArray_( |
| /** @type {number} */ (m), opt_n); |
| } else { |
| throw Error('Invalid argument(s) for Matrix contructor'); |
| } |
| |
| this.size_ = new goog.math.Size(this.array_[0].length, this.array_.length); |
| }; |
| |
| |
| /** |
| * Creates a square identity matrix. i.e. for n = 3: |
| * <pre> |
| * [ 1 0 0 ] |
| * [ 0 1 0 ] |
| * [ 0 0 1 ] |
| * </pre> |
| * @param {number} n The size of the square identity matrix. |
| * @return {!goog.math.Matrix} Identity matrix of width and height {@code n}. |
| */ |
| goog.math.Matrix.createIdentityMatrix = function(n) { |
| var rv = []; |
| for (var i = 0; i < n; i++) { |
| rv[i] = []; |
| for (var j = 0; j < n; j++) { |
| rv[i][j] = i == j ? 1 : 0; |
| } |
| } |
| return new goog.math.Matrix(rv); |
| }; |
| |
| |
| /** |
| * Calls a function for each cell in a matrix. |
| * @param {goog.math.Matrix} matrix The matrix to iterate over. |
| * @param {function(this:T, number, number, number, !goog.math.Matrix)} fn |
| * The function to call for every element. This function |
| * takes 4 arguments (value, i, j, and the matrix) |
| * and the return value is irrelevant. |
| * @param {T=} opt_obj The object to be used as the value of 'this' |
| * within {@code fn}. |
| * @template T |
| */ |
| goog.math.Matrix.forEach = function(matrix, fn, opt_obj) { |
| for (var i = 0; i < matrix.getSize().height; i++) { |
| for (var j = 0; j < matrix.getSize().width; j++) { |
| fn.call(opt_obj, matrix.array_[i][j], i, j, matrix); |
| } |
| } |
| }; |
| |
| |
| /** |
| * Tests whether an array is a valid matrix. A valid array is an array of |
| * arrays where all arrays are of the same length and all elements are numbers. |
| * @param {!Array<!Array<number>>} arr An array to test. |
| * @return {boolean} Whether the array is a valid matrix. |
| */ |
| goog.math.Matrix.isValidArray = function(arr) { |
| var len = 0; |
| for (var i = 0; i < arr.length; i++) { |
| if (!goog.isArrayLike(arr[i]) || len > 0 && arr[i].length != len) { |
| return false; |
| } |
| for (var j = 0; j < arr[i].length; j++) { |
| if (!goog.isNumber(arr[i][j])) { |
| return false; |
| } |
| } |
| if (len == 0) { |
| len = arr[i].length; |
| } |
| } |
| return len != 0; |
| }; |
| |
| |
| /** |
| * Calls a function for every cell in a matrix and inserts the result into a |
| * new matrix of equal dimensions. |
| * @param {!goog.math.Matrix} matrix The matrix to iterate over. |
| * @param {function(this:T, number, number, number, !goog.math.Matrix): number} |
| * fn The function to call for every element. This function |
| * takes 4 arguments (value, i, j and the matrix) |
| * and should return a number, which will be inserted into a new matrix. |
| * @param {T=} opt_obj The object to be used as the value of 'this' |
| * within {@code fn}. |
| * @return {!goog.math.Matrix} A new matrix with the results from {@code fn}. |
| * @template T |
| */ |
| goog.math.Matrix.map = function(matrix, fn, opt_obj) { |
| var m = new goog.math.Matrix(matrix.getSize()); |
| goog.math.Matrix.forEach(matrix, function(value, i, j) { |
| m.array_[i][j] = fn.call(opt_obj, value, i, j, matrix); |
| }); |
| return m; |
| }; |
| |
| |
| /** |
| * Creates a new zero padded matix. |
| * @param {number} m Height of matrix. |
| * @param {number} n Width of matrix. |
| * @return {!Array<!Array<number>>} The new zero padded matrix. |
| * @private |
| */ |
| goog.math.Matrix.createZeroPaddedArray_ = function(m, n) { |
| var rv = []; |
| for (var i = 0; i < m; i++) { |
| rv[i] = []; |
| for (var j = 0; j < n; j++) { |
| rv[i][j] = 0; |
| } |
| } |
| return rv; |
| }; |
| |
| |
| /** |
| * Internal array representing the matrix. |
| * @type {!Array<!Array<number>>} |
| * @private |
| */ |
| goog.math.Matrix.prototype.array_; |
| |
| |
| /** |
| * After construction the Matrix's size is constant and stored in this object. |
| * @type {!goog.math.Size} |
| * @private |
| */ |
| goog.math.Matrix.prototype.size_; |
| |
| |
| /** |
| * Returns a new matrix that is the sum of this and the provided matrix. |
| * @param {goog.math.Matrix} m The matrix to add to this one. |
| * @return {!goog.math.Matrix} Resultant sum. |
| */ |
| goog.math.Matrix.prototype.add = function(m) { |
| if (!goog.math.Size.equals(this.size_, m.getSize())) { |
| throw Error('Matrix summation is only supported on arrays of equal size'); |
| } |
| return goog.math.Matrix.map(this, function(val, i, j) { |
| return val + m.array_[i][j]; |
| }); |
| }; |
| |
| |
| /** |
| * Appends the given matrix to the right side of this matrix. |
| * @param {goog.math.Matrix} m The matrix to augment this matrix with. |
| * @return {!goog.math.Matrix} A new matrix with additional columns on the |
| * right. |
| */ |
| goog.math.Matrix.prototype.appendColumns = function(m) { |
| if (this.size_.height != m.getSize().height) { |
| throw Error('The given matrix has height ' + m.size_.height + ', but ' + |
| ' needs to have height ' + this.size_.height + '.'); |
| } |
| var result = new goog.math.Matrix(this.size_.height, |
| this.size_.width + m.size_.width); |
| goog.math.Matrix.forEach(this, function(value, i, j) { |
| result.array_[i][j] = value; |
| }); |
| goog.math.Matrix.forEach(m, function(value, i, j) { |
| result.array_[i][this.size_.width + j] = value; |
| }, this); |
| return result; |
| }; |
| |
| |
| /** |
| * Appends the given matrix to the bottom of this matrix. |
| * @param {goog.math.Matrix} m The matrix to augment this matrix with. |
| * @return {!goog.math.Matrix} A new matrix with added columns on the bottom. |
| */ |
| goog.math.Matrix.prototype.appendRows = function(m) { |
| if (this.size_.width != m.getSize().width) { |
| throw Error('The given matrix has width ' + m.size_.width + ', but ' + |
| ' needs to have width ' + this.size_.width + '.'); |
| } |
| var result = new goog.math.Matrix(this.size_.height + m.size_.height, |
| this.size_.width); |
| goog.math.Matrix.forEach(this, function(value, i, j) { |
| result.array_[i][j] = value; |
| }); |
| goog.math.Matrix.forEach(m, function(value, i, j) { |
| result.array_[this.size_.height + i][j] = value; |
| }, this); |
| return result; |
| }; |
| |
| |
| /** |
| * Returns whether the given matrix equals this matrix. |
| * @param {goog.math.Matrix} m The matrix to compare to this one. |
| * @param {number=} opt_tolerance The tolerance when comparing array entries. |
| * @return {boolean} Whether the given matrix equals this matrix. |
| */ |
| goog.math.Matrix.prototype.equals = function(m, opt_tolerance) { |
| if (this.size_.width != m.size_.width) { |
| return false; |
| } |
| if (this.size_.height != m.size_.height) { |
| return false; |
| } |
| |
| var tolerance = opt_tolerance || 0; |
| for (var i = 0; i < this.size_.height; i++) { |
| for (var j = 0; j < this.size_.width; j++) { |
| if (!goog.math.nearlyEquals(this.array_[i][j], m.array_[i][j], |
| tolerance)) { |
| return false; |
| } |
| } |
| } |
| |
| return true; |
| }; |
| |
| |
| /** |
| * Returns the determinant of this matrix. The determinant of a matrix A is |
| * often denoted as |A| and can only be applied to a square matrix. |
| * @return {number} The determinant of this matrix. |
| */ |
| goog.math.Matrix.prototype.getDeterminant = function() { |
| if (!this.isSquare()) { |
| throw Error('A determinant can only be take on a square matrix'); |
| } |
| |
| return this.getDeterminant_(); |
| }; |
| |
| |
| /** |
| * Returns the inverse of this matrix if it exists or null if the matrix is |
| * not invertible. |
| * @return {goog.math.Matrix} A new matrix which is the inverse of this matrix. |
| */ |
| goog.math.Matrix.prototype.getInverse = function() { |
| if (!this.isSquare()) { |
| throw Error('An inverse can only be taken on a square matrix.'); |
| } |
| if (this.getSize().width == 1) { |
| var a = this.getValueAt(0, 0); |
| return a == 0 ? null : new goog.math.Matrix([[1 / a]]); |
| } |
| var identity = goog.math.Matrix.createIdentityMatrix(this.size_.height); |
| var mi = this.appendColumns(identity).getReducedRowEchelonForm(); |
| var i = mi.getSubmatrixByCoordinates_( |
| 0, 0, identity.size_.width - 1, identity.size_.height - 1); |
| if (!i.equals(identity)) { |
| return null; // This matrix was not invertible |
| } |
| return mi.getSubmatrixByCoordinates_(0, identity.size_.width); |
| }; |
| |
| |
| /** |
| * Transforms this matrix into reduced row echelon form. |
| * @return {!goog.math.Matrix} A new matrix reduced row echelon form. |
| */ |
| goog.math.Matrix.prototype.getReducedRowEchelonForm = function() { |
| var result = new goog.math.Matrix(this); |
| var col = 0; |
| // Each iteration puts one row in reduced row echelon form |
| for (var row = 0; row < result.size_.height; row++) { |
| if (col >= result.size_.width) { |
| return result; |
| } |
| |
| // Scan each column starting from this row on down for a non-zero value |
| var i = row; |
| while (result.array_[i][col] == 0) { |
| i++; |
| if (i == result.size_.height) { |
| i = row; |
| col++; |
| if (col == result.size_.width) { |
| return result; |
| } |
| } |
| } |
| |
| // Make the row we found the current row with a leading 1 |
| this.swapRows_(i, row); |
| var divisor = result.array_[row][col]; |
| for (var j = col; j < result.size_.width; j++) { |
| result.array_[row][j] = result.array_[row][j] / divisor; |
| } |
| |
| // Subtract a multiple of this row from each other row |
| // so that all the other entries in this column are 0 |
| for (i = 0; i < result.size_.height; i++) { |
| if (i != row) { |
| var multiple = result.array_[i][col]; |
| for (var j = col; j < result.size_.width; j++) { |
| result.array_[i][j] -= multiple * result.array_[row][j]; |
| } |
| } |
| } |
| |
| // Move on to the next column |
| col++; |
| } |
| return result; |
| }; |
| |
| |
| /** |
| * @return {!goog.math.Size} The dimensions of the matrix. |
| */ |
| goog.math.Matrix.prototype.getSize = function() { |
| return this.size_; |
| }; |
| |
| |
| /** |
| * Return the transpose of this matrix. For an m-by-n matrix, the transpose |
| * is the n-by-m matrix which results from turning rows into columns and columns |
| * into rows |
| * @return {!goog.math.Matrix} A new matrix A^T. |
| */ |
| goog.math.Matrix.prototype.getTranspose = function() { |
| var m = new goog.math.Matrix(this.size_.width, this.size_.height); |
| goog.math.Matrix.forEach(this, function(value, i, j) { |
| m.array_[j][i] = value; |
| }); |
| return m; |
| }; |
| |
| |
| /** |
| * Retrieves the value of a particular coordinate in the matrix or null if the |
| * requested coordinates are out of range. |
| * @param {number} i The i index of the coordinate. |
| * @param {number} j The j index of the coordinate. |
| * @return {?number} The value at the specified coordinate. |
| */ |
| goog.math.Matrix.prototype.getValueAt = function(i, j) { |
| if (!this.isInBounds_(i, j)) { |
| return null; |
| } |
| return this.array_[i][j]; |
| }; |
| |
| |
| /** |
| * @return {boolean} Whether the horizontal and vertical dimensions of this |
| * matrix are the same. |
| */ |
| goog.math.Matrix.prototype.isSquare = function() { |
| return this.size_.width == this.size_.height; |
| }; |
| |
| |
| /** |
| * Sets the value at a particular coordinate (if the coordinate is within the |
| * bounds of the matrix). |
| * @param {number} i The i index of the coordinate. |
| * @param {number} j The j index of the coordinate. |
| * @param {number} value The new value for the coordinate. |
| */ |
| goog.math.Matrix.prototype.setValueAt = function(i, j, value) { |
| if (!this.isInBounds_(i, j)) { |
| throw Error( |
| 'Index out of bounds when setting matrix value, (' + i + ',' + j + |
| ') in size (' + this.size_.height + ',' + this.size_.width + ')'); |
| } |
| this.array_[i][j] = value; |
| }; |
| |
| |
| /** |
| * Performs matrix or scalar multiplication on a matrix and returns the |
| * resultant matrix. |
| * |
| * Matrix multiplication is defined between two matrices only if the number of |
| * columns of the first matrix is the same as the number of rows of the second |
| * matrix. If A is an m-by-n matrix and B is an n-by-p matrix, then their |
| * product AB is an m-by-p matrix |
| * |
| * Scalar multiplication returns a matrix of the same size as the original, |
| * each value multiplied by the given value. |
| * |
| * @param {goog.math.Matrix|number} m Matrix/number to multiply the matrix by. |
| * @return {!goog.math.Matrix} Resultant product. |
| */ |
| goog.math.Matrix.prototype.multiply = function(m) { |
| if (m instanceof goog.math.Matrix) { |
| if (this.size_.width != m.getSize().height) { |
| throw Error('Invalid matrices for multiplication. Second matrix ' + |
| 'should have the same number of rows as the first has columns.'); |
| } |
| return this.matrixMultiply_(/** @type {!goog.math.Matrix} */ (m)); |
| } else if (goog.isNumber(m)) { |
| return this.scalarMultiply_(/** @type {number} */ (m)); |
| } else { |
| throw Error('A matrix can only be multiplied by' + |
| ' a number or another matrix.'); |
| } |
| }; |
| |
| |
| /** |
| * Returns a new matrix that is the difference of this and the provided matrix. |
| * @param {goog.math.Matrix} m The matrix to subtract from this one. |
| * @return {!goog.math.Matrix} Resultant difference. |
| */ |
| goog.math.Matrix.prototype.subtract = function(m) { |
| if (!goog.math.Size.equals(this.size_, m.getSize())) { |
| throw Error( |
| 'Matrix subtraction is only supported on arrays of equal size.'); |
| } |
| return goog.math.Matrix.map(this, function(val, i, j) { |
| return val - m.array_[i][j]; |
| }); |
| }; |
| |
| |
| /** |
| * @return {!Array<!Array<number>>} A 2D internal array representing this |
| * matrix. Not a clone. |
| */ |
| goog.math.Matrix.prototype.toArray = function() { |
| return this.array_; |
| }; |
| |
| |
| if (goog.DEBUG) { |
| /** |
| * Returns a string representation of the matrix. e.g. |
| * <pre> |
| * [ 12 5 9 1 ] |
| * [ 4 16 0 17 ] |
| * [ 12 5 1 23 ] |
| * </pre> |
| * |
| * @return {string} A string representation of this matrix. |
| * @override |
| */ |
| goog.math.Matrix.prototype.toString = function() { |
| // Calculate correct padding for optimum display of matrix |
| var maxLen = 0; |
| goog.math.Matrix.forEach(this, function(val) { |
| var len = String(val).length; |
| if (len > maxLen) { |
| maxLen = len; |
| } |
| }); |
| |
| // Build the string |
| var sb = []; |
| goog.array.forEach(this.array_, function(row, x) { |
| sb.push('[ '); |
| goog.array.forEach(row, function(val, y) { |
| var strval = String(val); |
| sb.push(goog.string.repeat(' ', maxLen - strval.length) + strval + ' '); |
| }); |
| sb.push(']\n'); |
| }); |
| |
| return sb.join(''); |
| }; |
| } |
| |
| |
| /** |
| * Returns the signed minor. |
| * @param {number} i The row index. |
| * @param {number} j The column index. |
| * @return {number} The cofactor C[i,j] of this matrix. |
| * @private |
| */ |
| goog.math.Matrix.prototype.getCofactor_ = function(i, j) { |
| return (i + j % 2 == 0 ? 1 : -1) * this.getMinor_(i, j); |
| }; |
| |
| |
| /** |
| * Returns the determinant of this matrix. The determinant of a matrix A is |
| * often denoted as |A| and can only be applied to a square matrix. Same as |
| * public method but without validation. Implemented using Laplace's formula. |
| * @return {number} The determinant of this matrix. |
| * @private |
| */ |
| goog.math.Matrix.prototype.getDeterminant_ = function() { |
| if (this.getSize().area() == 1) { |
| return this.array_[0][0]; |
| } |
| |
| // We might want to use matrix decomposition to improve running time |
| // For now we'll do a Laplace expansion along the first row |
| var determinant = 0; |
| for (var j = 0; j < this.size_.width; j++) { |
| determinant += (this.array_[0][j] * this.getCofactor_(0, j)); |
| } |
| return determinant; |
| }; |
| |
| |
| /** |
| * Returns the determinant of the submatrix resulting from the deletion of row i |
| * and column j. |
| * @param {number} i The row to delete. |
| * @param {number} j The column to delete. |
| * @return {number} The first minor M[i,j] of this matrix. |
| * @private |
| */ |
| goog.math.Matrix.prototype.getMinor_ = function(i, j) { |
| return this.getSubmatrixByDeletion_(i, j).getDeterminant_(); |
| }; |
| |
| |
| /** |
| * Returns a submatrix contained within this matrix. |
| * @param {number} i1 The upper row index. |
| * @param {number} j1 The left column index. |
| * @param {number=} opt_i2 The lower row index. |
| * @param {number=} opt_j2 The right column index. |
| * @return {!goog.math.Matrix} The submatrix contained within the given bounds. |
| * @private |
| */ |
| goog.math.Matrix.prototype.getSubmatrixByCoordinates_ = |
| function(i1, j1, opt_i2, opt_j2) { |
| var i2 = opt_i2 ? opt_i2 : this.size_.height - 1; |
| var j2 = opt_j2 ? opt_j2 : this.size_.width - 1; |
| var result = new goog.math.Matrix(i2 - i1 + 1, j2 - j1 + 1); |
| goog.math.Matrix.forEach(result, function(value, i, j) { |
| result.array_[i][j] = this.array_[i1 + i][j1 + j]; |
| }, this); |
| return result; |
| }; |
| |
| |
| /** |
| * Returns a new matrix equal to this one, but with row i and column j deleted. |
| * @param {number} i The row index of the coordinate. |
| * @param {number} j The column index of the coordinate. |
| * @return {!goog.math.Matrix} The value at the specified coordinate. |
| * @private |
| */ |
| goog.math.Matrix.prototype.getSubmatrixByDeletion_ = function(i, j) { |
| var m = new goog.math.Matrix(this.size_.width - 1, this.size_.height - 1); |
| goog.math.Matrix.forEach(m, function(value, x, y) { |
| m.setValueAt(x, y, this.array_[x >= i ? x + 1 : x][y >= j ? y + 1 : y]); |
| }, this); |
| return m; |
| }; |
| |
| |
| /** |
| * Returns whether the given coordinates are contained within the bounds of the |
| * matrix. |
| * @param {number} i The i index of the coordinate. |
| * @param {number} j The j index of the coordinate. |
| * @return {boolean} The value at the specified coordinate. |
| * @private |
| */ |
| goog.math.Matrix.prototype.isInBounds_ = function(i, j) { |
| return i >= 0 && i < this.size_.height && |
| j >= 0 && j < this.size_.width; |
| }; |
| |
| |
| /** |
| * Matrix multiplication is defined between two matrices only if the number of |
| * columns of the first matrix is the same as the number of rows of the second |
| * matrix. If A is an m-by-n matrix and B is an n-by-p matrix, then their |
| * product AB is an m-by-p matrix |
| * |
| * @param {goog.math.Matrix} m Matrix to multiply the matrix by. |
| * @return {!goog.math.Matrix} Resultant product. |
| * @private |
| */ |
| goog.math.Matrix.prototype.matrixMultiply_ = function(m) { |
| var resultMatrix = new goog.math.Matrix(this.size_.height, m.getSize().width); |
| goog.math.Matrix.forEach(resultMatrix, function(val, x, y) { |
| var newVal = 0; |
| for (var i = 0; i < this.size_.width; i++) { |
| newVal += this.getValueAt(x, i) * m.getValueAt(i, y); |
| } |
| resultMatrix.setValueAt(x, y, newVal); |
| }, this); |
| return resultMatrix; |
| }; |
| |
| |
| /** |
| * Scalar multiplication returns a matrix of the same size as the original, |
| * each value multiplied by the given value. |
| * |
| * @param {number} m number to multiply the matrix by. |
| * @return {!goog.math.Matrix} Resultant product. |
| * @private |
| */ |
| goog.math.Matrix.prototype.scalarMultiply_ = function(m) { |
| return goog.math.Matrix.map(this, function(val, x, y) { |
| return val * m; |
| }); |
| }; |
| |
| |
| /** |
| * Swaps two rows. |
| * @param {number} i1 The index of the first row to swap. |
| * @param {number} i2 The index of the second row to swap. |
| * @private |
| */ |
| goog.math.Matrix.prototype.swapRows_ = function(i1, i2) { |
| var tmp = this.array_[i1]; |
| this.array_[i1] = this.array_[i2]; |
| this.array_[i2] = tmp; |
| }; |