1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package org.apache.commons.math.linear; 19 20import java.io.Serializable; 21 22import org.apache.commons.math.MathRuntimeException; 23import org.apache.commons.math.linear.MatrixVisitorException; 24import org.apache.commons.math.exception.util.LocalizedFormats; 25 26/** 27 * Implementation of RealMatrix using a double[][] array to store entries and 28 * <a href="http://www.math.gatech.edu/~bourbaki/math2601/Web-notes/2num.pdf"> 29 * LU decomposition</a> to support linear system 30 * solution and inverse. 31 * <p> 32 * The LU decomposition is performed as needed, to support the following operations: <ul> 33 * <li>solve</li> 34 * <li>isSingular</li> 35 * <li>getDeterminant</li> 36 * <li>inverse</li> </ul></p> 37 * <p> 38 * <strong>Usage notes</strong>:<br> 39 * <ul><li> 40 * The LU decomposition is cached and reused on subsequent calls. 41 * If data are modified via references to the underlying array obtained using 42 * <code>getDataRef()</code>, then the stored LU decomposition will not be 43 * discarded. In this case, you need to explicitly invoke 44 * <code>LUDecompose()</code> to recompute the decomposition 45 * before using any of the methods above.</li> 46 * <li> 47 * As specified in the {@link RealMatrix} interface, matrix element indexing 48 * is 0-based -- e.g., <code>getEntry(0, 0)</code> 49 * returns the element in the first row, first column of the matrix.</li></ul> 50 * </p> 51 * 52 * @version $Revision: 1073158 $ $Date: 2011-02-21 22:46:52 +0100 (lun. 21 févr. 2011) $ 53 */ 54public class Array2DRowRealMatrix extends AbstractRealMatrix implements Serializable { 55 56 /** Serializable version identifier */ 57 private static final long serialVersionUID = -1067294169172445528L; 58 59 /** Entries of the matrix */ 60 protected double data[][]; 61 62 /** 63 * Creates a matrix with no data 64 */ 65 public Array2DRowRealMatrix() { 66 } 67 68 /** 69 * Create a new RealMatrix with the supplied row and column dimensions. 70 * 71 * @param rowDimension the number of rows in the new matrix 72 * @param columnDimension the number of columns in the new matrix 73 * @throws IllegalArgumentException if row or column dimension is not 74 * positive 75 */ 76 public Array2DRowRealMatrix(final int rowDimension, final int columnDimension) 77 throws IllegalArgumentException { 78 super(rowDimension, columnDimension); 79 data = new double[rowDimension][columnDimension]; 80 } 81 82 /** 83 * Create a new RealMatrix using the input array as the underlying 84 * data array. 85 * <p>The input array is copied, not referenced. This constructor has 86 * the same effect as calling {@link #Array2DRowRealMatrix(double[][], boolean)} 87 * with the second argument set to <code>true</code>.</p> 88 * 89 * @param d data for new matrix 90 * @throws IllegalArgumentException if <code>d</code> is not rectangular 91 * (not all rows have the same length) or empty 92 * @throws NullPointerException if <code>d</code> is null 93 * @see #Array2DRowRealMatrix(double[][], boolean) 94 */ 95 public Array2DRowRealMatrix(final double[][] d) 96 throws IllegalArgumentException, NullPointerException { 97 copyIn(d); 98 } 99 100 /** 101 * Create a new RealMatrix using the input array as the underlying 102 * data array. 103 * <p>If an array is built specially in order to be embedded in a 104 * RealMatrix and not used directly, the <code>copyArray</code> may be 105 * set to <code>false</code. This will prevent the copying and improve 106 * performance as no new array will be built and no data will be copied.</p> 107 * @param d data for new matrix 108 * @param copyArray if true, the input array will be copied, otherwise 109 * it will be referenced 110 * @throws IllegalArgumentException if <code>d</code> is not rectangular 111 * (not all rows have the same length) or empty 112 * @throws NullPointerException if <code>d</code> is null 113 * @see #Array2DRowRealMatrix(double[][]) 114 */ 115 public Array2DRowRealMatrix(final double[][] d, final boolean copyArray) 116 throws IllegalArgumentException, NullPointerException { 117 if (copyArray) { 118 copyIn(d); 119 } else { 120 if (d == null) { 121 throw new NullPointerException(); 122 } 123 final int nRows = d.length; 124 if (nRows == 0) { 125 throw MathRuntimeException.createIllegalArgumentException( 126 LocalizedFormats.AT_LEAST_ONE_ROW); 127 } 128 final int nCols = d[0].length; 129 if (nCols == 0) { 130 throw MathRuntimeException.createIllegalArgumentException( 131 LocalizedFormats.AT_LEAST_ONE_COLUMN); 132 } 133 for (int r = 1; r < nRows; r++) { 134 if (d[r].length != nCols) { 135 throw MathRuntimeException.createIllegalArgumentException( 136 LocalizedFormats.DIFFERENT_ROWS_LENGTHS, nCols, d[r].length); 137 } 138 } 139 data = d; 140 } 141 } 142 143 /** 144 * Create a new (column) RealMatrix using <code>v</code> as the 145 * data for the unique column of the <code>v.length x 1</code> matrix 146 * created. 147 * <p>The input array is copied, not referenced.</p> 148 * 149 * @param v column vector holding data for new matrix 150 */ 151 public Array2DRowRealMatrix(final double[] v) { 152 final int nRows = v.length; 153 data = new double[nRows][1]; 154 for (int row = 0; row < nRows; row++) { 155 data[row][0] = v[row]; 156 } 157 } 158 159 /** {@inheritDoc} */ 160 @Override 161 public RealMatrix createMatrix(final int rowDimension, final int columnDimension) 162 throws IllegalArgumentException { 163 return new Array2DRowRealMatrix(rowDimension, columnDimension); 164 } 165 166 /** {@inheritDoc} */ 167 @Override 168 public RealMatrix copy() { 169 return new Array2DRowRealMatrix(copyOut(), false); 170 } 171 172 /** {@inheritDoc} */ 173 @Override 174 public RealMatrix add(final RealMatrix m) 175 throws IllegalArgumentException { 176 try { 177 return add((Array2DRowRealMatrix) m); 178 } catch (ClassCastException cce) { 179 return super.add(m); 180 } 181 } 182 183 /** 184 * Compute the sum of this and <code>m</code>. 185 * 186 * @param m matrix to be added 187 * @return this + m 188 * @throws IllegalArgumentException if m is not the same size as this 189 */ 190 public Array2DRowRealMatrix add(final Array2DRowRealMatrix m) 191 throws IllegalArgumentException { 192 193 // safety check 194 MatrixUtils.checkAdditionCompatible(this, m); 195 196 final int rowCount = getRowDimension(); 197 final int columnCount = getColumnDimension(); 198 final double[][] outData = new double[rowCount][columnCount]; 199 for (int row = 0; row < rowCount; row++) { 200 final double[] dataRow = data[row]; 201 final double[] mRow = m.data[row]; 202 final double[] outDataRow = outData[row]; 203 for (int col = 0; col < columnCount; col++) { 204 outDataRow[col] = dataRow[col] + mRow[col]; 205 } 206 } 207 208 return new Array2DRowRealMatrix(outData, false); 209 210 } 211 212 /** {@inheritDoc} */ 213 @Override 214 public RealMatrix subtract(final RealMatrix m) 215 throws IllegalArgumentException { 216 try { 217 return subtract((Array2DRowRealMatrix) m); 218 } catch (ClassCastException cce) { 219 return super.subtract(m); 220 } 221 } 222 223 /** 224 * Compute this minus <code>m</code>. 225 * 226 * @param m matrix to be subtracted 227 * @return this + m 228 * @throws IllegalArgumentException if m is not the same size as this 229 */ 230 public Array2DRowRealMatrix subtract(final Array2DRowRealMatrix m) 231 throws IllegalArgumentException { 232 233 // safety check 234 MatrixUtils.checkSubtractionCompatible(this, m); 235 236 final int rowCount = getRowDimension(); 237 final int columnCount = getColumnDimension(); 238 final double[][] outData = new double[rowCount][columnCount]; 239 for (int row = 0; row < rowCount; row++) { 240 final double[] dataRow = data[row]; 241 final double[] mRow = m.data[row]; 242 final double[] outDataRow = outData[row]; 243 for (int col = 0; col < columnCount; col++) { 244 outDataRow[col] = dataRow[col] - mRow[col]; 245 } 246 } 247 248 return new Array2DRowRealMatrix(outData, false); 249 250 } 251 252 /** {@inheritDoc} */ 253 @Override 254 public RealMatrix multiply(final RealMatrix m) 255 throws IllegalArgumentException { 256 try { 257 return multiply((Array2DRowRealMatrix) m); 258 } catch (ClassCastException cce) { 259 return super.multiply(m); 260 } 261 } 262 263 /** 264 * Returns the result of postmultiplying this by <code>m</code>. 265 * @param m matrix to postmultiply by 266 * @return this*m 267 * @throws IllegalArgumentException 268 * if columnDimension(this) != rowDimension(m) 269 */ 270 public Array2DRowRealMatrix multiply(final Array2DRowRealMatrix m) 271 throws IllegalArgumentException { 272 273 // safety check 274 MatrixUtils.checkMultiplicationCompatible(this, m); 275 276 final int nRows = this.getRowDimension(); 277 final int nCols = m.getColumnDimension(); 278 final int nSum = this.getColumnDimension(); 279 final double[][] outData = new double[nRows][nCols]; 280 for (int row = 0; row < nRows; row++) { 281 final double[] dataRow = data[row]; 282 final double[] outDataRow = outData[row]; 283 for (int col = 0; col < nCols; col++) { 284 double sum = 0; 285 for (int i = 0; i < nSum; i++) { 286 sum += dataRow[i] * m.data[i][col]; 287 } 288 outDataRow[col] = sum; 289 } 290 } 291 292 return new Array2DRowRealMatrix(outData, false); 293 294 } 295 296 /** {@inheritDoc} */ 297 @Override 298 public double[][] getData() { 299 return copyOut(); 300 } 301 302 /** 303 * Returns a reference to the underlying data array. 304 * <p> 305 * Does <strong>not</strong> make a fresh copy of the underlying data.</p> 306 * 307 * @return 2-dimensional array of entries 308 */ 309 public double[][] getDataRef() { 310 return data; 311 } 312 313 /** {@inheritDoc} */ 314 @Override 315 public void setSubMatrix(final double[][] subMatrix, final int row, final int column) 316 throws MatrixIndexException { 317 if (data == null) { 318 if (row > 0) { 319 throw MathRuntimeException.createIllegalStateException( 320 LocalizedFormats.FIRST_ROWS_NOT_INITIALIZED_YET, row); 321 } 322 if (column > 0) { 323 throw MathRuntimeException.createIllegalStateException( 324 LocalizedFormats.FIRST_COLUMNS_NOT_INITIALIZED_YET, column); 325 } 326 final int nRows = subMatrix.length; 327 if (nRows == 0) { 328 throw MathRuntimeException.createIllegalArgumentException( 329 LocalizedFormats.AT_LEAST_ONE_ROW); 330 } 331 332 final int nCols = subMatrix[0].length; 333 if (nCols == 0) { 334 throw MathRuntimeException.createIllegalArgumentException( 335 LocalizedFormats.AT_LEAST_ONE_COLUMN); 336 } 337 data = new double[subMatrix.length][nCols]; 338 for (int i = 0; i < data.length; ++i) { 339 if (subMatrix[i].length != nCols) { 340 throw MathRuntimeException.createIllegalArgumentException( 341 LocalizedFormats.DIFFERENT_ROWS_LENGTHS, nCols, subMatrix[i].length); 342 } 343 System.arraycopy(subMatrix[i], 0, data[i + row], column, nCols); 344 } 345 } else { 346 super.setSubMatrix(subMatrix, row, column); 347 } 348 349 } 350 351 /** {@inheritDoc} */ 352 @Override 353 public double getEntry(final int row, final int column) 354 throws MatrixIndexException { 355 try { 356 return data[row][column]; 357 } catch (ArrayIndexOutOfBoundsException e) { 358 throw new MatrixIndexException( 359 LocalizedFormats.NO_SUCH_MATRIX_ENTRY, row, column, getRowDimension(), getColumnDimension()); 360 } 361 } 362 363 /** {@inheritDoc} */ 364 @Override 365 public void setEntry(final int row, final int column, final double value) 366 throws MatrixIndexException { 367 try { 368 data[row][column] = value; 369 } catch (ArrayIndexOutOfBoundsException e) { 370 throw new MatrixIndexException( 371 LocalizedFormats.NO_SUCH_MATRIX_ENTRY, 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 LocalizedFormats.NO_SUCH_MATRIX_ENTRY, row, column, getRowDimension(), getColumnDimension()); 384 } 385 } 386 387 /** {@inheritDoc} */ 388 @Override 389 public void multiplyEntry(final int row, final int column, final double factor) 390 throws MatrixIndexException { 391 try { 392 data[row][column] *= factor; 393 } catch (ArrayIndexOutOfBoundsException e) { 394 throw new MatrixIndexException( 395 LocalizedFormats.NO_SUCH_MATRIX_ENTRY, row, column, getRowDimension(), getColumnDimension()); 396 } 397 } 398 399 /** {@inheritDoc} */ 400 @Override 401 public int getRowDimension() { 402 return (data == null) ? 0 : data.length; 403 } 404 405 /** {@inheritDoc} */ 406 @Override 407 public int getColumnDimension() { 408 return ((data == null) || (data[0] == null)) ? 0 : data[0].length; 409 } 410 411 /** {@inheritDoc} */ 412 @Override 413 public double[] operate(final double[] v) 414 throws IllegalArgumentException { 415 final int nRows = this.getRowDimension(); 416 final int nCols = this.getColumnDimension(); 417 if (v.length != nCols) { 418 throw MathRuntimeException.createIllegalArgumentException( 419 LocalizedFormats.VECTOR_LENGTH_MISMATCH, v.length, nCols); 420 } 421 final double[] out = new double[nRows]; 422 for (int row = 0; row < nRows; row++) { 423 final double[] dataRow = data[row]; 424 double sum = 0; 425 for (int i = 0; i < nCols; i++) { 426 sum += dataRow[i] * v[i]; 427 } 428 out[row] = sum; 429 } 430 return out; 431 } 432 433 /** {@inheritDoc} */ 434 @Override 435 public double[] preMultiply(final double[] v) 436 throws IllegalArgumentException { 437 438 final int nRows = getRowDimension(); 439 final int nCols = getColumnDimension(); 440 if (v.length != nRows) { 441 throw MathRuntimeException.createIllegalArgumentException( 442 LocalizedFormats.VECTOR_LENGTH_MISMATCH, v.length, nRows); 443 } 444 445 final double[] out = new double[nCols]; 446 for (int col = 0; col < nCols; ++col) { 447 double sum = 0; 448 for (int i = 0; i < nRows; ++i) { 449 sum += data[i][col] * v[i]; 450 } 451 out[col] = sum; 452 } 453 454 return out; 455 456 } 457 458 /** {@inheritDoc} */ 459 @Override 460 public double walkInRowOrder(final RealMatrixChangingVisitor visitor) 461 throws MatrixVisitorException { 462 final int rows = getRowDimension(); 463 final int columns = getColumnDimension(); 464 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 465 for (int i = 0; i < rows; ++i) { 466 final double[] rowI = data[i]; 467 for (int j = 0; j < columns; ++j) { 468 rowI[j] = visitor.visit(i, j, rowI[j]); 469 } 470 } 471 return visitor.end(); 472 } 473 474 /** {@inheritDoc} */ 475 @Override 476 public double walkInRowOrder(final RealMatrixPreservingVisitor visitor) 477 throws MatrixVisitorException { 478 final int rows = getRowDimension(); 479 final int columns = getColumnDimension(); 480 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 481 for (int i = 0; i < rows; ++i) { 482 final double[] rowI = data[i]; 483 for (int j = 0; j < columns; ++j) { 484 visitor.visit(i, j, rowI[j]); 485 } 486 } 487 return visitor.end(); 488 } 489 490 /** {@inheritDoc} */ 491 @Override 492 public double walkInRowOrder(final RealMatrixChangingVisitor visitor, 493 final int startRow, final int endRow, 494 final int startColumn, final int endColumn) 495 throws MatrixIndexException, MatrixVisitorException { 496 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 497 visitor.start(getRowDimension(), getColumnDimension(), 498 startRow, endRow, startColumn, endColumn); 499 for (int i = startRow; i <= endRow; ++i) { 500 final double[] rowI = data[i]; 501 for (int j = startColumn; j <= endColumn; ++j) { 502 rowI[j] = visitor.visit(i, j, rowI[j]); 503 } 504 } 505 return visitor.end(); 506 } 507 508 /** {@inheritDoc} */ 509 @Override 510 public double walkInRowOrder(final RealMatrixPreservingVisitor 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 visitor.visit(i, j, rowI[j]); 521 } 522 } 523 return visitor.end(); 524 } 525 526 /** {@inheritDoc} */ 527 @Override 528 public double walkInColumnOrder(final RealMatrixChangingVisitor visitor) 529 throws MatrixVisitorException { 530 final int rows = getRowDimension(); 531 final int columns = getColumnDimension(); 532 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 533 for (int j = 0; j < columns; ++j) { 534 for (int i = 0; i < rows; ++i) { 535 final double[] rowI = data[i]; 536 rowI[j] = visitor.visit(i, j, rowI[j]); 537 } 538 } 539 return visitor.end(); 540 } 541 542 /** {@inheritDoc} */ 543 @Override 544 public double walkInColumnOrder(final RealMatrixPreservingVisitor visitor) 545 throws MatrixVisitorException { 546 final int rows = getRowDimension(); 547 final int columns = getColumnDimension(); 548 visitor.start(rows, columns, 0, rows - 1, 0, columns - 1); 549 for (int j = 0; j < columns; ++j) { 550 for (int i = 0; i < rows; ++i) { 551 visitor.visit(i, j, data[i][j]); 552 } 553 } 554 return visitor.end(); 555 } 556 557 /** {@inheritDoc} */ 558 @Override 559 public double walkInColumnOrder(final RealMatrixChangingVisitor visitor, 560 final int startRow, final int endRow, 561 final int startColumn, final int endColumn) 562 throws MatrixIndexException, MatrixVisitorException { 563 MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn); 564 visitor.start(getRowDimension(), getColumnDimension(), 565 startRow, endRow, startColumn, endColumn); 566 for (int j = startColumn; j <= endColumn; ++j) { 567 for (int i = startRow; i <= endRow; ++i) { 568 final double[] rowI = data[i]; 569 rowI[j] = visitor.visit(i, j, rowI[j]); 570 } 571 } 572 return visitor.end(); 573 } 574 575 /** {@inheritDoc} */ 576 @Override 577 public double walkInColumnOrder(final RealMatrixPreservingVisitor 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 visitor.visit(i, j, data[i][j]); 587 } 588 } 589 return visitor.end(); 590 } 591 592 /** 593 * Returns a fresh copy of the underlying data array. 594 * 595 * @return a copy of the underlying data array. 596 */ 597 private double[][] copyOut() { 598 final int nRows = this.getRowDimension(); 599 final double[][] out = new double[nRows][this.getColumnDimension()]; 600 // can't copy 2-d array in one shot, otherwise get row references 601 for (int i = 0; i < nRows; i++) { 602 System.arraycopy(data[i], 0, out[i], 0, data[i].length); 603 } 604 return out; 605 } 606 607 /** 608 * Replaces data with a fresh copy of the input array. 609 * <p> 610 * Verifies that the input array is rectangular and non-empty.</p> 611 * 612 * @param in data to copy in 613 * @throws IllegalArgumentException if input array is empty or not 614 * rectangular 615 * @throws NullPointerException if input array is null 616 */ 617 private void copyIn(final double[][] in) { 618 setSubMatrix(in, 0, 0); 619 } 620 621} 622