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: 885278 $ $Date: 2009-11-29 16:47:51 -0500 (Sun, 29 Nov 2009) $ 051 */ 052 public class Array2DRowRealMatrix extends AbstractRealMatrix implements Serializable { 053 054 /** Serializable version identifier */ 055 private static final long serialVersionUID = -1067294169172445528L; 056 057 /** Message for at least one row. */ 058 private static final String AT_LEAST_ONE_ROW_MESSAGE = 059 "matrix must have at least one row"; 060 061 /** Message for at least one column. */ 062 private static final String AT_LEAST_ONE_COLUMN_MESSAGE = 063 "matrix must have at least one column"; 064 065 /** Message for different rows lengths. */ 066 private static final String DIFFERENT_ROWS_LENGTHS_MESSAGE = 067 "some rows have length {0} while others have length {1}"; 068 069 /** Message for no entry at selected indices. */ 070 private static final String NO_ENTRY_MESSAGE = 071 "no entry at indices ({0}, {1}) in a {2}x{3} matrix"; 072 073 /** Message for vector lengths mismatch. */ 074 private static final String VECTOR_LENGTHS_MISMATCH = 075 "vector length mismatch: got {0} but expected {1}"; 076 077 /** Entries of the matrix */ 078 protected double data[][]; 079 080 /** 081 * Creates a matrix with no data 082 */ 083 public Array2DRowRealMatrix() { 084 } 085 086 /** 087 * Create a new RealMatrix with the supplied row and column dimensions. 088 * 089 * @param rowDimension the number of rows in the new matrix 090 * @param columnDimension the number of columns in the new matrix 091 * @throws IllegalArgumentException if row or column dimension is not 092 * positive 093 */ 094 public Array2DRowRealMatrix(final int rowDimension, final int columnDimension) 095 throws IllegalArgumentException { 096 super(rowDimension, columnDimension); 097 data = new double[rowDimension][columnDimension]; 098 } 099 100 /** 101 * Create a new RealMatrix using the input array as the underlying 102 * data array. 103 * <p>The input array is copied, not referenced. This constructor has 104 * the same effect as calling {@link #Array2DRowRealMatrix(double[][], boolean)} 105 * with the second argument set to <code>true</code>.</p> 106 * 107 * @param d data for new matrix 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[][], boolean) 112 */ 113 public Array2DRowRealMatrix(final double[][] d) 114 throws IllegalArgumentException, NullPointerException { 115 copyIn(d); 116 } 117 118 /** 119 * Create a new RealMatrix using the input array as the underlying 120 * data array. 121 * <p>If an array is built specially in order to be embedded in a 122 * RealMatrix and not used directly, the <code>copyArray</code> may be 123 * set to <code>false</code. This will prevent the copying and improve 124 * performance as no new array will be built and no data will be copied.</p> 125 * @param d data for new matrix 126 * @param copyArray if true, the input array will be copied, otherwise 127 * it will be referenced 128 * @throws IllegalArgumentException if <code>d</code> is not rectangular 129 * (not all rows have the same length) or empty 130 * @throws NullPointerException if <code>d</code> is null 131 * @see #Array2DRowRealMatrix(double[][]) 132 */ 133 public Array2DRowRealMatrix(final double[][] d, final boolean copyArray) 134 throws IllegalArgumentException, NullPointerException { 135 if (copyArray) { 136 copyIn(d); 137 } else { 138 if (d == null) { 139 throw new NullPointerException(); 140 } 141 final int nRows = d.length; 142 if (nRows == 0) { 143 throw MathRuntimeException.createIllegalArgumentException( 144 AT_LEAST_ONE_ROW_MESSAGE); 145 } 146 final int nCols = d[0].length; 147 if (nCols == 0) { 148 throw MathRuntimeException.createIllegalArgumentException( 149 AT_LEAST_ONE_COLUMN_MESSAGE); 150 } 151 for (int r = 1; r < nRows; r++) { 152 if (d[r].length != nCols) { 153 throw MathRuntimeException.createIllegalArgumentException( 154 DIFFERENT_ROWS_LENGTHS_MESSAGE, nCols, d[r].length); 155 } 156 } 157 data = d; 158 } 159 } 160 161 /** 162 * Create a new (column) RealMatrix using <code>v</code> as the 163 * data for the unique column of the <code>v.length x 1</code> matrix 164 * created. 165 * <p>The input array is copied, not referenced.</p> 166 * 167 * @param v column vector holding data for new matrix 168 */ 169 public Array2DRowRealMatrix(final double[] v) { 170 final int nRows = v.length; 171 data = new double[nRows][1]; 172 for (int row = 0; row < nRows; row++) { 173 data[row][0] = v[row]; 174 } 175 } 176 177 /** {@inheritDoc} */ 178 @Override 179 public RealMatrix createMatrix(final int rowDimension, final int columnDimension) 180 throws IllegalArgumentException { 181 return new Array2DRowRealMatrix(rowDimension, columnDimension); 182 } 183 184 /** {@inheritDoc} */ 185 @Override 186 public RealMatrix copy() { 187 return new Array2DRowRealMatrix(copyOut(), false); 188 } 189 190 /** {@inheritDoc} */ 191 @Override 192 public RealMatrix add(final RealMatrix m) 193 throws IllegalArgumentException { 194 try { 195 return add((Array2DRowRealMatrix) m); 196 } catch (ClassCastException cce) { 197 return super.add(m); 198 } 199 } 200 201 /** 202 * Compute the sum of this and <code>m</code>. 203 * 204 * @param m matrix to be added 205 * @return this + m 206 * @throws IllegalArgumentException if m is not the same size as this 207 */ 208 public Array2DRowRealMatrix add(final Array2DRowRealMatrix m) 209 throws IllegalArgumentException { 210 211 // safety check 212 MatrixUtils.checkAdditionCompatible(this, m); 213 214 final int rowCount = getRowDimension(); 215 final int columnCount = getColumnDimension(); 216 final double[][] outData = new double[rowCount][columnCount]; 217 for (int row = 0; row < rowCount; row++) { 218 final double[] dataRow = data[row]; 219 final double[] mRow = m.data[row]; 220 final double[] outDataRow = outData[row]; 221 for (int col = 0; col < columnCount; col++) { 222 outDataRow[col] = dataRow[col] + mRow[col]; 223 } 224 } 225 226 return new Array2DRowRealMatrix(outData, false); 227 228 } 229 230 /** {@inheritDoc} */ 231 @Override 232 public RealMatrix subtract(final RealMatrix m) 233 throws IllegalArgumentException { 234 try { 235 return subtract((Array2DRowRealMatrix) m); 236 } catch (ClassCastException cce) { 237 return super.subtract(m); 238 } 239 } 240 241 /** 242 * Compute this minus <code>m</code>. 243 * 244 * @param m matrix to be subtracted 245 * @return this + m 246 * @throws IllegalArgumentException if m is not the same size as this 247 */ 248 public Array2DRowRealMatrix subtract(final Array2DRowRealMatrix m) 249 throws IllegalArgumentException { 250 251 // safety check 252 MatrixUtils.checkSubtractionCompatible(this, m); 253 254 final int rowCount = getRowDimension(); 255 final int columnCount = getColumnDimension(); 256 final double[][] outData = new double[rowCount][columnCount]; 257 for (int row = 0; row < rowCount; row++) { 258 final double[] dataRow = data[row]; 259 final double[] mRow = m.data[row]; 260 final double[] outDataRow = outData[row]; 261 for (int col = 0; col < columnCount; col++) { 262 outDataRow[col] = dataRow[col] - mRow[col]; 263 } 264 } 265 266 return new Array2DRowRealMatrix(outData, false); 267 268 } 269 270 /** {@inheritDoc} */ 271 @Override 272 public RealMatrix multiply(final RealMatrix m) 273 throws IllegalArgumentException { 274 try { 275 return multiply((Array2DRowRealMatrix) m); 276 } catch (ClassCastException cce) { 277 return super.multiply(m); 278 } 279 } 280 281 /** 282 * Returns the result of postmultiplying this by <code>m</code>. 283 * @param m matrix to postmultiply by 284 * @return this*m 285 * @throws IllegalArgumentException 286 * if columnDimension(this) != rowDimension(m) 287 */ 288 public Array2DRowRealMatrix multiply(final Array2DRowRealMatrix m) 289 throws IllegalArgumentException { 290 291 // safety check 292 MatrixUtils.checkMultiplicationCompatible(this, m); 293 294 final int nRows = this.getRowDimension(); 295 final int nCols = m.getColumnDimension(); 296 final int nSum = this.getColumnDimension(); 297 final double[][] outData = new double[nRows][nCols]; 298 for (int row = 0; row < nRows; row++) { 299 final double[] dataRow = data[row]; 300 final double[] outDataRow = outData[row]; 301 for (int col = 0; col < nCols; col++) { 302 double sum = 0; 303 for (int i = 0; i < nSum; i++) { 304 sum += dataRow[i] * m.data[i][col]; 305 } 306 outDataRow[col] = sum; 307 } 308 } 309 310 return new Array2DRowRealMatrix(outData, false); 311 312 } 313 314 /** {@inheritDoc} */ 315 @Override 316 public double[][] getData() { 317 return copyOut(); 318 } 319 320 /** 321 * Returns a reference to the underlying data array. 322 * <p> 323 * Does <strong>not</strong> make a fresh copy of the underlying data.</p> 324 * 325 * @return 2-dimensional array of entries 326 */ 327 public double[][] getDataRef() { 328 return data; 329 } 330 331 /** {@inheritDoc} */ 332 @Override 333 public void setSubMatrix(final double[][] subMatrix, final int row, final int column) 334 throws MatrixIndexException { 335 if (data == null) { 336 if (row > 0) { 337 throw MathRuntimeException.createIllegalStateException( 338 "first {0} rows are not initialized yet", row); 339 } 340 if (column > 0) { 341 throw MathRuntimeException.createIllegalStateException( 342 "first {0} columns are not initialized yet", column); 343 } 344 final int nRows = subMatrix.length; 345 if (nRows == 0) { 346 throw MathRuntimeException.createIllegalArgumentException( 347 AT_LEAST_ONE_ROW_MESSAGE); 348 } 349 350 final int nCols = subMatrix[0].length; 351 if (nCols == 0) { 352 throw MathRuntimeException.createIllegalArgumentException( 353 AT_LEAST_ONE_COLUMN_MESSAGE); 354 } 355 data = new double[subMatrix.length][nCols]; 356 for (int i = 0; i < data.length; ++i) { 357 if (subMatrix[i].length != nCols) { 358 throw MathRuntimeException.createIllegalArgumentException( 359 DIFFERENT_ROWS_LENGTHS_MESSAGE, nCols, subMatrix[i].length); 360 } 361 System.arraycopy(subMatrix[i], 0, data[i + row], column, nCols); 362 } 363 } else { 364 super.setSubMatrix(subMatrix, row, column); 365 } 366 367 } 368 369 /** {@inheritDoc} */ 370 @Override 371 public double getEntry(final int row, final int column) 372 throws MatrixIndexException { 373 try { 374 return data[row][column]; 375 } catch (ArrayIndexOutOfBoundsException e) { 376 throw new MatrixIndexException( 377 NO_ENTRY_MESSAGE, row, column, getRowDimension(), getColumnDimension()); 378 } 379 } 380 381 /** {@inheritDoc} */ 382 @Override 383 public void setEntry(final int row, final int column, final double value) 384 throws MatrixIndexException { 385 try { 386 data[row][column] = value; 387 } catch (ArrayIndexOutOfBoundsException e) { 388 throw new MatrixIndexException( 389 NO_ENTRY_MESSAGE, row, column, getRowDimension(), getColumnDimension()); 390 } 391 } 392 393 /** {@inheritDoc} */ 394 @Override 395 public void addToEntry(final int row, final int column, final double increment) 396 throws MatrixIndexException { 397 try { 398 data[row][column] += increment; 399 } catch (ArrayIndexOutOfBoundsException e) { 400 throw new MatrixIndexException( 401 NO_ENTRY_MESSAGE, row, column, getRowDimension(), getColumnDimension()); 402 } 403 } 404 405 /** {@inheritDoc} */ 406 @Override 407 public void multiplyEntry(final int row, final int column, final double factor) 408 throws MatrixIndexException { 409 try { 410 data[row][column] *= factor; 411 } catch (ArrayIndexOutOfBoundsException e) { 412 throw new MatrixIndexException( 413 NO_ENTRY_MESSAGE, row, column, getRowDimension(), getColumnDimension()); 414 } 415 } 416 417 /** {@inheritDoc} */ 418 @Override 419 public int getRowDimension() { 420 return (data == null) ? 0 : data.length; 421 } 422 423 /** {@inheritDoc} */ 424 @Override 425 public int getColumnDimension() { 426 return ((data == null) || (data[0] == null)) ? 0 : data[0].length; 427 } 428 429 /** {@inheritDoc} */ 430 @Override 431 public double[] operate(final double[] v) 432 throws IllegalArgumentException { 433 final int nRows = this.getRowDimension(); 434 final int nCols = this.getColumnDimension(); 435 if (v.length != nCols) { 436 throw MathRuntimeException.createIllegalArgumentException( 437 VECTOR_LENGTHS_MISMATCH, v.length, nCols); 438 } 439 final double[] out = new double[nRows]; 440 for (int row = 0; row < nRows; row++) { 441 final double[] dataRow = data[row]; 442 double sum = 0; 443 for (int i = 0; i < nCols; i++) { 444 sum += dataRow[i] * v[i]; 445 } 446 out[row] = sum; 447 } 448 return out; 449 } 450 451 /** {@inheritDoc} */ 452 @Override 453 public double[] preMultiply(final double[] v) 454 throws IllegalArgumentException { 455 456 final int nRows = getRowDimension(); 457 final int nCols = getColumnDimension(); 458 if (v.length != nRows) { 459 throw MathRuntimeException.createIllegalArgumentException( 460 VECTOR_LENGTHS_MISMATCH, v.length, nRows); 461 } 462 463 final double[] out = new double[nCols]; 464 for (int col = 0; col < nCols; ++col) { 465 double sum = 0; 466 for (int i = 0; i < nRows; ++i) { 467 sum += data[i][col] * v[i]; 468 } 469 out[col] = sum; 470 } 471 472 return out; 473 474 } 475 476 /** {@inheritDoc} */ 477 @Override 478 public double walkInRowOrder(final RealMatrixChangingVisitor visitor) 479 throws MatrixVisitorException { 480 final int rows = getRowDimension(); 481 final int columns = getColumnDimension(); 482 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 483 for (int i = 0; i < rows; ++i) { 484 final double[] rowI = data[i]; 485 for (int j = 0; j < columns; ++j) { 486 rowI[j] = visitor.visit(i, j, rowI[j]); 487 } 488 } 489 return visitor.end(); 490 } 491 492 /** {@inheritDoc} */ 493 @Override 494 public double walkInRowOrder(final RealMatrixPreservingVisitor visitor) 495 throws MatrixVisitorException { 496 final int rows = getRowDimension(); 497 final int columns = getColumnDimension(); 498 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 499 for (int i = 0; i < rows; ++i) { 500 final double[] rowI = data[i]; 501 for (int j = 0; j < columns; ++j) { 502 visitor.visit(i, j, rowI[j]); 503 } 504 } 505 return visitor.end(); 506 } 507 508 /** {@inheritDoc} */ 509 @Override 510 public double walkInRowOrder(final RealMatrixChangingVisitor visitor, 511 final int startRow, final int endRow, 512 final int startColumn, final int endColumn) 513 throws MatrixIndexException, MatrixVisitorException { 514 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 515 visitor.start(getRowDimension(), getColumnDimension(), 516 startRow, endRow, startColumn, endColumn); 517 for (int i = startRow; i <= endRow; ++i) { 518 final double[] rowI = data[i]; 519 for (int j = startColumn; j <= endColumn; ++j) { 520 rowI[j] = visitor.visit(i, j, rowI[j]); 521 } 522 } 523 return visitor.end(); 524 } 525 526 /** {@inheritDoc} */ 527 @Override 528 public double walkInRowOrder(final RealMatrixPreservingVisitor visitor, 529 final int startRow, final int endRow, 530 final int startColumn, final int endColumn) 531 throws MatrixIndexException, MatrixVisitorException { 532 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 533 visitor.start(getRowDimension(), getColumnDimension(), 534 startRow, endRow, startColumn, endColumn); 535 for (int i = startRow; i <= endRow; ++i) { 536 final double[] rowI = data[i]; 537 for (int j = startColumn; j <= endColumn; ++j) { 538 visitor.visit(i, j, rowI[j]); 539 } 540 } 541 return visitor.end(); 542 } 543 544 /** {@inheritDoc} */ 545 @Override 546 public double walkInColumnOrder(final RealMatrixChangingVisitor visitor) 547 throws MatrixVisitorException { 548 final int rows = getRowDimension(); 549 final int columns = getColumnDimension(); 550 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 551 for (int j = 0; j < columns; ++j) { 552 for (int i = 0; i < rows; ++i) { 553 final double[] rowI = data[i]; 554 rowI[j] = visitor.visit(i, j, rowI[j]); 555 } 556 } 557 return visitor.end(); 558 } 559 560 /** {@inheritDoc} */ 561 @Override 562 public double walkInColumnOrder(final RealMatrixPreservingVisitor visitor) 563 throws MatrixVisitorException { 564 final int rows = getRowDimension(); 565 final int columns = getColumnDimension(); 566 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 567 for (int j = 0; j < columns; ++j) { 568 for (int i = 0; i < rows; ++i) { 569 visitor.visit(i, j, data[i][j]); 570 } 571 } 572 return visitor.end(); 573 } 574 575 /** {@inheritDoc} */ 576 @Override 577 public double walkInColumnOrder(final RealMatrixChangingVisitor visitor, 578 final int startRow, final int endRow, 579 final int startColumn, final int endColumn) 580 throws MatrixIndexException, MatrixVisitorException { 581 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 582 visitor.start(getRowDimension(), getColumnDimension(), 583 startRow, endRow, startColumn, endColumn); 584 for (int j = startColumn; j <= endColumn; ++j) { 585 for (int i = startRow; i <= endRow; ++i) { 586 final double[] rowI = data[i]; 587 rowI[j] = visitor.visit(i, j, rowI[j]); 588 } 589 } 590 return visitor.end(); 591 } 592 593 /** {@inheritDoc} */ 594 @Override 595 public double walkInColumnOrder(final RealMatrixPreservingVisitor visitor, 596 final int startRow, final int endRow, 597 final int startColumn, final int endColumn) 598 throws MatrixIndexException, MatrixVisitorException { 599 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 600 visitor.start(getRowDimension(), getColumnDimension(), 601 startRow, endRow, startColumn, endColumn); 602 for (int j = startColumn; j <= endColumn; ++j) { 603 for (int i = startRow; i <= endRow; ++i) { 604 visitor.visit(i, j, data[i][j]); 605 } 606 } 607 return visitor.end(); 608 } 609 610 /** 611 * Returns a fresh copy of the underlying data array. 612 * 613 * @return a copy of the underlying data array. 614 */ 615 private double[][] copyOut() { 616 final int nRows = this.getRowDimension(); 617 final double[][] out = new double[nRows][this.getColumnDimension()]; 618 // can't copy 2-d array in one shot, otherwise get row references 619 for (int i = 0; i < nRows; i++) { 620 System.arraycopy(data[i], 0, out[i], 0, data[i].length); 621 } 622 return out; 623 } 624 625 /** 626 * Replaces data with a fresh copy of the input array. 627 * <p> 628 * Verifies that the input array is rectangular and non-empty.</p> 629 * 630 * @param in data to copy in 631 * @throws IllegalArgumentException if input array is empty or not 632 * rectangular 633 * @throws NullPointerException if input array is null 634 */ 635 private void copyIn(final double[][] in) { 636 setSubMatrix(in, 0, 0); 637 } 638 639 }