001: package JSci.maths.matrices;
002:
003: import JSci.GlobalSettings;
004: import JSci.maths.Mapping;
005: import JSci.maths.DimensionException;
006: import JSci.maths.vectors.AbstractDoubleVector;
007: import JSci.maths.vectors.DoubleVector;
008:
009: /**
010: * The DoubleSparseMatrix class provides an object for encapsulating sparse matrices.
011: * Uses compressed row storage.
012: * @version 1.2
013: * @author Mark Hale
014: */
015: public final class DoubleSparseMatrix extends AbstractDoubleMatrix {
016: /**
017: * Matrix elements.
018: */
019: private double elements[];
020: /**
021: * Sparse indexing data.
022: * Contains the column positions of each element,
023: * e.g. <code>colPos[n]</code> is the column position
024: * of the <code>n</code>th element.
025: */
026: private int colPos[];
027: /**
028: * Sparse indexing data.
029: * Contains the indices of the start of each row,
030: * e.g. <code>rows[i]</code> is the index
031: * where the <code>i</code>th row starts.
032: */
033: private int rows[];
034:
035: /**
036: * Constructs an empty matrix.
037: * @param rowCount the number of rows
038: * @param colCount the number of columns
039: */
040: public DoubleSparseMatrix(final int rowCount, final int colCount) {
041: super (rowCount, colCount);
042: elements = new double[0];
043: colPos = new int[0];
044: rows = new int[numRows + 1];
045: }
046:
047: /**
048: * Constructs a matrix from an array.
049: * @param array an assigned value
050: */
051: public DoubleSparseMatrix(final double array[][]) {
052: super (array.length, array[0].length);
053: rows = new int[numRows + 1];
054: int n = 0;
055: for (int i = 0; i < numRows; i++) {
056: if (array[i].length != array.length)
057: throw new MatrixDimensionException(
058: "Array is not square.");
059: for (int j = 0; j < numCols; j++) {
060: if (Math.abs(array[i][j]) > GlobalSettings.ZERO_TOL)
061: n++;
062: }
063: }
064: elements = new double[n];
065: colPos = new int[n];
066: n = 0;
067: for (int i = 0; i < numRows; i++) {
068: rows[i] = n;
069: for (int j = 0; j < numCols; j++) {
070: if (Math.abs(array[i][j]) > GlobalSettings.ZERO_TOL) {
071: elements[n] = array[i][j];
072: colPos[n] = j;
073: n++;
074: }
075: }
076: }
077: rows[numRows] = n;
078: }
079:
080: /**
081: * Compares two double sparse matrices for equality.
082: * @param m a double matrix
083: */
084: public boolean equals(AbstractDoubleMatrix m, double tol) {
085: if (numRows == m.numRows && numCols == m.numCols) {
086: if (m instanceof DoubleSparseMatrix) {
087: return this .equals((DoubleSparseMatrix) m);
088: } else {
089: double sumSqr = 0;
090: for (int i = 0; i < numRows; i++) {
091: for (int j = 0; j < numCols; j++) {
092: double delta = getElement(i, j)
093: - m.getElement(i, j);
094: sumSqr += delta * delta;
095: }
096: }
097: return (sumSqr <= tol * tol);
098: }
099: } else
100: return false;
101: }
102:
103: public final boolean equals(DoubleSparseMatrix m) {
104: return equals(m, GlobalSettings.ZERO_TOL);
105: }
106:
107: public boolean equals(DoubleSparseMatrix m, double tol) {
108: if (numRows == m.numRows && numCols == m.numCols) {
109: if (colPos.length != m.colPos.length)
110: return false;
111: for (int i = 1; i < rows.length; i++) {
112: if (rows[i] != m.rows[i])
113: return false;
114: }
115: double sumSqr = 0.0;
116: for (int i = 1; i < colPos.length; i++) {
117: if (colPos[i] != m.colPos[i])
118: return false;
119: double delta = elements[i] - m.elements[i];
120: sumSqr += delta * delta;
121: }
122: return (sumSqr <= tol * tol);
123: } else
124: return false;
125: }
126:
127: /**
128: * Returns a string representing this matrix.
129: */
130: public String toString() {
131: final StringBuffer buf = new StringBuffer(numRows * numCols);
132: for (int i = 0; i < numRows; i++) {
133: for (int j = 0; j < numCols; j++) {
134: buf.append(getElement(i, j));
135: buf.append(' ');
136: }
137: buf.append('\n');
138: }
139: return buf.toString();
140: }
141:
142: /**
143: * Converts this matrix to an integer matrix.
144: * @return an integer matrix
145: */
146: public AbstractIntegerMatrix toIntegerMatrix() {
147: final int ans[][] = new int[numRows][numCols];
148: for (int i = 0; i < numRows; i++) {
149: for (int j = 0; j < numCols; j++)
150: ans[i][j] = Math.round((float) getElement(i, j));
151: }
152: return new IntegerMatrix(ans);
153: }
154:
155: /**
156: * Converts this matrix to a complex matrix.
157: * @return a complex matrix
158: */
159: public AbstractComplexMatrix toComplexMatrix() {
160: final double arrayRe[][] = new double[numRows][numCols];
161: for (int i = 0; i < numRows; i++) {
162: for (int j = 0; j < numCols; j++)
163: arrayRe[i][j] = getElement(i, j);
164: }
165: return new ComplexMatrix(arrayRe, new double[numRows][numCols]);
166: }
167:
168: /**
169: * Returns an element of the matrix.
170: * @param i row index of the element
171: * @param j column index of the element
172: * @exception MatrixDimensionException If attempting to access an invalid element.
173: */
174: public double getElement(final int i, final int j) {
175: if (i >= 0 && i < numRows && j >= 0 && j < numCols) {
176: for (int k = rows[i]; k < rows[i + 1]; k++) {
177: if (colPos[k] == j)
178: return elements[k];
179: }
180: return 0.0;
181: } else
182: throw new MatrixDimensionException(getInvalidElementMsg(i,
183: j));
184: }
185:
186: /**
187: * Sets the value of an element of the matrix.
188: * @param i row index of the element
189: * @param j column index of the element
190: * @param x a number
191: * @exception MatrixDimensionException If attempting to access an invalid element.
192: */
193: public void setElement(final int i, final int j, final double x) {
194: if (i >= 0 && i < numRows && j >= 0 && j < numCols) {
195: if (Math.abs(x) <= GlobalSettings.ZERO_TOL)
196: return;
197: for (int k = rows[i]; k < rows[i + 1]; k++) {
198: if (colPos[k] == j) {
199: elements[k] = x;
200: return;
201: }
202: }
203: final double oldMatrix[] = elements;
204: final int oldColPos[] = colPos;
205: elements = new double[oldMatrix.length + 1];
206: colPos = new int[oldColPos.length + 1];
207: System.arraycopy(oldMatrix, 0, elements, 0, rows[i]);
208: System.arraycopy(oldColPos, 0, colPos, 0, rows[i]);
209: int k;
210: for (k = rows[i]; k < rows[i + 1] && oldColPos[k] < j; k++) {
211: elements[k] = oldMatrix[k];
212: colPos[k] = oldColPos[k];
213: }
214: elements[k] = x;
215: colPos[k] = j;
216: System.arraycopy(oldMatrix, k, elements, k + 1,
217: oldMatrix.length - k);
218: System.arraycopy(oldColPos, k, colPos, k + 1,
219: oldColPos.length - k);
220: for (k = i + 1; k < rows.length; k++)
221: rows[k]++;
222: } else
223: throw new MatrixDimensionException(getInvalidElementMsg(i,
224: j));
225: }
226:
227: /**
228: * Returns the l<sup><img border=0 alt="infinity" src="doc-files/infinity.gif"></sup>-norm.
229: */
230: public double infNorm() {
231: double result = 0.0, tmpResult;
232: for (int i = 0; i < numRows; i++) {
233: tmpResult = 0.0;
234: for (int j = rows[i]; j < rows[i + 1]; j++)
235: tmpResult += Math.abs(elements[j]);
236: if (tmpResult > result)
237: result = tmpResult;
238: }
239: return result;
240: }
241:
242: /**
243: * Returns the Frobenius (l<sup>2</sup>) norm.
244: */
245: public double frobeniusNorm() {
246: double result = 0.0;
247: for (int i = 0; i < colPos.length; i++)
248: result += elements[i] * elements[i];
249: return Math.sqrt(result);
250: }
251:
252: //============
253: // OPERATIONS
254: //============
255:
256: // ADDITION
257:
258: /**
259: * Returns the addition of this matrix and another.
260: * @param m a double matrix
261: * @exception MatrixDimensionException If the matrices are different sizes.
262: */
263: public AbstractDoubleMatrix add(final AbstractDoubleMatrix m) {
264: if (m instanceof DoubleSparseMatrix)
265: return add((DoubleSparseMatrix) m);
266: if (m instanceof DoubleMatrix)
267: return add((DoubleMatrix) m);
268:
269: if (numRows == m.rows() && numCols == m.columns()) {
270: final double array[][] = new double[numRows][numCols];
271: for (int i = 0; i < numRows; i++) {
272: for (int j = rows[i]; j < rows[i + 1]; j++)
273: array[i][colPos[j]] = elements[j];
274: array[i][0] += m.getElement(i, 0);
275: for (int j = 1; j < numCols; j++)
276: array[i][j] += m.getElement(i, j);
277: }
278: return new DoubleMatrix(array);
279: } else {
280: throw new MatrixDimensionException(
281: "Matrices are different sizes.");
282: }
283: }
284:
285: public DoubleMatrix add(final DoubleMatrix m) {
286: if (numRows == m.numRows && numCols == m.numCols) {
287: final double array[][] = new double[numRows][numCols];
288: for (int i = 0; i < numRows; i++) {
289: for (int j = rows[i]; j < rows[i + 1]; j++)
290: array[i][colPos[j]] = elements[j];
291: array[i][0] += m.matrix[i][0];
292: for (int j = 1; j < numCols; j++)
293: array[i][j] += m.matrix[i][j];
294: }
295: return new DoubleMatrix(array);
296: } else
297: throw new MatrixDimensionException(
298: "Matrices are different sizes.");
299: }
300:
301: /**
302: * Returns the addition of this matrix and another.
303: * @param m a double sparse matrix
304: * @exception MatrixDimensionException If the matrices are different sizes.
305: */
306: public DoubleSparseMatrix add(final DoubleSparseMatrix m) {
307: if (numRows == m.numRows && numCols == m.numCols) {
308: DoubleSparseMatrix ans = new DoubleSparseMatrix(numRows,
309: numCols);
310: for (int i = 0; i < numRows; i++) {
311: for (int j = 0; j < numCols; j++)
312: ans.setElement(i, j, getElement(i, j)
313: + m.getElement(i, j));
314: }
315: return ans;
316: } else
317: throw new MatrixDimensionException(
318: "Matrices are different sizes.");
319: }
320:
321: // SUBTRACTION
322:
323: /**
324: * Returns the subtraction of this matrix and another.
325: * @param m a double matrix
326: * @exception MatrixDimensionException If the matrices are different sizes.
327: */
328: public AbstractDoubleMatrix subtract(final AbstractDoubleMatrix m) {
329: if (m instanceof DoubleSparseMatrix)
330: return subtract((DoubleSparseMatrix) m);
331: if (m instanceof DoubleMatrix)
332: return subtract((DoubleMatrix) m);
333:
334: if (numRows == m.rows() && numCols == m.columns()) {
335: final double array[][] = new double[numRows][numCols];
336: for (int i = 0; i < numRows; i++) {
337: for (int j = rows[i]; j < rows[i + 1]; j++)
338: array[i][colPos[j]] = elements[j];
339: array[i][0] -= m.getElement(i, 0);
340: for (int j = 1; j < numCols; j++)
341: array[i][j] -= m.getElement(i, j);
342: }
343: return new DoubleMatrix(array);
344: } else {
345: throw new MatrixDimensionException(
346: "Matrices are different sizes.");
347: }
348: }
349:
350: public DoubleMatrix subtract(final DoubleMatrix m) {
351: if (numRows == m.numRows && numCols == m.numCols) {
352: final double array[][] = new double[numRows][numCols];
353: for (int i = 0; i < numRows; i++) {
354: for (int j = rows[i]; j < rows[i + 1]; j++)
355: array[i][colPos[j]] = elements[j];
356: array[i][0] -= m.matrix[i][0];
357: for (int j = 1; j < numCols; j++)
358: array[i][j] -= m.matrix[i][j];
359: }
360: return new DoubleMatrix(array);
361: } else
362: throw new MatrixDimensionException(
363: "Matrices are different sizes.");
364: }
365:
366: /**
367: * Returns the addition of this matrix and another.
368: * @param m a double sparse matrix
369: * @exception MatrixDimensionException If the matrices are different sizes.
370: */
371: public DoubleSparseMatrix subtract(final DoubleSparseMatrix m) {
372: if (numRows == m.numRows && numCols == m.numCols) {
373: DoubleSparseMatrix ans = new DoubleSparseMatrix(numRows,
374: numCols);
375: for (int i = 0; i < numRows; i++) {
376: for (int j = 0; j < numCols; j++)
377: ans.setElement(i, j, getElement(i, j)
378: - m.getElement(i, j));
379: }
380: return ans;
381: } else
382: throw new MatrixDimensionException(
383: "Matrices are different sizes.");
384: }
385:
386: // SCALAR MULTIPLICATION
387:
388: /**
389: * Returns the multiplication of this matrix by a scalar.
390: * @param x a double
391: * @return a double sparse matrix
392: */
393: public AbstractDoubleMatrix scalarMultiply(final double x) {
394: final DoubleSparseMatrix ans = new DoubleSparseMatrix(numRows,
395: numCols);
396: ans.elements = new double[elements.length];
397: ans.colPos = new int[colPos.length];
398: System.arraycopy(colPos, 0, ans.colPos, 0, colPos.length);
399: System.arraycopy(rows, 0, ans.rows, 0, rows.length);
400: for (int i = 0; i < colPos.length; i++)
401: ans.elements[i] = x * elements[i];
402: return ans;
403: }
404:
405: public AbstractDoubleMatrix scalarDivide(final double x) {
406: final DoubleSparseMatrix ans = new DoubleSparseMatrix(numRows,
407: numCols);
408: ans.elements = new double[elements.length];
409: ans.colPos = new int[colPos.length];
410: System.arraycopy(colPos, 0, ans.colPos, 0, colPos.length);
411: System.arraycopy(rows, 0, ans.rows, 0, rows.length);
412: for (int i = 0; i < colPos.length; i++)
413: ans.elements[i] = elements[i] / x;
414: return ans;
415: }
416:
417: // SCALAR PRODUCT
418:
419: /**
420: * Returns the scalar product of this matrix and another.
421: * @param m a double matrix.
422: * @exception MatrixDimensionException If the matrices are different sizes.
423: */
424: public double scalarProduct(final AbstractDoubleMatrix m) {
425: if (m instanceof DoubleMatrix)
426: return scalarProduct((DoubleMatrix) m);
427:
428: if (numRows == m.numRows && numCols == m.numCols) {
429: double ans = 0.0;
430: for (int i = 0; i < numRows; i++) {
431: for (int j = rows[i]; j < rows[i + 1]; j++)
432: ans += elements[j] * m.getElement(i, colPos[j]);
433: }
434: return ans;
435: } else
436: throw new MatrixDimensionException(
437: "Matrices are different sizes.");
438: }
439:
440: public double scalarProduct(final DoubleMatrix m) {
441: if (numRows == m.numRows && numCols == m.numCols) {
442: double ans = 0.0;
443: for (int i = 0; i < numRows; i++) {
444: for (int j = rows[i]; j < rows[i + 1]; j++)
445: ans += elements[j] * m.matrix[i][colPos[j]];
446: }
447: return ans;
448: } else
449: throw new MatrixDimensionException(
450: "Matrices are different sizes.");
451: }
452:
453: // MATRIX MULTIPLICATION
454:
455: /**
456: * Returns the multiplication of a vector by this matrix.
457: * @param v a double vector
458: * @exception DimensionException If the matrix and vector are incompatible.
459: */
460: public AbstractDoubleVector multiply(final AbstractDoubleVector v) {
461: if (numCols == v.dimension()) {
462: final double array[] = new double[numRows];
463: for (int i = 0; i < numRows; i++) {
464: for (int j = rows[i]; j < rows[i + 1]; j++)
465: array[i] += elements[j] * v.getComponent(colPos[j]);
466: }
467: return new DoubleVector(array);
468: } else
469: throw new DimensionException(
470: "Matrix and vector are incompatible.");
471: }
472:
473: /**
474: * Returns the multiplication of this matrix and another.
475: * @param m a double matrix
476: * @exception MatrixDimensionException If the matrices are incompatible.
477: */
478: public AbstractDoubleMatrix multiply(final AbstractDoubleMatrix m) {
479: if (m instanceof DoubleSparseMatrix)
480: return multiply((DoubleSparseMatrix) m);
481: if (m instanceof DoubleMatrix)
482: return multiply((DoubleMatrix) m);
483:
484: if (numCols == m.numRows) {
485: final double array[][] = new double[numRows][m.numCols];
486: for (int j = 0; j < numRows; j++) {
487: for (int k = 0; k < m.numCols; k++) {
488: for (int n = rows[j]; n < rows[j + 1]; n++)
489: array[j][k] += elements[n]
490: * m.getElement(colPos[n], k);
491: }
492: }
493: if (numRows == m.numCols)
494: return new DoubleSquareMatrix(array);
495: else
496: return new DoubleMatrix(array);
497: } else
498: throw new MatrixDimensionException("Incompatible matrices.");
499: }
500:
501: public AbstractDoubleMatrix multiply(final DoubleMatrix m) {
502: if (numCols == m.numRows) {
503: final double array[][] = new double[numRows][m.numCols];
504: for (int j = 0; j < numRows; j++) {
505: for (int k = 0; k < m.numCols; k++) {
506: for (int n = rows[j]; n < rows[j + 1]; n++)
507: array[j][k] += elements[n]
508: * m.matrix[colPos[n]][k];
509: }
510: }
511: if (numRows == m.numCols)
512: return new DoubleSquareMatrix(array);
513: else
514: return new DoubleMatrix(array);
515: } else
516: throw new MatrixDimensionException("Incompatible matrices.");
517: }
518:
519: /**
520: * Returns the multiplication of this matrix and another.
521: * @param m a double sparse matrix
522: * @exception MatrixDimensionException If the matrices are incompatible.
523: */
524: public AbstractDoubleMatrix multiply(final DoubleSparseMatrix m) {
525: if (numCols == m.numRows) {
526: AbstractDoubleMatrix ans;
527: if (numRows == m.numCols)
528: ans = new DoubleSparseSquareMatrix(numRows);
529: else
530: ans = new DoubleSparseMatrix(numRows, m.numCols);
531: for (int j = 0; j < ans.numRows; j++) {
532: for (int k = 0; k < ans.numCols; k++) {
533: double tmp = 0.0;
534: for (int n = rows[j]; n < rows[j + 1]; n++)
535: tmp += elements[n] * m.getElement(colPos[n], k);
536: ans.setElement(j, k, tmp);
537: }
538: }
539: return ans;
540: } else
541: throw new MatrixDimensionException("Incompatible matrices.");
542: }
543:
544: // TRANSPOSE
545:
546: /**
547: * Returns the transpose of this matrix.
548: * @return a double sparse matrix
549: */
550: public Matrix transpose() {
551: final DoubleSparseMatrix ans = new DoubleSparseMatrix(numCols,
552: numRows);
553: for (int i = 0; i < numRows; i++) {
554: ans.setElement(0, i, getElement(i, 0));
555: for (int j = 1; j < numCols; j++)
556: ans.setElement(j, i, getElement(i, j));
557: }
558: return ans;
559: }
560:
561: // MAP ELEMENTS
562:
563: /**
564: * Applies a function on all the matrix elements.
565: * @param f a user-defined function
566: * @return a double sparse matrix
567: */
568: public AbstractDoubleMatrix mapElements(final Mapping f) {
569: final DoubleSparseMatrix ans = new DoubleSparseMatrix(numRows,
570: numCols);
571: ans.elements = new double[elements.length];
572: ans.colPos = new int[colPos.length];
573: System.arraycopy(colPos, 0, ans.colPos, 0, colPos.length);
574: System.arraycopy(rows, 0, ans.rows, 0, rows.length);
575: for (int i = 0; i < colPos.length; i++)
576: ans.elements[i] = f.map(elements[i]);
577: return ans;
578: }
579: }
|