View Javadoc

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  
18  package org.apache.commons.math.linear;
19  
20  import java.io.Serializable;
21  
22  import org.apache.commons.math.MathRuntimeException;
23  
24  /**
25   * Implementation of RealMatrix using a double[][] array to store entries and
26   * <a href="http://www.math.gatech.edu/~bourbaki/math2601/Web-notes/2num.pdf">
27   * LU decomposition</a> to support linear system
28   * solution and inverse.
29   * <p>
30   * The LU decomposition is performed as needed, to support the following operations: <ul>
31   * <li>solve</li>
32   * <li>isSingular</li>
33   * <li>getDeterminant</li>
34   * <li>inverse</li> </ul></p>
35   * <p>
36   * <strong>Usage notes</strong>:<br>
37   * <ul><li>
38   * The LU decomposition is cached and reused on subsequent calls.   
39   * If data are modified via references to the underlying array obtained using
40   * <code>getDataRef()</code>, then the stored LU decomposition will not be
41   * discarded.  In this case, you need to explicitly invoke 
42   * <code>LUDecompose()</code> to recompute the decomposition
43   * before using any of the methods above.</li>
44   * <li>
45   * As specified in the {@link RealMatrix} interface, matrix element indexing
46   * is 0-based -- e.g., <code>getEntry(0, 0)</code>
47   * returns the element in the first row, first column of the matrix.</li></ul>
48   * </p>
49   *
50   * @version $Revision: 783702 $ $Date: 2009-06-11 04:54:02 -0400 (Thu, 11 Jun 2009) $
51   */
52  public class Array2DRowRealMatrix extends AbstractRealMatrix implements Serializable {
53      
54      /** Serializable version identifier */
55      private static final long serialVersionUID = -1067294169172445528L;
56  
57      /** Entries of the matrix */
58      protected double data[][];
59  
60      /**
61       * Creates a matrix with no data
62       */
63      public Array2DRowRealMatrix() {
64      }
65  
66      /**
67       * Create a new RealMatrix with the supplied row and column dimensions.
68       *
69       * @param rowDimension  the number of rows in the new matrix
70       * @param columnDimension  the number of columns in the new matrix
71       * @throws IllegalArgumentException if row or column dimension is not
72       *  positive
73       */
74      public Array2DRowRealMatrix(final int rowDimension, final int columnDimension)
75          throws IllegalArgumentException {
76          super(rowDimension, columnDimension);
77          data = new double[rowDimension][columnDimension];
78      }
79  
80      /**
81       * Create a new RealMatrix using the input array as the underlying
82       * data array.
83       * <p>The input array is copied, not referenced. This constructor has
84       * the same effect as calling {@link #Array2DRowRealMatrix(double[][], boolean)}
85       * with the second argument set to <code>true</code>.</p>
86       *
87       * @param d data for new matrix
88       * @throws IllegalArgumentException if <code>d</code> is not rectangular
89       *  (not all rows have the same length) or empty
90       * @throws NullPointerException if <code>d</code> is null
91       * @see #Array2DRowRealMatrix(double[][], boolean)
92       */
93      public Array2DRowRealMatrix(final double[][] d)
94          throws IllegalArgumentException, NullPointerException {
95          copyIn(d);
96      }
97  
98      /**
99       * 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 }