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    *      http://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  package org.apache.commons.math.linear;
19  
20  import java.io.Serializable;
21  
22  import org.apache.commons.math.util.OpenIntToDoubleHashMap;
23  
24  /**
25   * Sparse matrix implementation based on an open addressed map.
26   * 
27   * @version $Revision: 783678 $ $Date: 2009-06-11 04:05:24 -0400 (Thu, 11 Jun 2009) $
28   * @since 2.0
29   */
30  public class OpenMapRealMatrix extends AbstractRealMatrix implements SparseRealMatrix, Serializable {
31  
32      /** Serializable version identifier. */
33      private static final long serialVersionUID = -5962461716457143437L;
34  
35      /** Number of rows of the matrix. */
36      private final int rowDimension;
37  
38      /** Number of columns of the matrix. */
39      private final int columnDimension;
40  
41      /** Storage for (sparse) matrix elements. */
42      private final OpenIntToDoubleHashMap entries;
43  
44      /**
45       * Build a sparse matrix with the supplied row and column dimensions.
46       * @param rowDimension number of rows of the matrix
47       * @param columnDimension number of columns of the matrix
48       */
49      public OpenMapRealMatrix(int rowDimension, int columnDimension) {
50          super(rowDimension, columnDimension);
51          this.rowDimension = rowDimension;
52          this.columnDimension = columnDimension;
53          this.entries = new OpenIntToDoubleHashMap(0.0);
54      }
55    
56      /**
57       * Build a matrix by copying another one.
58       * @param matrix matrix to copy
59       */
60      public OpenMapRealMatrix(OpenMapRealMatrix matrix) {
61          this.rowDimension = matrix.rowDimension;
62          this.columnDimension = matrix.columnDimension;
63          this.entries = new OpenIntToDoubleHashMap(matrix.entries);
64      }
65    
66      /** {@inheritDoc} */
67      @Override
68      public OpenMapRealMatrix copy() {
69          return new OpenMapRealMatrix(this);
70      }
71  
72      /** {@inheritDoc} */
73      @Override
74      public OpenMapRealMatrix createMatrix(int rowDimension, int columnDimension)
75              throws IllegalArgumentException {
76          return new OpenMapRealMatrix(rowDimension, columnDimension);
77      }
78  
79      /** {@inheritDoc} */
80      @Override
81      public int getColumnDimension() {
82          return columnDimension;
83      }
84  
85      /** {@inheritDoc} */
86      @Override
87      public OpenMapRealMatrix add(final RealMatrix m)
88          throws IllegalArgumentException {
89          try {
90              return add((OpenMapRealMatrix) m);
91          } catch (ClassCastException cce) {
92              return (OpenMapRealMatrix) super.add(m);
93          }
94      }
95  
96      /**
97       * Compute the sum of this and <code>m</code>.
98       *
99       * @param m    matrix to be added
100      * @return     this + m
101      * @throws  IllegalArgumentException if m is not the same size as this
102      */
103     public OpenMapRealMatrix add(OpenMapRealMatrix m) throws IllegalArgumentException {
104 
105         // safety check
106         MatrixUtils.checkAdditionCompatible(this, m);
107 
108         final OpenMapRealMatrix out = new OpenMapRealMatrix(this);
109         for (OpenIntToDoubleHashMap.Iterator iterator = m.entries.iterator(); iterator.hasNext();) {
110             iterator.advance();
111             final int row = iterator.key() / columnDimension;
112             final int col = iterator.key() - row * columnDimension;
113             out.setEntry(row, col, getEntry(row, col) + iterator.value());
114         }
115 
116         return out;
117 
118     }
119 
120     /** {@inheritDoc} */
121     @Override
122     public OpenMapRealMatrix subtract(final RealMatrix m)
123         throws IllegalArgumentException {
124         try {
125             return subtract((OpenMapRealMatrix) m);
126         } catch (ClassCastException cce) {
127             return (OpenMapRealMatrix) super.subtract(m);
128         }
129     }
130 
131     /**
132      * Compute this minus <code>m</code>.
133      *
134      * @param m    matrix to be subtracted
135      * @return     this - m
136      * @throws  IllegalArgumentException if m is not the same size as this
137      */
138     public OpenMapRealMatrix subtract(OpenMapRealMatrix m) throws IllegalArgumentException {
139 
140         // safety check
141         MatrixUtils.checkAdditionCompatible(this, m);
142 
143         final OpenMapRealMatrix out = new OpenMapRealMatrix(this);
144         for (OpenIntToDoubleHashMap.Iterator iterator = m.entries.iterator(); iterator.hasNext();) {
145             iterator.advance();
146             final int row = iterator.key() / columnDimension;
147             final int col = iterator.key() - row * columnDimension;
148             out.setEntry(row, col, getEntry(row, col) - iterator.value());
149         }
150 
151         return out;
152 
153     }
154 
155     /** {@inheritDoc} */
156     @Override
157     public RealMatrix multiply(final RealMatrix m)
158         throws IllegalArgumentException {
159         try {
160             return multiply((OpenMapRealMatrix) m);
161         } catch (ClassCastException cce) {
162 
163             // safety check
164             MatrixUtils.checkMultiplicationCompatible(this, m);
165 
166             final int outCols = m.getColumnDimension();
167             final BlockRealMatrix out = new BlockRealMatrix(rowDimension, outCols);
168             for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
169                 iterator.advance();
170                 final double value = iterator.value();
171                 final int key      = iterator.key();
172                 final int i        = key / columnDimension;
173                 final int k        = key % columnDimension;
174                 for (int j = 0; j < outCols; ++j) {
175                     out.addToEntry(i, j, value * m.getEntry(k, j));
176                 }
177             }
178 
179             return out;
180 
181         }
182     }
183 
184     /**
185      * Returns the result of postmultiplying this by m.
186      *
187      * @param m    matrix to postmultiply by
188      * @return     this * m
189      * @throws     IllegalArgumentException
190      *             if columnDimension(this) != rowDimension(m)
191      */
192     public OpenMapRealMatrix multiply(OpenMapRealMatrix m) throws IllegalArgumentException {
193 
194         // safety check
195         MatrixUtils.checkMultiplicationCompatible(this, m);
196 
197         final int outCols = m.getColumnDimension();
198         OpenMapRealMatrix out = new OpenMapRealMatrix(rowDimension, outCols);
199         for (OpenIntToDoubleHashMap.Iterator iterator = entries.iterator(); iterator.hasNext();) {
200             iterator.advance();
201             final double value = iterator.value();
202             final int key      = iterator.key();
203             final int i        = key / columnDimension;
204             final int k        = key % columnDimension;
205             for (int j = 0; j < outCols; ++j) {
206                 final int rightKey = m.computeKey(k, j);
207                 if (m.entries.containsKey(rightKey)) {
208                     final int outKey = out.computeKey(i, j);
209                     final double outValue =
210                         out.entries.get(outKey) + value * m.entries.get(rightKey);
211                     if (outValue == 0.0) {
212                         out.entries.remove(outKey);
213                     } else {
214                         out.entries.put(outKey, outValue);
215                     }
216                 }
217             }
218         }
219 
220         return out;
221 
222     }
223 
224     /** {@inheritDoc} */
225     @Override
226     public double getEntry(int row, int column) throws MatrixIndexException {
227         MatrixUtils.checkRowIndex(this, row);
228         MatrixUtils.checkColumnIndex(this, column);
229         return entries.get(computeKey(row, column));
230     }
231 
232     /** {@inheritDoc} */
233     @Override
234     public int getRowDimension() {
235         return rowDimension;
236     }
237 
238     /** {@inheritDoc} */
239     @Override
240     public void setEntry(int row, int column, double value)
241             throws MatrixIndexException {
242         MatrixUtils.checkRowIndex(this, row);
243         MatrixUtils.checkColumnIndex(this, column);
244         if (value == 0.0) {
245             entries.remove(computeKey(row, column));
246         } else {
247             entries.put(computeKey(row, column), value);
248         }
249     }
250 
251     /** {@inheritDoc} */
252     @Override
253     public void addToEntry(int row, int column, double increment)
254             throws MatrixIndexException {
255         MatrixUtils.checkRowIndex(this, row);
256         MatrixUtils.checkColumnIndex(this, column);
257         final int key = computeKey(row, column);
258         final double value = entries.get(key) + increment;
259         if (value == 0.0) {
260             entries.remove(key);
261         } else {
262             entries.put(key, value);
263         }
264     }
265 
266     /** {@inheritDoc} */
267     @Override
268     public void multiplyEntry(int row, int column, double factor)
269             throws MatrixIndexException {
270         MatrixUtils.checkRowIndex(this, row);
271         MatrixUtils.checkColumnIndex(this, column);
272         final int key = computeKey(row, column);
273         final double value = entries.get(key) * factor;
274         if (value == 0.0) {
275             entries.remove(key);
276         } else {
277             entries.put(key, value);
278         }
279     }
280 
281     /**
282      * Compute the key to access a matrix element
283      * @param row row index of the matrix element
284      * @param column column index of the matrix element
285      * @return key within the map to access the matrix element
286      */
287     private int computeKey(int row, int column) {
288         return row * columnDimension + column;
289     }
290 
291 
292 }