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 }