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: 783702 $ $Date: 2009-06-11 04:54:02 -0400 (Thu, 11 Jun 2009) $
051     */
052    public class Array2DRowRealMatrix extends AbstractRealMatrix implements Serializable {
053        
054        /** Serializable version identifier */
055        private static final long serialVersionUID = -1067294169172445528L;
056    
057        /** Entries of the matrix */
058        protected double data[][];
059    
060        /**
061         * Creates a matrix with no data
062         */
063        public Array2DRowRealMatrix() {
064        }
065    
066        /**
067         * Create a new RealMatrix with the supplied row and column dimensions.
068         *
069         * @param rowDimension  the number of rows in the new matrix
070         * @param columnDimension  the number of columns in the new matrix
071         * @throws IllegalArgumentException if row or column dimension is not
072         *  positive
073         */
074        public Array2DRowRealMatrix(final int rowDimension, final int columnDimension)
075            throws IllegalArgumentException {
076            super(rowDimension, columnDimension);
077            data = new double[rowDimension][columnDimension];
078        }
079    
080        /**
081         * Create a new RealMatrix using the input array as the underlying
082         * data array.
083         * <p>The input array is copied, not referenced. This constructor has
084         * the same effect as calling {@link #Array2DRowRealMatrix(double[][], boolean)}
085         * with the second argument set to <code>true</code>.</p>
086         *
087         * @param d data for new matrix
088         * @throws IllegalArgumentException if <code>d</code> is not rectangular
089         *  (not all rows have the same length) or empty
090         * @throws NullPointerException if <code>d</code> is null
091         * @see #Array2DRowRealMatrix(double[][], boolean)
092         */
093        public Array2DRowRealMatrix(final double[][] d)
094            throws IllegalArgumentException, NullPointerException {
095            copyIn(d);
096        }
097    
098        /**
099         * 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    }