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