View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      https://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  /*
19   * This is not the original file distributed by the Apache Software Foundation
20   * It has been modified by the Hipparchus project
21   */
22  
23  package org.hipparchus.linear;
24  
25  import java.io.Serializable;
26  
27  import org.hipparchus.exception.LocalizedCoreFormats;
28  import org.hipparchus.exception.MathIllegalArgumentException;
29  import org.hipparchus.util.OpenIntToDoubleHashMap;
30  
31  /**
32   * Sparse matrix implementation based on an open addressed map.
33   *
34   * <p>
35   *  Caveat: This implementation assumes that, for any {@code x},
36   *  the equality {@code x * 0d == 0d} holds. But it is is not true for
37   *  {@code NaN}. Moreover, zero entries will lose their sign.
38   *  Some operations (that involve {@code NaN} and/or infinities) may
39   *  thus give incorrect results.
40   * </p>
41   */
42  public class OpenMapRealMatrix extends AbstractRealMatrix
43      implements SparseRealMatrix, Serializable {
44      /** Serializable version identifier. */
45      private static final long serialVersionUID = -5962461716457143437L;
46      /** Number of rows of the matrix. */
47      private final int rows;
48      /** Number of columns of the matrix. */
49      private final int columns;
50      /** Storage for (sparse) matrix elements. */
51      private final OpenIntToDoubleHashMap entries;
52  
53      /**
54       * Build a sparse matrix with the supplied row and column dimensions.
55       *
56       * @param rowDimension Number of rows of the matrix.
57       * @param columnDimension Number of columns of the matrix.
58       * @throws MathIllegalArgumentException if row or column dimension is not
59       * positive.
60       * @throws MathIllegalArgumentException if the total number of entries of the
61       * matrix is larger than {@code Integer.MAX_VALUE}.
62       */
63      public OpenMapRealMatrix(int rowDimension, int columnDimension)
64          throws MathIllegalArgumentException {
65          super(rowDimension, columnDimension);
66          long lRow = rowDimension;
67          long lCol = columnDimension;
68          if (lRow * lCol >= Integer.MAX_VALUE) {
69              throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_LARGE_BOUND_EXCLUDED,
70                                                     lRow * lCol, Integer.MAX_VALUE);
71          }
72          this.rows = rowDimension;
73          this.columns = columnDimension;
74          this.entries = new OpenIntToDoubleHashMap(0.0);
75      }
76  
77      /**
78       * Build a matrix by copying another one.
79       *
80       * @param matrix matrix to copy.
81       */
82      public OpenMapRealMatrix(OpenMapRealMatrix matrix) {
83          this.rows = matrix.rows;
84          this.columns = matrix.columns;
85          this.entries = new OpenIntToDoubleHashMap(matrix.entries);
86      }
87  
88      /** {@inheritDoc} */
89      @Override
90      public OpenMapRealMatrix copy() {
91          return new OpenMapRealMatrix(this);
92      }
93  
94      /**
95       * {@inheritDoc}
96       *
97       * @throws MathIllegalArgumentException if the total number of entries of the
98       * matrix is larger than {@code Integer.MAX_VALUE}.
99       */
100     @Override
101     public OpenMapRealMatrix createMatrix(int rowDimension, int columnDimension)
102         throws MathIllegalArgumentException {
103         return new OpenMapRealMatrix(rowDimension, columnDimension);
104     }
105 
106     /** {@inheritDoc} */
107     @Override
108     public int getColumnDimension() {
109         return columns;
110     }
111 
112     /**
113      * Compute the sum of this matrix and {@code m}.
114      *
115      * @param m Matrix to be added.
116      * @return {@code this} + {@code m}.
117      * @throws MathIllegalArgumentException if {@code m} is not the same
118      * size as {@code this}.
119      */
120     public OpenMapRealMatrix add(OpenMapRealMatrix m)
121         throws MathIllegalArgumentException {
122 
123         MatrixUtils.checkAdditionCompatible(this, m);
124 
125         final OpenMapRealMatrix out = new OpenMapRealMatrix(this);
126         for (OpenIntToDoubleHashMap.Iterator iterator = m.entries.iterator(); iterator.hasNext();) {
127             iterator.advance();
128             final int row = iterator.key() / columns;
129             final int col = iterator.key() - row * columns;
130             out.setEntry(row, col, getEntry(row, col) + iterator.value());
131         }
132 
133         return out;
134 
135     }
136 
137     /** {@inheritDoc} */
138     @Override
139     public OpenMapRealMatrix subtract(final RealMatrix m)
140         throws MathIllegalArgumentException {
141         if (m instanceof OpenMapRealMatrix) {
142             return subtract((OpenMapRealMatrix) m);
143         } else {
144             return (OpenMapRealMatrix) super.subtract(m);
145         }
146     }
147 
148     /**
149      * Subtract {@code m} from this matrix.
150      *
151      * @param m Matrix to be subtracted.
152      * @return {@code this} - {@code m}.
153      * @throws MathIllegalArgumentException if {@code m} is not the same
154      * size as {@code this}.
155      */
156     public OpenMapRealMatrix subtract(OpenMapRealMatrix m)
157         throws MathIllegalArgumentException {
158         MatrixUtils.checkAdditionCompatible(this, m);
159 
160         final OpenMapRealMatrix out = new OpenMapRealMatrix(this);
161         for (OpenIntToDoubleHashMap.Iterator iterator = m.entries.iterator(); iterator.hasNext();) {
162             iterator.advance();
163             final int row = iterator.key() / columns;
164             final int col = iterator.key() - row * columns;
165             out.setEntry(row, col, getEntry(row, col) - iterator.value());
166         }
167 
168         return out;
169     }
170 
171     /**
172      * {@inheritDoc}
173      *
174      * @throws MathIllegalArgumentException if {@code m} is an
175      * {@code OpenMapRealMatrix}, and the total number of entries of the product
176      * is larger than {@code Integer.MAX_VALUE}.
177      */
178     @Override
179     public RealMatrix multiply(final RealMatrix m)
180         throws MathIllegalArgumentException {
181 
182         MatrixUtils.checkMultiplicationCompatible(this, m);
183 
184         final int outCols = m.getColumnDimension();
185         final RealMatrix out = m.createMatrix(rows, outCols);
186         for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
187             iterator.advance();
188             final double value = iterator.value();
189             final int key      = iterator.key();
190             final int i        = key / columns;
191             final int k        = key % columns;
192             for (int j = 0; j < outCols; ++j) {
193                 out.addToEntry(i, j, value * m.getEntry(k, j));
194             }
195         }
196 
197         return out;
198 
199     }
200 
201     /**
202      * {@inheritDoc}
203      *
204      * @throws MathIllegalArgumentException if {@code m} is an
205      * {@code OpenMapRealMatrix}, and the total number of entries of the product
206      * is larger than {@code Integer.MAX_VALUE}.
207      */
208     @Override
209     public RealMatrix multiplyTransposed(final RealMatrix m)
210         throws MathIllegalArgumentException {
211 
212         MatrixUtils.checkSameColumnDimension(this, m);
213 
214         final int outCols = m.getRowDimension();
215         final RealMatrix out = m.createMatrix(rows, outCols);
216         for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
217             iterator.advance();
218             final double value = iterator.value();
219             final int key      = iterator.key();
220             final int i        = key / columns;
221             final int k        = key % columns;
222             for (int j = 0; j < outCols; ++j) {
223                 out.addToEntry(i, j, value * m.getEntry(j, k));
224             }
225         }
226 
227         return out;
228 
229     }
230 
231     /**
232      * {@inheritDoc}
233      *
234      * @throws MathIllegalArgumentException if {@code m} is an
235      * {@code OpenMapRealMatrix}, and the total number of entries of the product
236      * is larger than {@code Integer.MAX_VALUE}.
237      */
238     @Override
239     public RealMatrix transposeMultiply(final RealMatrix m)
240         throws MathIllegalArgumentException {
241 
242         MatrixUtils.checkSameRowDimension(this, m);
243 
244         final int outCols = m.getColumnDimension();
245         final RealMatrix out = m.createMatrix(columns, outCols);
246         for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
247             iterator.advance();
248             final double value = iterator.value();
249             final int key      = iterator.key();
250             final int k        = key / columns;
251             final int i        = key % columns;
252             for (int j = 0; j < outCols; ++j) {
253                 out.addToEntry(i, j, value * m.getEntry(k, j));
254             }
255         }
256 
257         return out;
258 
259     }
260 
261     /**
262      * Postmultiply this matrix by {@code m}.
263      *
264      * @param m Matrix to postmultiply by.
265      * @return {@code this} * {@code m}.
266      * @throws MathIllegalArgumentException if the number of rows of {@code m}
267      * differ from the number of columns of {@code this} matrix.
268      * @throws MathIllegalArgumentException if the total number of entries of the
269      * product is larger than {@code Integer.MAX_VALUE}.
270      */
271     public OpenMapRealMatrix multiply(OpenMapRealMatrix m)
272         throws MathIllegalArgumentException {
273         // Safety check.
274         MatrixUtils.checkMultiplicationCompatible(this, m);
275 
276         final int outCols = m.getColumnDimension();
277         OpenMapRealMatrix out = new OpenMapRealMatrix(rows, outCols);
278         for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
279             iterator.advance();
280             final double value = iterator.value();
281             final int key      = iterator.key();
282             final int i        = key / columns;
283             final int k        = key % columns;
284             for (int j = 0; j < outCols; ++j) {
285                 final int rightKey = m.computeKey(k, j);
286                 if (m.entries.containsKey(rightKey)) {
287                     final int outKey = out.computeKey(i, j);
288                     final double outValue =
289                         out.entries.get(outKey) + value * m.entries.get(rightKey);
290                     if (outValue == 0.0) {
291                         out.entries.remove(outKey);
292                     } else {
293                         out.entries.put(outKey, outValue);
294                     }
295                 }
296             }
297         }
298 
299         return out;
300     }
301 
302     /** {@inheritDoc} */
303     @Override
304     public double getEntry(int row, int column) throws MathIllegalArgumentException {
305         MatrixUtils.checkRowIndex(this, row);
306         MatrixUtils.checkColumnIndex(this, column);
307         return entries.get(computeKey(row, column));
308     }
309 
310     /** {@inheritDoc} */
311     @Override
312     public int getRowDimension() {
313         return rows;
314     }
315 
316     /** {@inheritDoc} */
317     @Override
318     public void setEntry(int row, int column, double value)
319         throws MathIllegalArgumentException {
320         MatrixUtils.checkRowIndex(this, row);
321         MatrixUtils.checkColumnIndex(this, column);
322         if (value == 0.0) {
323             entries.remove(computeKey(row, column));
324         } else {
325             entries.put(computeKey(row, column), value);
326         }
327     }
328 
329     /** {@inheritDoc} */
330     @Override
331     public void addToEntry(int row, int column, double increment)
332         throws MathIllegalArgumentException {
333         MatrixUtils.checkRowIndex(this, row);
334         MatrixUtils.checkColumnIndex(this, column);
335         final int key = computeKey(row, column);
336         final double value = entries.get(key) + increment;
337         if (value == 0.0) {
338             entries.remove(key);
339         } else {
340             entries.put(key, value);
341         }
342     }
343 
344     /** {@inheritDoc} */
345     @Override
346     public void multiplyEntry(int row, int column, double factor)
347         throws MathIllegalArgumentException {
348         MatrixUtils.checkRowIndex(this, row);
349         MatrixUtils.checkColumnIndex(this, column);
350         final int key = computeKey(row, column);
351         final double value = entries.get(key) * factor;
352         if (value == 0.0) {
353             entries.remove(key);
354         } else {
355             entries.put(key, value);
356         }
357     }
358 
359     /**
360      * Compute the key to access a matrix element
361      * @param row row index of the matrix element
362      * @param column column index of the matrix element
363      * @return key within the map to access the matrix element
364      */
365     private int computeKey(int row, int column) {
366         return row * columns + column;
367     }
368 
369 
370 }