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: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $
051     * @deprecated as of 2.0 replaced by {@link Array2DRowRealMatrix}
052     */
053    @Deprecated
054    public class RealMatrixImpl extends AbstractRealMatrix implements Serializable {
055    
056        /** Serializable version identifier */
057        private static final long serialVersionUID = -1067294169172445528L;
058    
059        /** Entries of the matrix */
060        protected double data[][];
061    
062        /**
063         * Creates a matrix with no data
064         */
065        public RealMatrixImpl() {
066        }
067    
068        /**
069         * Create a new RealMatrix with the supplied row and column dimensions.
070         *
071         * @param rowDimension  the number of rows in the new matrix
072         * @param columnDimension  the number of columns in the new matrix
073         * @throws IllegalArgumentException if row or column dimension is not
074         *  positive
075         */
076        public RealMatrixImpl(final int rowDimension, final int columnDimension)
077            throws IllegalArgumentException {
078            super(rowDimension, columnDimension);
079            data = new double[rowDimension][columnDimension];
080        }
081    
082        /**
083         * Create a new RealMatrix using the input array as the underlying
084         * data array.
085         * <p>The input array is copied, not referenced. This constructor has
086         * the same effect as calling {@link #RealMatrixImpl(double[][], boolean)}
087         * with the second argument set to <code>true</code>.</p>
088         *
089         * @param d data for new matrix
090         * @throws IllegalArgumentException if <code>d</code> is not rectangular
091         *  (not all rows have the same length) or empty
092         * @throws NullPointerException if <code>d</code> is null
093         * @see #RealMatrixImpl(double[][], boolean)
094         */
095        public RealMatrixImpl(final double[][] d)
096            throws IllegalArgumentException, NullPointerException {
097            copyIn(d);
098        }
099    
100        /**
101         * Create a new RealMatrix using the input array as the underlying
102         * data array.
103         * <p>If an array is built specially in order to be embedded in a
104         * RealMatrix and not used directly, the <code>copyArray</code> may be
105         * set to <code>false</code. This will prevent the copying and improve
106         * performance as no new array will be built and no data will be copied.</p>
107         * @param d data for new matrix
108         * @param copyArray if true, the input array will be copied, otherwise
109         * it will be referenced
110         * @throws IllegalArgumentException if <code>d</code> is not rectangular
111         *  (not all rows have the same length) or empty
112         * @throws NullPointerException if <code>d</code> is null
113         * @see #RealMatrixImpl(double[][])
114         */
115        public RealMatrixImpl(final double[][] d, final boolean copyArray)
116            throws IllegalArgumentException, NullPointerException {
117            if (copyArray) {
118                copyIn(d);
119            } else {
120                if (d == null) {
121                    throw new NullPointerException();
122                }
123                final int nRows = d.length;
124                if (nRows == 0) {
125                    throw MathRuntimeException.createIllegalArgumentException("matrix must have at least one row");
126                }
127                final int nCols = d[0].length;
128                if (nCols == 0) {
129                    throw MathRuntimeException.createIllegalArgumentException("matrix must have at least one column");
130                }
131                for (int r = 1; r < nRows; r++) {
132                    if (d[r].length != nCols) {
133                        throw MathRuntimeException.createIllegalArgumentException(
134                                "some rows have length {0} while others have length {1}",
135                                nCols, d[r].length);
136                    }
137                }
138                data = d;
139            }
140        }
141    
142        /**
143         * Create a new (column) RealMatrix using <code>v</code> as the
144         * data for the unique column of the <code>v.length x 1</code> matrix
145         * created.
146         * <p>The input array is copied, not referenced.</p>
147         *
148         * @param v column vector holding data for new matrix
149         */
150        public RealMatrixImpl(final double[] v) {
151            final int nRows = v.length;
152            data = new double[nRows][1];
153            for (int row = 0; row < nRows; row++) {
154                data[row][0] = v[row];
155            }
156        }
157    
158        /** {@inheritDoc} */
159        @Override
160        public RealMatrix createMatrix(final int rowDimension, final int columnDimension)
161            throws IllegalArgumentException {
162            return new RealMatrixImpl(rowDimension, columnDimension);
163        }
164    
165        /** {@inheritDoc} */
166        @Override
167        public RealMatrix copy() {
168            return new RealMatrixImpl(copyOut(), false);
169        }
170    
171        /** {@inheritDoc} */
172        @Override
173        public RealMatrix add(final RealMatrix m)
174            throws IllegalArgumentException {
175            try {
176                return add((RealMatrixImpl) m);
177            } catch (ClassCastException cce) {
178                return super.add(m);
179            }
180        }
181    
182        /**
183         * Compute the sum of this and <code>m</code>.
184         *
185         * @param m    matrix to be added
186         * @return     this + m
187         * @throws  IllegalArgumentException if m is not the same size as this
188         */
189        public RealMatrixImpl add(final RealMatrixImpl m)
190            throws IllegalArgumentException {
191    
192            // safety check
193            MatrixUtils.checkAdditionCompatible(this, m);
194    
195            final int rowCount    = getRowDimension();
196            final int columnCount = getColumnDimension();
197            final double[][] outData = new double[rowCount][columnCount];
198            for (int row = 0; row < rowCount; row++) {
199                final double[] dataRow    = data[row];
200                final double[] mRow       = m.data[row];
201                final double[] outDataRow = outData[row];
202                for (int col = 0; col < columnCount; col++) {
203                    outDataRow[col] = dataRow[col] + mRow[col];
204                }
205            }
206    
207            return new RealMatrixImpl(outData, false);
208    
209        }
210    
211        /** {@inheritDoc} */
212        @Override
213        public RealMatrix subtract(final RealMatrix m)
214            throws IllegalArgumentException {
215            try {
216                return subtract((RealMatrixImpl) m);
217            } catch (ClassCastException cce) {
218                return super.subtract(m);
219            }
220        }
221    
222        /**
223         * Compute  this minus <code>m</code>.
224         *
225         * @param m    matrix to be subtracted
226         * @return     this + m
227         * @throws  IllegalArgumentException if m is not the same size as this
228         */
229        public RealMatrixImpl subtract(final RealMatrixImpl m)
230            throws IllegalArgumentException {
231    
232            // safety check
233            MatrixUtils.checkSubtractionCompatible(this, m);
234    
235            final int rowCount    = getRowDimension();
236            final int columnCount = getColumnDimension();
237            final double[][] outData = new double[rowCount][columnCount];
238            for (int row = 0; row < rowCount; row++) {
239                final double[] dataRow    = data[row];
240                final double[] mRow       = m.data[row];
241                final double[] outDataRow = outData[row];
242                for (int col = 0; col < columnCount; col++) {
243                    outDataRow[col] = dataRow[col] - mRow[col];
244                }
245            }
246    
247            return new RealMatrixImpl(outData, false);
248    
249        }
250    
251        /** {@inheritDoc} */
252        @Override
253        public RealMatrix multiply(final RealMatrix m)
254            throws IllegalArgumentException {
255            try {
256                return multiply((RealMatrixImpl) m);
257            } catch (ClassCastException cce) {
258                return super.multiply(m);
259            }
260        }
261    
262        /**
263         * Returns the result of postmultiplying this by <code>m</code>.
264         * @param m    matrix to postmultiply by
265         * @return     this*m
266         * @throws     IllegalArgumentException
267         *             if columnDimension(this) != rowDimension(m)
268         */
269        public RealMatrixImpl multiply(final RealMatrixImpl m)
270            throws IllegalArgumentException {
271    
272            // safety check
273            MatrixUtils.checkMultiplicationCompatible(this, m);
274    
275            final int nRows = this.getRowDimension();
276            final int nCols = m.getColumnDimension();
277            final int nSum = this.getColumnDimension();
278            final double[][] outData = new double[nRows][nCols];
279            for (int row = 0; row < nRows; row++) {
280                final double[] dataRow    = data[row];
281                final double[] outDataRow = outData[row];
282                for (int col = 0; col < nCols; col++) {
283                    double sum = 0;
284                    for (int i = 0; i < nSum; i++) {
285                        sum += dataRow[i] * m.data[i][col];
286                    }
287                    outDataRow[col] = sum;
288                }
289            }
290    
291            return new RealMatrixImpl(outData, false);
292    
293        }
294    
295        /** {@inheritDoc} */
296        @Override
297        public double[][] getData() {
298            return copyOut();
299        }
300    
301        /**
302         * Returns a reference to the underlying data array.
303         * <p>
304         * Does <strong>not</strong> make a fresh copy of the underlying data.</p>
305         *
306         * @return 2-dimensional array of entries
307         */
308        public double[][] getDataRef() {
309            return data;
310        }
311    
312        /** {@inheritDoc} */
313        @Override
314        public void setSubMatrix(final double[][] subMatrix, final int row, final int column)
315        throws MatrixIndexException {
316            if (data == null) {
317                if (row > 0) {
318                    throw MathRuntimeException.createIllegalStateException(
319                            "first {0} rows are not initialized yet",
320                            row);
321                }
322                if (column > 0) {
323                    throw MathRuntimeException.createIllegalStateException(
324                            "first {0} columns are not initialized yet",
325                            column);
326                }
327                final int nRows = subMatrix.length;
328                if (nRows == 0) {
329                    throw MathRuntimeException.createIllegalArgumentException("matrix must have at least one row");
330                }
331    
332                final int nCols = subMatrix[0].length;
333                if (nCols == 0) {
334                    throw MathRuntimeException.createIllegalArgumentException("matrix must have at least one column");
335                }
336                data = new double[subMatrix.length][nCols];
337                for (int i = 0; i < data.length; ++i) {
338                    if (subMatrix[i].length != nCols) {
339                        throw MathRuntimeException.createIllegalArgumentException(
340                                "some rows have length {0} while others have length {1}",
341                                nCols, subMatrix[i].length);
342                    }
343                    System.arraycopy(subMatrix[i], 0, data[i + row], column, nCols);
344                }
345            } else {
346                super.setSubMatrix(subMatrix, row, column);
347            }
348    
349        }
350    
351        /** {@inheritDoc} */
352        @Override
353        public double getEntry(final int row, final int column)
354            throws MatrixIndexException {
355            try {
356                return data[row][column];
357            } catch (ArrayIndexOutOfBoundsException e) {
358                throw new MatrixIndexException(
359                        "no entry at indices ({0}, {1}) in a {2}x{3} matrix",
360                        row, column, getRowDimension(), getColumnDimension());
361            }
362        }
363    
364        /** {@inheritDoc} */
365        @Override
366        public void setEntry(final int row, final int column, final double value)
367            throws MatrixIndexException {
368            try {
369                data[row][column] = value;
370            } catch (ArrayIndexOutOfBoundsException e) {
371                throw new MatrixIndexException(
372                        "no entry at indices ({0}, {1}) in a {2}x{3} matrix",
373                        row, column, getRowDimension(), getColumnDimension());
374            }
375        }
376    
377        /** {@inheritDoc} */
378        @Override
379        public void addToEntry(final int row, final int column, final double increment)
380            throws MatrixIndexException {
381            try {
382                data[row][column] += increment;
383            } catch (ArrayIndexOutOfBoundsException e) {
384                throw new MatrixIndexException(
385                        "no entry at indices ({0}, {1}) in a {2}x{3} matrix",
386                        row, column, getRowDimension(), getColumnDimension());
387            }
388        }
389    
390        /** {@inheritDoc} */
391        @Override
392        public void multiplyEntry(final int row, final int column, final double factor)
393            throws MatrixIndexException {
394            try {
395                data[row][column] *= factor;
396            } catch (ArrayIndexOutOfBoundsException e) {
397                throw new MatrixIndexException(
398                        "no entry at indices ({0}, {1}) in a {2}x{3} matrix",
399                        row, column, getRowDimension(), getColumnDimension());
400            }
401        }
402    
403        /** {@inheritDoc} */
404        @Override
405        public int getRowDimension() {
406            return (data == null) ? 0 : data.length;
407        }
408    
409        /** {@inheritDoc} */
410        @Override
411        public int getColumnDimension() {
412            return ((data == null) || (data[0] == null)) ? 0 : data[0].length;
413        }
414    
415        /** {@inheritDoc} */
416        @Override
417        public double[] operate(final double[] v)
418            throws IllegalArgumentException {
419            final int nRows = this.getRowDimension();
420            final int nCols = this.getColumnDimension();
421            if (v.length != nCols) {
422                throw MathRuntimeException.createIllegalArgumentException(
423                        "vector length mismatch: got {0} but expected {1}",
424                        v.length, nCols);
425            }
426            final double[] out = new double[nRows];
427            for (int row = 0; row < nRows; row++) {
428                final double[] dataRow = data[row];
429                double sum = 0;
430                for (int i = 0; i < nCols; i++) {
431                    sum += dataRow[i] * v[i];
432                }
433                out[row] = sum;
434            }
435            return out;
436        }
437    
438        /** {@inheritDoc} */
439        @Override
440        public double[] preMultiply(final double[] v)
441            throws IllegalArgumentException {
442    
443            final int nRows = getRowDimension();
444            final int nCols = getColumnDimension();
445            if (v.length != nRows) {
446                throw MathRuntimeException.createIllegalArgumentException(
447                        "vector length mismatch: got {0} but expected {1}",
448                        v.length, nRows);
449            }
450    
451            final double[] out = new double[nCols];
452            for (int col = 0; col < nCols; ++col) {
453                double sum = 0;
454                for (int i = 0; i < nRows; ++i) {
455                    sum += data[i][col] * v[i];
456                }
457                out[col] = sum;
458            }
459    
460            return out;
461    
462        }
463    
464        /** {@inheritDoc} */
465        @Override
466        public double walkInRowOrder(final RealMatrixChangingVisitor visitor)
467            throws MatrixVisitorException {
468            final int rows    = getRowDimension();
469            final int columns = getColumnDimension();
470            visitor.start(rows, columns, 0, rows - 1, 0, columns - 1);
471            for (int i = 0; i < rows; ++i) {
472                final double[] rowI = data[i];
473                for (int j = 0; j < columns; ++j) {
474                    rowI[j] = visitor.visit(i, j, rowI[j]);
475                }
476            }
477            return visitor.end();
478        }
479    
480        /** {@inheritDoc} */
481        @Override
482        public double walkInRowOrder(final RealMatrixPreservingVisitor visitor)
483            throws MatrixVisitorException {
484            final int rows    = getRowDimension();
485            final int columns = getColumnDimension();
486            visitor.start(rows, columns, 0, rows - 1, 0, columns - 1);
487            for (int i = 0; i < rows; ++i) {
488                final double[] rowI = data[i];
489                for (int j = 0; j < columns; ++j) {
490                    visitor.visit(i, j, rowI[j]);
491                }
492            }
493            return visitor.end();
494        }
495    
496        /** {@inheritDoc} */
497        @Override
498        public double walkInRowOrder(final RealMatrixChangingVisitor visitor,
499                                     final int startRow, final int endRow,
500                                     final int startColumn, final int endColumn)
501            throws MatrixIndexException, MatrixVisitorException {
502            MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn);
503            visitor.start(getRowDimension(), getColumnDimension(),
504                          startRow, endRow, startColumn, endColumn);
505            for (int i = startRow; i <= endRow; ++i) {
506                final double[] rowI = data[i];
507                for (int j = startColumn; j <= endColumn; ++j) {
508                    rowI[j] = visitor.visit(i, j, rowI[j]);
509                }
510            }
511            return visitor.end();
512        }
513    
514        /** {@inheritDoc} */
515        @Override
516        public double walkInRowOrder(final RealMatrixPreservingVisitor visitor,
517                                     final int startRow, final int endRow,
518                                     final int startColumn, final int endColumn)
519            throws MatrixIndexException, MatrixVisitorException {
520            MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn);
521            visitor.start(getRowDimension(), getColumnDimension(),
522                          startRow, endRow, startColumn, endColumn);
523            for (int i = startRow; i <= endRow; ++i) {
524                final double[] rowI = data[i];
525                for (int j = startColumn; j <= endColumn; ++j) {
526                    visitor.visit(i, j, rowI[j]);
527                }
528            }
529            return visitor.end();
530        }
531    
532        /** {@inheritDoc} */
533        @Override
534        public double walkInColumnOrder(final RealMatrixChangingVisitor visitor)
535            throws MatrixVisitorException {
536            final int rows    = getRowDimension();
537            final int columns = getColumnDimension();
538            visitor.start(rows, columns, 0, rows - 1, 0, columns - 1);
539            for (int j = 0; j < columns; ++j) {
540                for (int i = 0; i < rows; ++i) {
541                    final double[] rowI = data[i];
542                    rowI[j] = visitor.visit(i, j, rowI[j]);
543                }
544            }
545            return visitor.end();
546        }
547    
548        /** {@inheritDoc} */
549        @Override
550        public double walkInColumnOrder(final RealMatrixPreservingVisitor visitor)
551            throws MatrixVisitorException {
552            final int rows    = getRowDimension();
553            final int columns = getColumnDimension();
554            visitor.start(rows, columns, 0, rows - 1, 0, columns - 1);
555            for (int j = 0; j < columns; ++j) {
556                for (int i = 0; i < rows; ++i) {
557                    visitor.visit(i, j, data[i][j]);
558                }
559            }
560            return visitor.end();
561        }
562    
563        /** {@inheritDoc} */
564        @Override
565        public double walkInColumnOrder(final RealMatrixChangingVisitor visitor,
566                                        final int startRow, final int endRow,
567                                        final int startColumn, final int endColumn)
568            throws MatrixIndexException, MatrixVisitorException {
569            MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn);
570            visitor.start(getRowDimension(), getColumnDimension(),
571                          startRow, endRow, startColumn, endColumn);
572            for (int j = startColumn; j <= endColumn; ++j) {
573                for (int i = startRow; i <= endRow; ++i) {
574                    final double[] rowI = data[i];
575                    rowI[j] = visitor.visit(i, j, rowI[j]);
576                }
577            }
578            return visitor.end();
579        }
580    
581        /** {@inheritDoc} */
582        @Override
583        public double walkInColumnOrder(final RealMatrixPreservingVisitor visitor,
584                                        final int startRow, final int endRow,
585                                        final int startColumn, final int endColumn)
586            throws MatrixIndexException, MatrixVisitorException {
587            MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn);
588            visitor.start(getRowDimension(), getColumnDimension(),
589                          startRow, endRow, startColumn, endColumn);
590            for (int j = startColumn; j <= endColumn; ++j) {
591                for (int i = startRow; i <= endRow; ++i) {
592                    visitor.visit(i, j, data[i][j]);
593                }
594            }
595            return visitor.end();
596        }
597    
598        /**
599         * Returns a fresh copy of the underlying data array.
600         *
601         * @return a copy of the underlying data array.
602         */
603        private double[][] copyOut() {
604            final int nRows = this.getRowDimension();
605            final double[][] out = new double[nRows][this.getColumnDimension()];
606            // can't copy 2-d array in one shot, otherwise get row references
607            for (int i = 0; i < nRows; i++) {
608                System.arraycopy(data[i], 0, out[i], 0, data[i].length);
609            }
610            return out;
611        }
612    
613        /**
614         * Replaces data with a fresh copy of the input array.
615         * <p>
616         * Verifies that the input array is rectangular and non-empty.</p>
617         *
618         * @param in data to copy in
619         * @throws IllegalArgumentException if input array is empty or not
620         *    rectangular
621         * @throws NullPointerException if input array is null
622         */
623        private void copyIn(final double[][] in) {
624            setSubMatrix(in, 0, 0);
625        }
626    
627    }