    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    import org.apache.commons.math.linear.MatrixVisitorException;
    024    import org.apache.commons.math.exception.util.LocalizedFormats;
    025
    026    /**
    027     * Implementation of RealMatrix using a double[][] array to store entries and
    028     * <a href="http://www.math.gatech.edu/~bourbaki/math2601/Web-notes/2num.pdf">
    029     * LU decomposition</a> to support linear system
    030     * solution and inverse.
    031     * <p>
    032     * The LU decomposition is performed as needed, to support the following operations: <ul>
    033     * <li>solve</li>
    034     * <li>isSingular</li>
    035     * <li>getDeterminant</li>
    036     * <li>inverse</li> </ul></p>
    037     * <p>
    038     * <strong>Usage notes</strong>:<br>
    039     * <ul><li>
    040     * The LU decomposition is cached and reused on subsequent calls.
    041     * If data are modified via references to the underlying array obtained using
    042     * <code>getDataRef()</code>, then the stored LU decomposition will not be
    043     * discarded.  In this case, you need to explicitly invoke
    044     * <code>LUDecompose()</code> to recompute the decomposition
    045     * before using any of the methods above.</li>
    046     * <li>
    047     * As specified in the {@link RealMatrix} interface, matrix element indexing
    048     * is 0-based -- e.g., <code>getEntry(0, 0)</code>
    049     * returns the element in the first row, first column of the matrix.</li></ul>
    050     * </p>
    051     *
    052     * @version $Revision: 1073158 $ $Date: 2011-02-21 22:46:52 +0100 (lun. 21 f??vr. 2011) $
    053     */
    054    public class Array2DRowRealMatrix 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 Array2DRowRealMatrix() {
    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 Array2DRowRealMatrix(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 #Array2DRowRealMatrix(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 #Array2DRowRealMatrix(double[][], boolean)
    094         */
    095        public Array2DRowRealMatrix(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 #Array2DRowRealMatrix(double[][])
    114         */
    115        public Array2DRowRealMatrix(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(
    126                          LocalizedFormats.AT_LEAST_ONE_ROW);
    127                }
    128                final int nCols = d[0].length;
    129                if (nCols == 0) {
    130                    throw MathRuntimeException.createIllegalArgumentException(
    131                          LocalizedFormats.AT_LEAST_ONE_COLUMN);
    132                }
    133                for (int r = 1; r < nRows; r++) {
    134                    if (d[r].length != nCols) {
    135                        throw MathRuntimeException.createIllegalArgumentException(
    136                              LocalizedFormats.DIFFERENT_ROWS_LENGTHS, nCols, d[r].length);
    137                    }
    138                }
    139                data = d;
    140            }
    141        }
    142
    143        /**
    144         * Create a new (column) RealMatrix using <code>v</code> as the
    145         * data for the unique column of the <code>v.length x 1</code> matrix
    146         * created.
    147         * <p>The input array is copied, not referenced.</p>
    148         *
    149         * @param v column vector holding data for new matrix
    150         */
    151        public Array2DRowRealMatrix(final double[] v) {
    152            final int nRows = v.length;
    153            data = new double[nRows][1];
    154            for (int row = 0; row < nRows; row++) {
    155                data[row][0] = v[row];
    156            }
    157        }
    158
    159        /** {@inheritDoc} */
    160        @Override
    161        public RealMatrix createMatrix(final int rowDimension, final int columnDimension)
    162            throws IllegalArgumentException {
    163            return new Array2DRowRealMatrix(rowDimension, columnDimension);
    164        }
    165
    166        /** {@inheritDoc} */
    167        @Override
    168        public RealMatrix copy() {
    169            return new Array2DRowRealMatrix(copyOut(), false);
    170        }
    171
    172        /** {@inheritDoc} */
    173        @Override
    174        public RealMatrix add(final RealMatrix m)
    175            throws IllegalArgumentException {
    176            try {
    177                return add((Array2DRowRealMatrix) m);
    178            } catch (ClassCastException cce) {
    179                return super.add(m);
    180            }
    181        }
    182
    183        /**
    184         * Compute the sum of this and <code>m</code>.
    185         *
    186         * @param m    matrix to be added
    187         * @return     this + m
    188         * @throws  IllegalArgumentException if m is not the same size as this
    189         */
    190        public Array2DRowRealMatrix add(final Array2DRowRealMatrix m)
    191            throws IllegalArgumentException {
    192
    193            // safety check
    194            MatrixUtils.checkAdditionCompatible(this, m);
    195
    196            final int rowCount    = getRowDimension();
    197            final int columnCount = getColumnDimension();
    198            final double[][] outData = new double[rowCount][columnCount];
    199            for (int row = 0; row < rowCount; row++) {
    200                final double[] dataRow    = data[row];
    201                final double[] mRow       = m.data[row];
    202                final double[] outDataRow = outData[row];
    203                for (int col = 0; col < columnCount; col++) {
    204                    outDataRow[col] = dataRow[col] + mRow[col];
    205                }
    206            }
    207
    208            return new Array2DRowRealMatrix(outData, false);
    209
    210        }
    211
    212        /** {@inheritDoc} */
    213        @Override
    214        public RealMatrix subtract(final RealMatrix m)
    215            throws IllegalArgumentException {
    216            try {
    217                return subtract((Array2DRowRealMatrix) m);
    218            } catch (ClassCastException cce) {
    219                return super.subtract(m);
    220            }
    221        }
    222
    223        /**
    224         * Compute  this minus <code>m</code>.
    225         *
    226         * @param m    matrix to be subtracted
    227         * @return     this + m
    228         * @throws  IllegalArgumentException if m is not the same size as this
    229         */
    230        public Array2DRowRealMatrix subtract(final Array2DRowRealMatrix m)
    231            throws IllegalArgumentException {
    232
    233            // safety check
    234            MatrixUtils.checkSubtractionCompatible(this, m);
    235
    236            final int rowCount    = getRowDimension();
    237            final int columnCount = getColumnDimension();
    238            final double[][] outData = new double[rowCount][columnCount];
    239            for (int row = 0; row < rowCount; row++) {
    240                final double[] dataRow    = data[row];
    241                final double[] mRow       = m.data[row];
    242                final double[] outDataRow = outData[row];
    243                for (int col = 0; col < columnCount; col++) {
    244                    outDataRow[col] = dataRow[col] - mRow[col];
    245                }
    246            }
    247
    248            return new Array2DRowRealMatrix(outData, false);
    249
    250        }
    251
    252        /** {@inheritDoc} */
    253        @Override
    254        public RealMatrix multiply(final RealMatrix m)
    255            throws IllegalArgumentException {
    256            try {
    257                return multiply((Array2DRowRealMatrix) m);
    258            } catch (ClassCastException cce) {
    259                return super.multiply(m);
    260            }
    261        }
    262
    263        /**
    264         * Returns the result of postmultiplying this by <code>m</code>.
    265         * @param m    matrix to postmultiply by
    266         * @return     this*m
    267         * @throws     IllegalArgumentException
    268         *             if columnDimension(this) != rowDimension(m)
    269         */
    270        public Array2DRowRealMatrix multiply(final Array2DRowRealMatrix m)
    271            throws IllegalArgumentException {
    272
    273            // safety check
    274            MatrixUtils.checkMultiplicationCompatible(this, m);
    275
    276            final int nRows = this.getRowDimension();
    277            final int nCols = m.getColumnDimension();
    278            final int nSum = this.getColumnDimension();
    279            final double[][] outData = new double[nRows][nCols];
    280            for (int row = 0; row < nRows; row++) {
    281                final double[] dataRow    = data[row];
    282                final double[] outDataRow = outData[row];
    283                for (int col = 0; col < nCols; col++) {
    284                    double sum = 0;
    285                    for (int i = 0; i < nSum; i++) {
    286                        sum += dataRow[i] * m.data[i][col];
    287                    }
    288                    outDataRow[col] = sum;
    289                }
    290            }
    291
    292            return new Array2DRowRealMatrix(outData, false);
    293
    294        }
    295
    296        /** {@inheritDoc} */
    297        @Override
    298        public double[][] getData() {
    299            return copyOut();
    300        }
    301
    302        /**
    303         * Returns a reference to the underlying data array.
    304         * <p>
    305         * Does <strong>not</strong> make a fresh copy of the underlying data.</p>
    306         *
    307         * @return 2-dimensional array of entries
    308         */
    309        public double[][] getDataRef() {
    310            return data;
    311        }
    312
    313        /** {@inheritDoc} */
    314        @Override
    315        public void setSubMatrix(final double[][] subMatrix, final int row, final int column)
    316        throws MatrixIndexException {
    317            if (data == null) {
    318                if (row > 0) {
    319                    throw MathRuntimeException.createIllegalStateException(
    320                          LocalizedFormats.FIRST_ROWS_NOT_INITIALIZED_YET, row);
    321                }
    322                if (column > 0) {
    323                    throw MathRuntimeException.createIllegalStateException(
    324                          LocalizedFormats.FIRST_COLUMNS_NOT_INITIALIZED_YET, column);
    325                }
    326                final int nRows = subMatrix.length;
    327                if (nRows == 0) {
    328                    throw MathRuntimeException.createIllegalArgumentException(
    329                          LocalizedFormats.AT_LEAST_ONE_ROW);
    330                }
    331
    332                final int nCols = subMatrix[0].length;
    333                if (nCols == 0) {
    334                    throw MathRuntimeException.createIllegalArgumentException(
    335                          LocalizedFormats.AT_LEAST_ONE_COLUMN);
    336                }
    337                data = new double[subMatrix.length][nCols];
    338                for (int i = 0; i < data.length; ++i) {
    339                    if (subMatrix[i].length != nCols) {
    340                        throw MathRuntimeException.createIllegalArgumentException(
    341                              LocalizedFormats.DIFFERENT_ROWS_LENGTHS, 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                          LocalizedFormats.NO_SUCH_MATRIX_ENTRY, row, column, getRowDimension(), getColumnDimension());
    360            }
    361        }
    362
    363        /** {@inheritDoc} */
    364        @Override
    365        public void setEntry(final int row, final int column, final double value)
    366            throws MatrixIndexException {
    367            try {
    368                data[row][column] = value;
    369            } catch (ArrayIndexOutOfBoundsException e) {
    370                throw new MatrixIndexException(
    371                          LocalizedFormats.NO_SUCH_MATRIX_ENTRY, 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                          LocalizedFormats.NO_SUCH_MATRIX_ENTRY, row, column, getRowDimension(), getColumnDimension());
    384            }
    385        }
    386
    387        /** {@inheritDoc} */
    388        @Override
    389        public void multiplyEntry(final int row, final int column, final double factor)
    390            throws MatrixIndexException {
    391            try {
    392                data[row][column] *= factor;
    393            } catch (ArrayIndexOutOfBoundsException e) {
    394                throw new MatrixIndexException(
    395                          LocalizedFormats.NO_SUCH_MATRIX_ENTRY, row, column, getRowDimension(), getColumnDimension());
    396            }
    397        }
    398
    399        /** {@inheritDoc} */
    400        @Override
    401        public int getRowDimension() {
    402            return (data == null) ? 0 : data.length;
    403        }
    404
    405        /** {@inheritDoc} */
    406        @Override
    407        public int getColumnDimension() {
    408            return ((data == null) || (data[0] == null)) ? 0 : data[0].length;
    409        }
    410
    411        /** {@inheritDoc} */
    412        @Override
    413        public double[] operate(final double[] v)
    414            throws IllegalArgumentException {
    415            final int nRows = this.getRowDimension();
    416            final int nCols = this.getColumnDimension();
    417            if (v.length != nCols) {
    418                throw MathRuntimeException.createIllegalArgumentException(
    419                      LocalizedFormats.VECTOR_LENGTH_MISMATCH, v.length, nCols);
    420            }
    421            final double[] out = new double[nRows];
    422            for (int row = 0; row < nRows; row++) {
    423                final double[] dataRow = data[row];
    424                double sum = 0;
    425                for (int i = 0; i < nCols; i++) {
    426                    sum += dataRow[i] * v[i];
    427                }
    428                out[row] = sum;
    429            }
    430            return out;
    431        }
    432
    433        /** {@inheritDoc} */
    434        @Override
    435        public double[] preMultiply(final double[] v)
    436            throws IllegalArgumentException {
    437
    438            final int nRows = getRowDimension();
    439            final int nCols = getColumnDimension();
    440            if (v.length != nRows) {
    441                throw MathRuntimeException.createIllegalArgumentException(
    442                      LocalizedFormats.VECTOR_LENGTH_MISMATCH, v.length, nRows);
    443            }
    444
    445            final double[] out = new double[nCols];
    446            for (int col = 0; col < nCols; ++col) {
    447                double sum = 0;
    448                for (int i = 0; i < nRows; ++i) {
    449                    sum += data[i][col] * v[i];
    450                }
    451                out[col] = sum;
    452            }
    453
    454            return out;
    455
    456        }
    457
    458        /** {@inheritDoc} */
    459        @Override
    460        public double walkInRowOrder(final RealMatrixChangingVisitor visitor)
    461            throws MatrixVisitorException {
    462            final int rows    = getRowDimension();
    463            final int columns = getColumnDimension();
    464            visitor.start(rows, columns, 0, rows - 1, 0, columns - 1);
    465            for (int i = 0; i < rows; ++i) {
    466                final double[] rowI = data[i];
    467                for (int j = 0; j < columns; ++j) {
    468                    rowI[j] = visitor.visit(i, j, rowI[j]);
    469                }
    470            }
    471            return visitor.end();
    472        }
    473
    474        /** {@inheritDoc} */
    475        @Override
    476        public double walkInRowOrder(final RealMatrixPreservingVisitor visitor)
    477            throws MatrixVisitorException {
    478            final int rows    = getRowDimension();
    479            final int columns = getColumnDimension();
    480            visitor.start(rows, columns, 0, rows - 1, 0, columns - 1);
    481            for (int i = 0; i < rows; ++i) {
    482                final double[] rowI = data[i];
    483                for (int j = 0; j < columns; ++j) {
    484                    visitor.visit(i, j, rowI[j]);
    485                }
    486            }
    487            return visitor.end();
    488        }
    489
    490        /** {@inheritDoc} */
    491        @Override
    492        public double walkInRowOrder(final RealMatrixChangingVisitor visitor,
    493                                     final int startRow, final int endRow,
    494                                     final int startColumn, final int endColumn)
    495            throws MatrixIndexException, MatrixVisitorException {
    496            MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn);
    497            visitor.start(getRowDimension(), getColumnDimension(),
    498                          startRow, endRow, startColumn, endColumn);
    499            for (int i = startRow; i <= endRow; ++i) {
    500                final double[] rowI = data[i];
    501                for (int j = startColumn; j <= endColumn; ++j) {
    502                    rowI[j] = visitor.visit(i, j, rowI[j]);
    503                }
    504            }
    505            return visitor.end();
    506        }
    507
    508        /** {@inheritDoc} */
    509        @Override
    510        public double walkInRowOrder(final RealMatrixPreservingVisitor 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                    visitor.visit(i, j, rowI[j]);
    521                }
    522            }
    523            return visitor.end();
    524        }
    525
    526        /** {@inheritDoc} */
    527        @Override
    528        public double walkInColumnOrder(final RealMatrixChangingVisitor visitor)
    529            throws MatrixVisitorException {
    530            final int rows    = getRowDimension();
    531            final int columns = getColumnDimension();
    532            visitor.start(rows, columns, 0, rows - 1, 0, columns - 1);
    533            for (int j = 0; j < columns; ++j) {
    534                for (int i = 0; i < rows; ++i) {
    535                    final double[] rowI = data[i];
    536                    rowI[j] = visitor.visit(i, j, rowI[j]);
    537                }
    538            }
    539            return visitor.end();
    540        }
    541
    542        /** {@inheritDoc} */
    543        @Override
    544        public double walkInColumnOrder(final RealMatrixPreservingVisitor visitor)
    545            throws MatrixVisitorException {
    546            final int rows    = getRowDimension();
    547            final int columns = getColumnDimension();
    548            visitor.start(rows, columns, 0, rows - 1, 0, columns - 1);
    549            for (int j = 0; j < columns; ++j) {
    550                for (int i = 0; i < rows; ++i) {
    551                    visitor.visit(i, j, data[i][j]);
    552                }
    553            }
    554            return visitor.end();
    555        }
    556
    557        /** {@inheritDoc} */
    558        @Override
    559        public double walkInColumnOrder(final RealMatrixChangingVisitor visitor,
    560                                        final int startRow, final int endRow,
    561                                        final int startColumn, final int endColumn)
    562            throws MatrixIndexException, MatrixVisitorException {
    563            MatrixUtils.checkSubMatrixIndex(this, startRow, endRow, startColumn, endColumn);
    564            visitor.start(getRowDimension(), getColumnDimension(),
    565                          startRow, endRow, startColumn, endColumn);
    566            for (int j = startColumn; j <= endColumn; ++j) {
    567                for (int i = startRow; i <= endRow; ++i) {
    568                    final double[] rowI = data[i];
    569                    rowI[j] = visitor.visit(i, j, rowI[j]);
    570                }
    571            }
    572            return visitor.end();
    573        }
    574
    575        /** {@inheritDoc} */
    576        @Override
    577        public double walkInColumnOrder(final RealMatrixPreservingVisitor 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                    visitor.visit(i, j, data[i][j]);
    587                }
    588            }
    589            return visitor.end();
    590        }
    591
    592        /**
    593         * Returns a fresh copy of the underlying data array.
    594         *
    595         * @return a copy of the underlying data array.
    596         */
    597        private double[][] copyOut() {
    598            final int nRows = this.getRowDimension();
    599            final double[][] out = new double[nRows][this.getColumnDimension()];
    600            // can't copy 2-d array in one shot, otherwise get row references
    601            for (int i = 0; i < nRows; i++) {
    602                System.arraycopy(data[i], 0, out[i], 0, data[i].length);
    603            }
    604            return out;
    605        }
    606
    607        /**
    608         * Replaces data with a fresh copy of the input array.
    609         * <p>
    610         * Verifies that the input array is rectangular and non-empty.</p>
    611         *
    612         * @param in data to copy in
    613         * @throws IllegalArgumentException if input array is empty or not
    614         *    rectangular
    615         * @throws NullPointerException if input array is null
    616         */
    617        private void copyIn(final double[][] in) {
    618            setSubMatrix(in, 0, 0);
    619        }
    620
    621    }