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    }