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: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 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 rows; 37 38 /** Number of columns of the matrix. */ 39 private final int columns; 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.rows = rowDimension; 52 this.columns = 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.rows = matrix.rows; 62 this.columns = matrix.columns; 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 columns; 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() / columns; 112 final int col = iterator.key() - row * columns; 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() / columns; 147 final int col = iterator.key() - row * columns; 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(rows, 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 / columns; 173 final int k = key % columns; 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(rows, 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 / columns; 204 final int k = key % columns; 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 rows; 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 * columns + column; 289 } 290 291 292 } 293
