DoubleSparseMatrix


1   package JSci.maths.matrices;
2   
3   import JSci.GlobalSettings;
4   import JSci.maths.Mapping;
5   import JSci.maths.DimensionException;
6   import JSci.maths.vectors.AbstractDoubleVector;
7   import JSci.maths.vectors.DoubleVector;
8   
9   /**
10  * The DoubleSparseMatrix class provides an object for encapsulating sparse matrices.
11  * Uses compressed row storage.
12  * @version 1.2
13  * @author Mark Hale
14  */
15  public final class DoubleSparseMatrix extends AbstractDoubleMatrix {
16          /**
17          * Matrix elements.
18          */
19          private double elements[];
20          /**
21          * Sparse indexing data.
22          * Contains the column positions of each element,
23          * e.g. <code>colPos[n]</code> is the column position
24          * of the <code>n</code>th element.
25          */
26          private int colPos[];
27          /**
28          * Sparse indexing data.
29          * Contains the indices of the start of each row,
30          * e.g. <code>rows[i]</code> is the index
31          * where the <code>i</code>th row starts.
32          */
33          private int rows[];
34          /**
35          * Constructs an empty matrix.
36          * @param rowCount the number of rows
37          * @param colCount the number of columns
38          */
39          public DoubleSparseMatrix(final int rowCount, final int colCount) {
40                  super(rowCount, colCount);
41                  elements=new double[0];
42                  colPos=new int[0];
43                  rows=new int[numRows+1];
44          }
45          /**
46          * Constructs a matrix from an array.
47          * @param array an assigned value
48          */
49          public DoubleSparseMatrix(final double array[][]) {
50                  super(array.length,array[0].length);
51                  rows=new int[numRows+1];
52                  int n=0;
53                  for(int i=0;i<numRows;i++) {
54                          if(array[i].length != array.length)
55                                  throw new MatrixDimensionException("Array is not square.");
56                          for(int j=0;j<numCols;j++) {
57                                  if(Math.abs(array[i][j])>GlobalSettings.ZERO_TOL)
58                                          n++;
59                          }
60                  }
61                  elements=new double[n];
62                  colPos=new int[n];
63                  n=0;
64                  for(int i=0;i<numRows;i++) {
65                          rows[i]=n;
66                          for(int j=0;j<numCols;j++) {
67                                  if(Math.abs(array[i][j])>GlobalSettings.ZERO_TOL) {
68                                          elements[n]=array[i][j];
69                                          colPos[n]=j;
70                                          n++;
71                                  }
72                          }
73                  }
74                  rows[numRows]=n;
75          }
76          /**
77          * Compares two double sparse matrices for equality.
78          * @param m a double matrix
79          */
80          public boolean equals(AbstractDoubleMatrix m, double tol) {
81                  if(numRows==m.numRows && numCols==m.numCols) {
82                          if(m instanceof DoubleSparseMatrix) {
83                                  return this.equals((DoubleSparseMatrix)m);
84                          } else {
85                      double sumSqr = 0;
86                                  for(int i=0;i<numRows;i++) {
87                                          for(int j=0;j<numCols;j++) {
88                              double delta = getElement(i,j)-m.getElement(i,j);
89                              sumSqr += delta*delta;
90                                          }
91                                  }
92                                  return (sumSqr <= tol*tol);
93                          }
94                  } else
95                          return false;
96          }
97          public final boolean equals(DoubleSparseMatrix m) {
98          return equals(m, GlobalSettings.ZERO_TOL);
99      }
100         public boolean equals(DoubleSparseMatrix m, double tol) {
101                 if(numRows==m.numRows && numCols==m.numCols) {
102                         if(colPos.length!=m.colPos.length)
103                                 return false;
104                         for(int i=1;i<rows.length;i++) {
105                                 if(rows[i]!=m.rows[i])
106                                         return false;
107                         }
108                         double sumSqr = 0.0;
109                         for(int i=1;i<colPos.length;i++) {
110                                 if(colPos[i]!=m.colPos[i])
111                                         return false;
112                                 double delta = elements[i] - m.elements[i];
113                                 sumSqr += delta*delta;
114                         }
115                         return (sumSqr <= tol*tol);
116                 } else
117                         return false;
118         }
119         /**
120         * Returns a string representing this matrix.
121         */
122         public String   toString() {
123                 final StringBuffer   buf=new StringBuffer  (numRows*numCols);
124                 for(int i=0;i<numRows;i++) {
125                         for(int j=0;j<numCols;j++) {
126                                 buf.append(getElement(i,j));
127                                 buf.append(' ');
128                         }
129                         buf.append('\n');
130                 }
131                 return buf.toString();
132         }
133         /**
134         * Converts this matrix to an integer matrix.
135         * @return an integer matrix
136         */
137         public AbstractIntegerMatrix toIntegerMatrix() {
138                 final int ans[][]=new int[numRows][numCols];
139                 for(int i=0;i<numRows;i++) {
140                         for(int j=0;j<numCols;j++)
141                                 ans[i][j]=Math.round((float)getElement(i,j));
142                 }
143                 return new IntegerMatrix(ans);
144         }
145         /**
146         * Converts this matrix to a complex matrix.
147         * @return a complex matrix
148         */
149         public AbstractComplexMatrix toComplexMatrix() {
150                 final double arrayRe[][]=new double[numRows][numCols];
151                 for(int i=0;i<numRows;i++) {
152                         for(int j=0;j<numCols;j++)
153                                 arrayRe[i][j]=getElement(i,j);
154                 }
155                 return new ComplexMatrix(arrayRe,new double[numRows][numCols]);
156         }
157         /**
158         * Returns an element of the matrix.
159         * @param i row index of the element
160         * @param j column index of the element
161         * @exception MatrixDimensionException If attempting to access an invalid element.
162         */
163         public double getElement(final int i, final int j) {
164                 if(i>=0 && i<numRows && j>=0 && j<numCols) {
165                         for(int k=rows[i];k<rows[i+1];k++) {
166                                 if(colPos[k]==j)
167                                         return elements[k];
168                         }
169                         return 0.0;
170                 } else
171                         throw new MatrixDimensionException(getInvalidElementMsg(i,j));
172         }
173         /**
174         * Sets the value of an element of the matrix.
175         * @param i row index of the element
176         * @param j column index of the element
177         * @param x a number
178         * @exception MatrixDimensionException If attempting to access an invalid element.
179         */
180         public void setElement(final int i, final int j, final double x) {
181                 if(i>=0 && i<numRows && j>=0 && j<numCols) {
182                         if(Math.abs(x)<=GlobalSettings.ZERO_TOL)
183                                 return;
184                         for(int k=rows[i];k<rows[i+1];k++) {
185                                 if(colPos[k]==j) {
186                                         elements[k]=x;
187                                         return;
188                                 }
189                         }
190                         final double oldMatrix[]=elements;
191                         final int oldColPos[]=colPos;
192                         elements=new double[oldMatrix.length+1];
193                         colPos=new int[oldColPos.length+1];
194                         System.arraycopy(oldMatrix,0,elements,0,rows[i]);
195                         System.arraycopy(oldColPos,0,colPos,0,rows[i]);
196                         int k;
197                         for(k=rows[i];k<rows[i+1] && oldColPos[k]<j;k++) {
198                                 elements[k]=oldMatrix[k];
199                                 colPos[k]=oldColPos[k];
200                         }
201                         elements[k]=x;
202                         colPos[k]=j;
203                         System.arraycopy(oldMatrix,k,elements,k+1,oldMatrix.length-k);
204                         System.arraycopy(oldColPos,k,colPos,k+1,oldColPos.length-k);
205                         for(k=i+1;k<rows.length;k++)
206                                 rows[k]++;
207                 } else
208                         throw new MatrixDimensionException(getInvalidElementMsg(i,j));
209         }
210         /**
211         * Returns the l<sup><img border=0 alt="infinity" SRC="doc-files/infinity.gif"></sup>-norm.
212         */
213         public double infNorm() {
214                 double result=0.0,tmpResult;
215                 for(int i=0;i<numRows;i++) {
216                         tmpResult=0.0;
217                         for(int j=rows[i];j<rows[i+1];j++)
218                                 tmpResult+=Math.abs(elements[j]);
219                         if(tmpResult>result)
220                                 result=tmpResult;
221                 }
222                 return result;
223         }
224         /**
225         * Returns the Frobenius (l<sup>2</sup>) norm.
226         */
227         public double frobeniusNorm() {
228                 double result=0.0;
229                 for(int i=0;i<colPos.length;i++)
230                         result+=elements[i]*elements[i];
231                 return Math.sqrt(result);
232         }
233 
234 //============
235 // OPERATIONS
236 //============
237 
238 // ADDITION
239 
240         /**
241         * Returns the addition of this matrix and another.
242         * @param m a double matrix
243         * @exception MatrixDimensionException If the matrices are different sizes.
244         */
245         public AbstractDoubleMatrix add(final AbstractDoubleMatrix m) {
246                 if(m instanceof DoubleSparseMatrix)
247                         return add((DoubleSparseMatrix)m);
248                 if(m instanceof DoubleMatrix)
249                         return add((DoubleMatrix)m);
250 
251                 if(numRows==m.rows() && numCols==m.columns()) {
252                         final double array[][]=new double[numRows][numCols];
253                         for(int i=0;i<numRows;i++) {
254                                 for(int j=rows[i];j<rows[i+1];j++)
255                                         array[i][colPos[j]]=elements[j];
256                                 array[i][0]+=m.getElement(i,0);
257                                 for(int j=1;j<numCols;j++)
258                                         array[i][j]+=m.getElement(i,j);
259                         }
260                         return new DoubleMatrix(array);
261                 } else {
262                         throw new MatrixDimensionException("Matrices are different sizes.");
263                 }
264         }
265         public DoubleMatrix add(final DoubleMatrix m) {
266                 if(numRows==m.numRows && numCols==m.numCols) {
267                         final double array[][]=new double[numRows][numCols];
268                         for(int i=0;i<numRows;i++) {
269                                 for(int j=rows[i];j<rows[i+1];j++)
270                                         array[i][colPos[j]]=elements[j];
271                                 array[i][0]+=m.matrix[i][0];
272                                 for(int j=1;j<numCols;j++)
273                                         array[i][j]+=m.matrix[i][j];
274                         }
275                         return new DoubleMatrix(array);
276                 } else
277                         throw new MatrixDimensionException("Matrices are different sizes.");
278         }
279         /**
280         * Returns the addition of this matrix and another.
281         * @param m a double sparse matrix
282         * @exception MatrixDimensionException If the matrices are different sizes.
283         */
284         public DoubleSparseMatrix add(final DoubleSparseMatrix m) {
285                 if(numRows==m.numRows && numCols==m.numCols) {
286                         DoubleSparseMatrix ans=new DoubleSparseMatrix(numRows,numCols);
287                         for(int i=0;i<numRows;i++) {
288                                 for(int j=0;j<numCols;j++)
289                                         ans.setElement(i,j,getElement(i,j)+m.getElement(i,j));
290                         }
291                         return ans;
292                 } else
293                         throw new MatrixDimensionException("Matrices are different sizes.");
294         }
295 
296 // SUBTRACTION
297 
298         /**
299         * Returns the subtraction of this matrix and another.
300         * @param m a double matrix
301         * @exception MatrixDimensionException If the matrices are different sizes.
302         */
303         public AbstractDoubleMatrix subtract(final AbstractDoubleMatrix m) {
304                 if(m instanceof DoubleSparseMatrix)
305                         return subtract((DoubleSparseMatrix)m);
306                 if(m instanceof DoubleMatrix)
307                         return subtract((DoubleMatrix)m);
308 
309                 if(numRows==m.rows() && numCols==m.columns()) {
310                         final double array[][]=new double[numRows][numCols];
311                         for(int i=0;i<numRows;i++) {
312                                 for(int j=rows[i];j<rows[i+1];j++)
313                                         array[i][colPos[j]]=elements[j];
314                                 array[i][0]-=m.getElement(i,0);
315                                 for(int j=1;j<numCols;j++)
316                                         array[i][j]-=m.getElement(i,j);
317                         }
318                         return new DoubleMatrix(array);
319                 } else {
320                         throw new MatrixDimensionException("Matrices are different sizes.");
321                 }
322         }
323         public DoubleMatrix subtract(final DoubleMatrix m) {
324                 if(numRows==m.numRows && numCols==m.numCols) {
325                         final double array[][]=new double[numRows][numCols];
326                         for(int i=0;i<numRows;i++) {
327                                 for(int j=rows[i];j<rows[i+1];j++)
328                                         array[i][colPos[j]]=elements[j];
329                                 array[i][0]-=m.matrix[i][0];
330                                 for(int j=1;j<numCols;j++)
331                                         array[i][j]-=m.matrix[i][j];
332                         }
333                         return new DoubleMatrix(array);
334                 } else
335                         throw new MatrixDimensionException("Matrices are different sizes.");
336         }
337         /**
338         * Returns the addition of this matrix and another.
339         * @param m a double sparse matrix
340         * @exception MatrixDimensionException If the matrices are different sizes.
341         */
342         public DoubleSparseMatrix subtract(final DoubleSparseMatrix m) {
343                 if(numRows==m.numRows && numCols==m.numCols) {
344                         DoubleSparseMatrix ans=new DoubleSparseMatrix(numRows,numCols);
345                         for(int i=0;i<numRows;i++) {
346                                 for(int j=0;j<numCols;j++)
347                                         ans.setElement(i,j,getElement(i,j)-m.getElement(i,j));
348                         }
349                         return ans;
350                 } else
351                         throw new MatrixDimensionException("Matrices are different sizes.");
352         }
353 
354 // SCALAR MULTIPLICATION
355 
356         /**
357         * Returns the multiplication of this matrix by a scalar.
358         * @param x a double
359         * @return a double sparse matrix
360         */
361         public AbstractDoubleMatrix scalarMultiply(final double x) {
362                 final DoubleSparseMatrix ans=new DoubleSparseMatrix(numRows,numCols);
363                 ans.elements=new double[elements.length];
364                 ans.colPos=new int[colPos.length];
365                 System.arraycopy(colPos,0,ans.colPos,0,colPos.length);
366                 System.arraycopy(rows,0,ans.rows,0,rows.length);
367                 for(int i=0;i<colPos.length;i++)
368                         ans.elements[i]=x*elements[i];
369                 return ans;
370         }
371 
372         public AbstractDoubleMatrix scalarDivide(final double x) {
373                 final DoubleSparseMatrix ans=new DoubleSparseMatrix(numRows,numCols);
374                 ans.elements=new double[elements.length];
375                 ans.colPos=new int[colPos.length];
376                 System.arraycopy(colPos,0,ans.colPos,0,colPos.length);
377                 System.arraycopy(rows,0,ans.rows,0,rows.length);
378                 for(int i=0;i<colPos.length;i++)
379                         ans.elements[i]=elements[i]/x;
380                 return ans;
381         }
382 
383 // SCALAR PRODUCT
384 
385         /**
386         * Returns the scalar product of this matrix and another.
387         * @param m a double matrix.
388         * @exception MatrixDimensionException If the matrices are different sizes.
389         */
390         public double scalarProduct(final AbstractDoubleMatrix m) {
391                 if(m instanceof DoubleMatrix)
392                         return scalarProduct((DoubleMatrix)m);
393 
394                 if(numRows==m.numRows && numCols==m.numCols) {
395                         double ans=0.0;
396                         for(int i=0;i<numRows;i++) {
397                                 for(int j=rows[i];j<rows[i+1];j++)
398                                         ans+=elements[j]*m.getElement(i,colPos[j]);
399                         }
400                         return ans;
401                 } else
402                         throw new MatrixDimensionException("Matrices are different sizes.");
403         }
404         public double scalarProduct(final DoubleMatrix m) {
405                 if(numRows==m.numRows && numCols==m.numCols) {
406                         double ans=0.0;
407                         for(int i=0;i<numRows;i++) {
408                                 for(int j=rows[i];j<rows[i+1];j++)
409                                         ans+=elements[j]*m.matrix[i][colPos[j]];
410                         }
411                         return ans;
412                 } else
413                         throw new MatrixDimensionException("Matrices are different sizes.");
414         }
415 
416 // MATRIX MULTIPLICATION
417 
418         /**
419         * Returns the multiplication of a vector by this matrix.
420         * @param v a double vector
421         * @exception DimensionException If the matrix and vector are incompatible.
422         */
423         public AbstractDoubleVector multiply(final AbstractDoubleVector v) {
424                 if(numCols==v.dimension()) {
425                         final double array[]=new double[numRows];
426                         for(int i=0;i<numRows;i++) {
427                                 for(int j=rows[i];j<rows[i+1];j++)
428                                         array[i]+=elements[j]*v.getComponent(colPos[j]);
429                         }
430                         return new DoubleVector(array);
431                 } else
432                         throw new DimensionException("Matrix and vector are incompatible.");
433         }
434         /**
435         * Returns the multiplication of this matrix and another.
436         * @param m a double matrix
437         * @exception MatrixDimensionException If the matrices are incompatible.
438         */
439         public AbstractDoubleMatrix multiply(final AbstractDoubleMatrix m) {
440                 if(m instanceof DoubleSparseMatrix)
441                         return multiply((DoubleSparseMatrix)m);
442                 if(m instanceof DoubleMatrix)
443                         return multiply((DoubleMatrix)m);
444 
445                 if(numCols==m.numRows) {
446                         final double array[][]=new double[numRows][m.numCols];
447                         for(int j=0;j<numRows;j++) {
448                                 for(int k=0;k<m.numCols;k++) {
449                                         for(int n=rows[j];n<rows[j+1];n++)
450                                                 array[j][k]+=elements[n]*m.getElement(colPos[n],k);
451                                 }
452                         }
453                         if(numRows==m.numCols)
454                                 return new DoubleSquareMatrix(array);
455                         else
456                                 return new DoubleMatrix(array);
457                 } else
458                         throw new MatrixDimensionException("Incompatible matrices.");
459         }
460         public AbstractDoubleMatrix multiply(final DoubleMatrix m) {
461                 if(numCols==m.numRows) {
462                         final double array[][]=new double[numRows][m.numCols];
463                         for(int j=0;j<numRows;j++) {
464                                 for(int k=0;k<m.numCols;k++) {
465                                         for(int n=rows[j];n<rows[j+1];n++)
466                                                 array[j][k]+=elements[n]*m.matrix[colPos[n]][k];
467                                 }
468                         }
469                         if(numRows==m.numCols)
470                                 return new DoubleSquareMatrix(array);
471                         else
472                                 return new DoubleMatrix(array);
473                 } else
474                         throw new MatrixDimensionException("Incompatible matrices.");
475         }
476         /**
477         * Returns the multiplication of this matrix and another.
478         * @param m a double sparse matrix
479         * @exception MatrixDimensionException If the matrices are incompatible.
480         */
481         public AbstractDoubleMatrix multiply(final DoubleSparseMatrix m) {
482                 if(numCols==m.numRows) {
483                         AbstractDoubleMatrix ans;
484                         if(numRows==m.numCols)
485                                 ans=new DoubleSparseSquareMatrix(numRows);
486                         else
487                                 ans=new DoubleSparseMatrix(numRows,m.numCols);
488                         for(int j=0;j<ans.numRows;j++) {
489                                 for(int k=0;k<ans.numCols;k++) {
490                                         double tmp=0.0;
491                                         for(int n=rows[j];n<rows[j+1];n++)
492                                                 tmp+=elements[n]*m.getElement(colPos[n],k);
493                                         ans.setElement(j,k,tmp);
494                                 }
495                         }
496                         return ans;
497                 } else
498                         throw new MatrixDimensionException("Incompatible matrices.");
499         }
500 
501 // TRANSPOSE
502 
503         /**
504         * Returns the transpose of this matrix.
505         * @return a double sparse matrix
506         */
507         public Matrix transpose() {
508                 final DoubleSparseMatrix ans=new DoubleSparseMatrix(numCols,numRows);
509                 for(int i=0;i<numRows;i++) {
510                         ans.setElement(0,i,getElement(i,0));
511                         for(int j=1;j<numCols;j++)
512                                 ans.setElement(j,i,getElement(i,j));
513                 }
514                 return ans;
515         }
516 
517 // MAP ELEMENTS
518 
519         /**
520         * Applies a function on all the matrix elements.
521         * @param f a user-defined function
522         * @return a double sparse matrix
523         */
524         public AbstractDoubleMatrix mapElements(final Mapping f) {
525                 final DoubleSparseMatrix ans=new DoubleSparseMatrix(numRows,numCols);
526                 ans.elements=new double[elements.length];
527                 ans.colPos=new int[colPos.length];
528                 System.arraycopy(colPos,0,ans.colPos,0,colPos.length);
529                 System.arraycopy(rows,0,ans.rows,0,rows.length);
530                 for(int i=0;i<colPos.length;i++)
531                         ans.elements[i]=f.map(elements[i]);
532                 return ans;
533         }
534 }
535 
536
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags