001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018 package org.apache.commons.math.linear; 019 020 import java.io.Serializable; 021 022 import org.apache.commons.math.MathRuntimeException; 023 024 /** 025 * Implementation of RealMatrix using a double[][] array to store entries and 026 * <a href="http://www.math.gatech.edu/~bourbaki/math2601/Web-notes/2num.pdf"> 027 * LU decomposition</a> to support linear system 028 * solution and inverse. 029 * <p> 030 * The LU decomposition is performed as needed, to support the following operations: <ul> 031 * <li>solve</li> 032 * <li>isSingular</li> 033 * <li>getDeterminant</li> 034 * <li>inverse</li> </ul></p> 035 * <p> 036 * <strong>Usage notes</strong>:<br> 037 * <ul><li> 038 * The LU decomposition is cached and reused on subsequent calls. 039 * If data are modified via references to the underlying array obtained using 040 * <code>getDataRef()</code>, then the stored LU decomposition will not be 041 * discarded. In this case, you need to explicitly invoke 042 * <code>LUDecompose()</code> to recompute the decomposition 043 * before using any of the methods above.</li> 044 * <li> 045 * As specified in the {@link RealMatrix} interface, matrix element indexing 046 * is 0-based -- e.g., <code>getEntry(0, 0)</code> 047 * returns the element in the first row, first column of the matrix.</li></ul> 048 * </p> 049 * 050 * @version $Revision: 783702 $ $Date: 2009-06-11 04:54:02 -0400 (Thu, 11 Jun 2009) $ 051 */ 052 public class Array2DRowRealMatrix extends AbstractRealMatrix implements Serializable { 053 054 /** Serializable version identifier */ 055 private static final long serialVersionUID = -1067294169172445528L; 056 057 /** Entries of the matrix */ 058 protected double data[][]; 059 060 /** 061 * Creates a matrix with no data 062 */ 063 public Array2DRowRealMatrix() { 064 } 065 066 /** 067 * Create a new RealMatrix with the supplied row and column dimensions. 068 * 069 * @param rowDimension the number of rows in the new matrix 070 * @param columnDimension the number of columns in the new matrix 071 * @throws IllegalArgumentException if row or column dimension is not 072 * positive 073 */ 074 public Array2DRowRealMatrix(final int rowDimension, final int columnDimension) 075 throws IllegalArgumentException { 076 super(rowDimension, columnDimension); 077 data = new double[rowDimension][columnDimension]; 078 } 079 080 /** 081 * Create a new RealMatrix using the input array as the underlying 082 * data array. 083 * <p>The input array is copied, not referenced. This constructor has 084 * the same effect as calling {@link #Array2DRowRealMatrix(double[][], boolean)} 085 * with the second argument set to <code>true</code>.</p> 086 * 087 * @param d data for new matrix 088 * @throws IllegalArgumentException if <code>d</code> is not rectangular 089 * (not all rows have the same length) or empty 090 * @throws NullPointerException if <code>d</code> is null 091 * @see #Array2DRowRealMatrix(double[][], boolean) 092 */ 093 public Array2DRowRealMatrix(final double[][] d) 094 throws IllegalArgumentException, NullPointerException { 095 copyIn(d); 096 } 097 098 /** 099 * Create a new RealMatrix using the input array as the underlying 100 * data array. 101 * <p>If an array is built specially in order to be embedded in a 102 * RealMatrix and not used directly, the <code>copyArray</code> may be 103 * set to <code>false</code. This will prevent the copying and improve 104 * performance as no new array will be built and no data will be copied.</p> 105 * @param d data for new matrix 106 * @param copyArray if true, the input array will be copied, otherwise 107 * it will be referenced 108 * @throws IllegalArgumentException if <code>d</code> is not rectangular 109 * (not all rows have the same length) or empty 110 * @throws NullPointerException if <code>d</code> is null 111 * @see #Array2DRowRealMatrix(double[][]) 112 */ 113 public Array2DRowRealMatrix(final double[][] d, final boolean copyArray) 114 throws IllegalArgumentException, NullPointerException { 115 if (copyArray) { 116 copyIn(d); 117 } else { 118 if (d == null) { 119 throw new NullPointerException(); 120 } 121 final int nRows = d.length; 122 if (nRows == 0) { 123 throw MathRuntimeException.createIllegalArgumentException("matrix must have at least one row"); 124 } 125 final int nCols = d[0].length; 126 if (nCols == 0) { 127 throw MathRuntimeException.createIllegalArgumentException("matrix must have at least one column"); 128 } 129 for (int r = 1; r < nRows; r++) { 130 if (d[r].length != nCols) { 131 throw MathRuntimeException.createIllegalArgumentException( 132 "some rows have length {0} while others have length {1}", 133 nCols, d[r].length); 134 } 135 } 136 data = d; 137 } 138 } 139 140 /** 141 * Create a new (column) RealMatrix using <code>v</code> as the 142 * data for the unique column of the <code>v.length x 1</code> matrix 143 * created. 144 * <p>The input array is copied, not referenced.</p> 145 * 146 * @param v column vector holding data for new matrix 147 */ 148 public Array2DRowRealMatrix(final double[] v) { 149 final int nRows = v.length; 150 data = new double[nRows][1]; 151 for (int row = 0; row < nRows; row++) { 152 data[row][0] = v[row]; 153 } 154 } 155 156 /** {@inheritDoc} */ 157 @Override 158 public RealMatrix createMatrix(final int rowDimension, final int columnDimension) 159 throws IllegalArgumentException { 160 return new Array2DRowRealMatrix(rowDimension, columnDimension); 161 } 162 163 /** {@inheritDoc} */ 164 @Override 165 public RealMatrix copy() { 166 return new Array2DRowRealMatrix(copyOut(), false); 167 } 168 169 /** {@inheritDoc} */ 170 @Override 171 public RealMatrix add(final RealMatrix m) 172 throws IllegalArgumentException { 173 try { 174 return add((Array2DRowRealMatrix) m); 175 } catch (ClassCastException cce) { 176 return super.add(m); 177 } 178 } 179 180 /** 181 * Compute the sum of this and <code>m</code>. 182 * 183 * @param m matrix to be added 184 * @return this + m 185 * @throws IllegalArgumentException if m is not the same size as this 186 */ 187 public Array2DRowRealMatrix add(final Array2DRowRealMatrix m) 188 throws IllegalArgumentException { 189 190 // safety check 191 MatrixUtils.checkAdditionCompatible(this, m); 192 193 final int rowCount = getRowDimension(); 194 final int columnCount = getColumnDimension(); 195 final double[][] outData = new double[rowCount][columnCount]; 196 for (int row = 0; row < rowCount; row++) { 197 final double[] dataRow = data[row]; 198 final double[] mRow = m.data[row]; 199 final double[] outDataRow = outData[row]; 200 for (int col = 0; col < columnCount; col++) { 201 outDataRow[col] = dataRow[col] + mRow[col]; 202 } 203 } 204 205 return new Array2DRowRealMatrix(outData, false); 206 207 } 208 209 /** {@inheritDoc} */ 210 @Override 211 public RealMatrix subtract(final RealMatrix m) 212 throws IllegalArgumentException { 213 try { 214 return subtract((Array2DRowRealMatrix) m); 215 } catch (ClassCastException cce) { 216 return super.subtract(m); 217 } 218 } 219 220 /** 221 * Compute this minus <code>m</code>. 222 * 223 * @param m matrix to be subtracted 224 * @return this + m 225 * @throws IllegalArgumentException if m is not the same size as this 226 */ 227 public Array2DRowRealMatrix subtract(final Array2DRowRealMatrix m) 228 throws IllegalArgumentException { 229 230 // safety check 231 MatrixUtils.checkSubtractionCompatible(this, m); 232 233 final int rowCount = getRowDimension(); 234 final int columnCount = getColumnDimension(); 235 final double[][] outData = new double[rowCount][columnCount]; 236 for (int row = 0; row < rowCount; row++) { 237 final double[] dataRow = data[row]; 238 final double[] mRow = m.data[row]; 239 final double[] outDataRow = outData[row]; 240 for (int col = 0; col < columnCount; col++) { 241 outDataRow[col] = dataRow[col] - mRow[col]; 242 } 243 } 244 245 return new Array2DRowRealMatrix(outData, false); 246 247 } 248 249 /** {@inheritDoc} */ 250 @Override 251 public RealMatrix multiply(final RealMatrix m) 252 throws IllegalArgumentException { 253 try { 254 return multiply((Array2DRowRealMatrix) m); 255 } catch (ClassCastException cce) { 256 return super.multiply(m); 257 } 258 } 259 260 /** 261 * Returns the result of postmultiplying this by <code>m</code>. 262 * @param m matrix to postmultiply by 263 * @return this*m 264 * @throws IllegalArgumentException 265 * if columnDimension(this) != rowDimension(m) 266 */ 267 public Array2DRowRealMatrix multiply(final Array2DRowRealMatrix m) 268 throws IllegalArgumentException { 269 270 // safety check 271 MatrixUtils.checkMultiplicationCompatible(this, m); 272 273 final int nRows = this.getRowDimension(); 274 final int nCols = m.getColumnDimension(); 275 final int nSum = this.getColumnDimension(); 276 final double[][] outData = new double[nRows][nCols]; 277 for (int row = 0; row < nRows; row++) { 278 final double[] dataRow = data[row]; 279 final double[] outDataRow = outData[row]; 280 for (int col = 0; col < nCols; col++) { 281 double sum = 0; 282 for (int i = 0; i < nSum; i++) { 283 sum += dataRow[i] * m.data[i][col]; 284 } 285 outDataRow[col] = sum; 286 } 287 } 288 289 return new Array2DRowRealMatrix(outData, false); 290 291 } 292 293 /** {@inheritDoc} */ 294 @Override 295 public double[][] getData() { 296 return copyOut(); 297 } 298 299 /** 300 * Returns a reference to the underlying data array. 301 * <p> 302 * Does <strong>not</strong> make a fresh copy of the underlying data.</p> 303 * 304 * @return 2-dimensional array of entries 305 */ 306 public double[][] getDataRef() { 307 return data; 308 } 309 310 /** {@inheritDoc} */ 311 @Override 312 public void setSubMatrix(final double[][] subMatrix, final int row, final int column) 313 throws MatrixIndexException { 314 if (data == null) { 315 if (row > 0) { 316 throw MathRuntimeException.createIllegalStateException( 317 "first {0} rows are not initialized yet", 318 row); 319 } 320 if (column > 0) { 321 throw MathRuntimeException.createIllegalStateException( 322 "first {0} columns are not initialized yet", 323 column); 324 } 325 final int nRows = subMatrix.length; 326 if (nRows == 0) { 327 throw MathRuntimeException.createIllegalArgumentException("matrix must have at least one row"); 328 } 329 330 final int nCols = subMatrix[0].length; 331 if (nCols == 0) { 332 throw MathRuntimeException.createIllegalArgumentException("matrix must have at least one column"); 333 } 334 data = new double[subMatrix.length][nCols]; 335 for (int i = 0; i < data.length; ++i) { 336 if (subMatrix[i].length != nCols) { 337 throw MathRuntimeException.createIllegalArgumentException( 338 "some rows have length {0} while others have length {1}", 339 nCols, subMatrix[i].length); 340 } 341 System.arraycopy(subMatrix[i], 0, data[i + row], column, nCols); 342 } 343 } else { 344 super.setSubMatrix(subMatrix, row, column); 345 } 346 347 } 348 349 /** {@inheritDoc} */ 350 @Override 351 public double getEntry(final int row, final int column) 352 throws MatrixIndexException { 353 try { 354 return data[row][column]; 355 } catch (ArrayIndexOutOfBoundsException e) { 356 throw new MatrixIndexException( 357 "no entry at indices ({0}, {1}) in a {2}x{3} matrix", 358 row, column, getRowDimension(), getColumnDimension()); 359 } 360 } 361 362 /** {@inheritDoc} */ 363 @Override 364 public void setEntry(final int row, final int column, final double value) 365 throws MatrixIndexException { 366 try { 367 data[row][column] = value; 368 } catch (ArrayIndexOutOfBoundsException e) { 369 throw new MatrixIndexException( 370 "no entry at indices ({0}, {1}) in a {2}x{3} matrix", 371 row, column, getRowDimension(), getColumnDimension()); 372 } 373 } 374 375 /** {@inheritDoc} */ 376 @Override 377 public void addToEntry(final int row, final int column, final double increment) 378 throws MatrixIndexException { 379 try { 380 data[row][column] += increment; 381 } catch (ArrayIndexOutOfBoundsException e) { 382 throw new MatrixIndexException( 383 "no entry at indices ({0}, {1}) in a {2}x{3} matrix", 384 row, column, getRowDimension(), getColumnDimension()); 385 } 386 } 387 388 /** {@inheritDoc} */ 389 @Override 390 public void multiplyEntry(final int row, final int column, final double factor) 391 throws MatrixIndexException { 392 try { 393 data[row][column] *= factor; 394 } catch (ArrayIndexOutOfBoundsException e) { 395 throw new MatrixIndexException( 396 "no entry at indices ({0}, {1}) in a {2}x{3} matrix", 397 row, column, getRowDimension(), getColumnDimension()); 398 } 399 } 400 401 /** {@inheritDoc} */ 402 @Override 403 public int getRowDimension() { 404 return (data == null) ? 0 : data.length; 405 } 406 407 /** {@inheritDoc} */ 408 @Override 409 public int getColumnDimension() { 410 return ((data == null) || (data[0] == null)) ? 0 : data[0].length; 411 } 412 413 /** {@inheritDoc} */ 414 @Override 415 public double[] operate(final double[] v) 416 throws IllegalArgumentException { 417 final int nRows = this.getRowDimension(); 418 final int nCols = this.getColumnDimension(); 419 if (v.length != nCols) { 420 throw MathRuntimeException.createIllegalArgumentException( 421 "vector length mismatch: got {0} but expected {1}", 422 v.length, nCols); 423 } 424 final double[] out = new double[nRows]; 425 for (int row = 0; row < nRows; row++) { 426 final double[] dataRow = data[row]; 427 double sum = 0; 428 for (int i = 0; i < nCols; i++) { 429 sum += dataRow[i] * v[i]; 430 } 431 out[row] = sum; 432 } 433 return out; 434 } 435 436 /** {@inheritDoc} */ 437 @Override 438 public double[] preMultiply(final double[] v) 439 throws IllegalArgumentException { 440 441 final int nRows = getRowDimension(); 442 final int nCols = getColumnDimension(); 443 if (v.length != nRows) { 444 throw MathRuntimeException.createIllegalArgumentException( 445 "vector length mismatch: got {0} but expected {1}", 446 v.length, nRows); 447 } 448 449 final double[] out = new double[nCols]; 450 for (int col = 0; col < nCols; ++col) { 451 double sum = 0; 452 for (int i = 0; i < nRows; ++i) { 453 sum += data[i][col] * v[i]; 454 } 455 out[col] = sum; 456 } 457 458 return out; 459 460 } 461 462 /** {@inheritDoc} */ 463 @Override 464 public double walkInRowOrder(final RealMatrixChangingVisitor visitor) 465 throws MatrixVisitorException { 466 final int rows = getRowDimension(); 467 final int columns = getColumnDimension(); 468 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 469 for (int i = 0; i < rows; ++i) { 470 final double[] rowI = data[i]; 471 for (int j = 0; j < columns; ++j) { 472 rowI[j] = visitor.visit(i, j, rowI[j]); 473 } 474 } 475 return visitor.end(); 476 } 477 478 /** {@inheritDoc} */ 479 @Override 480 public double walkInRowOrder(final RealMatrixPreservingVisitor visitor) 481 throws MatrixVisitorException { 482 final int rows = getRowDimension(); 483 final int columns = getColumnDimension(); 484 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 485 for (int i = 0; i < rows; ++i) { 486 final double[] rowI = data[i]; 487 for (int j = 0; j < columns; ++j) { 488 visitor.visit(i, j, rowI[j]); 489 } 490 } 491 return visitor.end(); 492 } 493 494 /** {@inheritDoc} */ 495 @Override 496 public double walkInRowOrder(final RealMatrixChangingVisitor visitor, 497 final int startRow, final int endRow, 498 final int startColumn, final int endColumn) 499 throws MatrixIndexException, MatrixVisitorException { 500 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 501 visitor.start(getRowDimension(), getColumnDimension(), 502 startRow, endRow, startColumn, endColumn); 503 for (int i = startRow; i <= endRow; ++i) { 504 final double[] rowI = data[i]; 505 for (int j = startColumn; j <= endColumn; ++j) { 506 rowI[j] = visitor.visit(i, j, rowI[j]); 507 } 508 } 509 return visitor.end(); 510 } 511 512 /** {@inheritDoc} */ 513 @Override 514 public double walkInRowOrder(final RealMatrixPreservingVisitor visitor, 515 final int startRow, final int endRow, 516 final int startColumn, final int endColumn) 517 throws MatrixIndexException, MatrixVisitorException { 518 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 519 visitor.start(getRowDimension(), getColumnDimension(), 520 startRow, endRow, startColumn, endColumn); 521 for (int i = startRow; i <= endRow; ++i) { 522 final double[] rowI = data[i]; 523 for (int j = startColumn; j <= endColumn; ++j) { 524 visitor.visit(i, j, rowI[j]); 525 } 526 } 527 return visitor.end(); 528 } 529 530 /** {@inheritDoc} */ 531 @Override 532 public double walkInColumnOrder(final RealMatrixChangingVisitor visitor) 533 throws MatrixVisitorException { 534 final int rows = getRowDimension(); 535 final int columns = getColumnDimension(); 536 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 537 for (int j = 0; j < columns; ++j) { 538 for (int i = 0; i < rows; ++i) { 539 final double[] rowI = data[i]; 540 rowI[j] = visitor.visit(i, j, rowI[j]); 541 } 542 } 543 return visitor.end(); 544 } 545 546 /** {@inheritDoc} */ 547 @Override 548 public double walkInColumnOrder(final RealMatrixPreservingVisitor visitor) 549 throws MatrixVisitorException { 550 final int rows = getRowDimension(); 551 final int columns = getColumnDimension(); 552 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 553 for (int j = 0; j < columns; ++j) { 554 for (int i = 0; i < rows; ++i) { 555 visitor.visit(i, j, data[i][j]); 556 } 557 } 558 return visitor.end(); 559 } 560 561 /** {@inheritDoc} */ 562 @Override 563 public double walkInColumnOrder(final RealMatrixChangingVisitor visitor, 564 final int startRow, final int endRow, 565 final int startColumn, final int endColumn) 566 throws MatrixIndexException, MatrixVisitorException { 567 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 568 visitor.start(getRowDimension(), getColumnDimension(), 569 startRow, endRow, startColumn, endColumn); 570 for (int j = startColumn; j <= endColumn; ++j) { 571 for (int i = startRow; i <= endRow; ++i) { 572 final double[] rowI = data[i]; 573 rowI[j] = visitor.visit(i, j, rowI[j]); 574 } 575 } 576 return visitor.end(); 577 } 578 579 /** {@inheritDoc} */ 580 @Override 581 public double walkInColumnOrder(final RealMatrixPreservingVisitor visitor, 582 final int startRow, final int endRow, 583 final int startColumn, final int endColumn) 584 throws MatrixIndexException, MatrixVisitorException { 585 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 586 visitor.start(getRowDimension(), getColumnDimension(), 587 startRow, endRow, startColumn, endColumn); 588 for (int j = startColumn; j <= endColumn; ++j) { 589 for (int i = startRow; i <= endRow; ++i) { 590 visitor.visit(i, j, data[i][j]); 591 } 592 } 593 return visitor.end(); 594 } 595 596 /** 597 * Returns a fresh copy of the underlying data array. 598 * 599 * @return a copy of the underlying data array. 600 */ 601 private double[][] copyOut() { 602 final int nRows = this.getRowDimension(); 603 final double[][] out = new double[nRows][this.getColumnDimension()]; 604 // can't copy 2-d array in one shot, otherwise get row references 605 for (int i = 0; i < nRows; i++) { 606 System.arraycopy(data[i], 0, out[i], 0, data[i].length); 607 } 608 return out; 609 } 610 611 /** 612 * Replaces data with a fresh copy of the input array. 613 * <p> 614 * Verifies that the input array is rectangular and non-empty.</p> 615 * 616 * @param in data to copy in 617 * @throws IllegalArgumentException if input array is empty or not 618 * rectangular 619 * @throws NullPointerException if input array is null 620 */ 621 private void copyIn(final double[][] in) { 622 setSubMatrix(in, 0, 0); 623 } 624 625 }