Matrix


1   /*
2    * JScience - Java(TM) Tools and Libraries for the Advancement of Sciences.
3    * Copyright (C) 2006 - JScience (http://jscience.org/)
4    * All rights reserved.
5    * 
6    * Permission to use, copy, modify, and distribute this software is
7    * freely granted, provided that this notice is preserved.
8    */
9   package org.jscience.mathematics.vectors;
10  
11  import java.util.Comparator  ;
12  
13  import javolution.lang.Immutable;
14  import javolution.lang.MathLib;
15  import javolution.text.Text;
16  import javolution.text.TextBuilder;
17  import javolution.context.PoolContext;
18  import javolution.context.RealtimeObject;
19  import javolution.xml.XMLFormat;
20  import javolution.xml.stream.XMLStreamException;
21  
22  import org.jscience.mathematics.numbers.Complex;
23  import org.jscience.mathematics.numbers.Float64;
24  import org.jscience.mathematics.structures.Field;
25  import org.jscience.mathematics.structures.Ring;
26  import org.jscience.mathematics.structures.VectorSpace;
27  
28  /**
29   * <p> This class represents a rectangular table of elements of a ring-like 
30   *     algebraic structure.</p>
31   *     
32   * <p> Instances of this class can be used to resolve system of linear equations
33   *     involving <i>any kind</i> of {@link Field Field} elements
34   *     (e.g. {@link org.jscience.mathematics.numbers.Real Real}, 
35   *     {@link org.jscience.mathematics.numbers.Complex Complex}, 
36   *     {@link org.jscience.physics.measures.Measure Measure&lt;?&gt;},
37   *     {@link org.jscience.mathematics.functions.Function Function}, etc).
38   *     For example:[code]
39   *        // Creates a dense matrix (2x2) of Rational numbers.
40   *        DenseMatrix<Rational> M = DenseMatrix.valueOf(
41   *            { Rational.valueOf(23, 45), Rational.valueOf(33, 75) },
42   *            { Rational.valueOf(15, 31), Rational.valueOf(-20, 45)});
43   *            
44   *        // Creates a sparse matrix (16x2) of Real numbers.
45   *        SparseMatrix<Real> M = SparseMatrix.valueOf(
46   *            SparseVector.valueOf(16, Real.ZERO, 0, Real.valueOf(5)),
47   *            SparseVector.valueOf(16, Real.ZERO, 15, Real.valueOf(-3)));
48   *            
49   *        // Creates a floating-point (64 bits) matrix (3x2).
50   *        Float64Matrix M = Float64Matrix.valueOf(
51   *           {{ 1.0, 2.0, 3.0}, { 4.0, 5.0, 6.0}});
52   *            
53   *        // Creates a complex single column matrix (1x2).
54   *        ComplexMatrix M = ComplexMatrix.valueOf(
55   *           {{ Complex.valueOf(1.0, 2.0), Complex.valueOf(4.0, 5.0)}}).transpose();
56   *            
57   *        // Creates an identity matrix (2x2) for modulo integer.
58   *        SparseMatrix<ModuloInteger> IDENTITY = SparseMatrix.valueOf(
59   *           DenseVector.valueOf(ModuloInteger.ONE, ModuloInteger.ONE), ModuloInteger.ZERO);
60   *     [/code]</p>
61   *     
62   * <p> Non-commutative field multiplication is supported. Invertible square 
63   *     matrices may form a non-commutative field (also called a division
64   *     ring). In which case this class may be used to resolve system of linear
65   *     equations with matrix coefficients.</p>
66   *     
67   * <p> Implementation Note: Matrices may use {@link 
68   *     javolution.context.PoolContext PoolContext} and {@link 
69   *     javolution.context.ConcurrentContext ConcurrentContext} in order to 
70   *     minimize heap allocation and accelerate calculations on multi-core 
71   *     systems.</p>
72   * 
73   * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
74   * @version 3.3, December 24, 2006
75   * @see <a HREF="http://en.wikipedia.org/wiki/Matrix_%28mathematics%29">
76   *      Wikipedia: Matrix (mathematics)</a>
77   */
78  public abstract class Matrix<F extends Field<F>> extends RealtimeObject
79          implements VectorSpace<Matrix<F>, F>, Ring<Matrix<F>>, Immutable {
80  
81      /**
82       * Holds the default XML representation for matrices. For example:[code]
83       *    <DenseMatrix rows="2" columns="2">
84       *        <Complex real="1.0" imaginary="0.0" />
85       *        <Complex real="0.0" imaginary="1.0" />
86       *        <Complex real="0.0" imaginary="0.4" />
87       *        <Complex real="-5.0" imaginary="-1.0" />
88       *    </DenseMatrix>[/code]
89       */
90      protected static final XMLFormat<Matrix> XML = new XMLFormat<Matrix>(
91              Matrix.class) {
92  
93          @Override  
94          public void read(InputElement xml, Matrix M) throws XMLStreamException {
95              // Nothing to do.
96          }
97  
98          @Override  
99          public void write(Matrix M, OutputElement xml)
100                 throws XMLStreamException {
101             final int m = M.getNumberOfRows();
102             final int n = M.getNumberOfColumns();
103             xml.setAttribute("rows", m);
104             xml.setAttribute("columns", n);
105             for (int i = 0; i < m; i++) {
106                 for (int j = 0; j < n; j++) {
107                     xml.add(M.get(i, j));
108                 }
109             }
110         }
111     };
112 
113     /**
114      * Returns a dense matrix from the specified 2-dimensional array
115      * (convenience method).
116      * 
117      * @param elements this matrix elements.
118      * @return the matrix having the specified elements.
119      * @throws DimensionException if rows have different length.
120      * @deprecated Since 3.3 - Replaced by {@link DenseMatrix#valueOf(Field[][])} 
121      */
122     public static <F extends Field<F>> Matrix<F> valueOf(F[][] elements) {
123         return DenseMatrix.valueOf(elements);
124     }
125 
126     /**
127      * Returns a dense matrix from a 2-dimensional array of <code>double</code>
128      * values (convenience method).
129      *
130      * @param  values the array of <code>double</code> values.
131      * @return the matrix having the specified elements.
132      * @throws DimensionException if rows have different length.
133      * @deprecated Since 3.3 - Replaced by {@link Float64Matrix#valueOf(double[][])} 
134      */
135     public static Matrix<Float64> valueOf(double[][] values) {
136         return Float64Matrix.valueOf(values);
137     }
138 
139     /**
140      * Returns a dense matrix from a 2-dimensional array of {@link Complex 
141      * complex} numbers (convenience method). 
142      *
143      * @param  elements the array of complex elements.
144      * @return the matrix having the specified elements.
145      * @throws DimensionException if rows have different length.
146      * @deprecated Since 3.3 - Replaced by {@link ComplexMatrix#valueOf(Complex[][])} 
147      */
148     public static Matrix<Complex> valueOf(Complex[][] elements) {
149         return ComplexMatrix.valueOf(elements);
150     }
151 
152     /**
153      * Returns the sparse square matrix having the specified diagonal
154      * vector.          
155      *
156      * @param  diagonal the diagonal vector.
157      * @param  zero value of non-diagonal elements.
158      * @return a square matrix with <code>diagonal</code> on the diagonal and
159      *         <code>zero</code> elsewhere.
160      * @deprecated Since 3.3 - Replaced by {@link SparseMatrix#valueOf(Vector, Field)} 
161      */
162     public static <F extends Field<F>> Matrix<F> valueOf(Vector<F> diagonal, 
163             F zero) {
164         return SparseMatrix.valueOf(diagonal, zero);
165     }
166 
167     /**
168      * Default constructor (for sub-classes).
169      */
170     protected Matrix() {
171     }
172 
173     /**
174      * Returns the number of rows <code>m</code> for this matrix.
175      *
176      * @return m, the number of rows.
177      */
178     public abstract int getNumberOfRows();
179 
180     /**
181      * Returns the number of columns <code>n</code> for this matrix.
182      *
183      * @return n, the number of columns.
184      */
185     public abstract int getNumberOfColumns();
186  
187     /**
188      * Returns a single element from this matrix.
189      *
190      * @param  i the row index (range [0..m[).
191      * @param  j the column index (range [0..n[).
192      * @return the element read at [i,j].
193      * @throws IndexOutOfBoundsException <code>
194      *         ((i < 0) || (i >= m)) || ((j < 0) || (j >= n))</code>
195      */
196     public abstract F get(int i, int j);
197 
198     /**
199      * Returns the row identified by the specified index in this matrix.
200      *
201      * @param  i the row index (range [0..m[).
202      * @return the vector holding the specified row.
203      * @throws IndexOutOfBoundsException <code>(i < 0) || (i >= m)</code>
204      */
205     public abstract Vector<F> getRow(int i);
206 
207     /**
208      * Returns the column identified by the specified index in this matrix.
209      *
210      * @param  j the column index (range [0..n[).
211      * @return the vector holding the specified column.
212      * @throws IndexOutOfBoundsException <code>(j < 0) || (j >= n)</code>
213      */
214     public abstract Vector<F> getColumn(int j);
215 
216     /**
217      * Returns the diagonal vector.
218      *
219      * @return the vector holding the diagonal elements.
220      */
221     public abstract Vector<F> getDiagonal();
222 
223     /**
224      * Returns the negation of this matrix.
225      *
226      * @return <code>-this</code>.
227      */
228     public abstract Matrix<F> opposite();
229 
230     /**
231      * Returns the sum of this matrix with the one specified.
232      *
233      * @param   that the matrix to be added.
234      * @return  <code>this + that</code>.
235      * @throws  DimensionException matrices's dimensions are different.
236      */
237     public abstract Matrix<F> plus(Matrix<F> that);
238 
239     /**
240      * Returns the difference between this matrix and the one specified.
241      *
242      * @param  that the matrix to be subtracted.
243      * @return <code>this - that</code>.
244      * @throws  DimensionException matrices's dimensions are different.
245      */
246     public Matrix<F> minus(Matrix<F> that) {
247         return this.plus(that.opposite());
248     }
249 
250     /**
251      * Returns the product of this matrix by the specified factor.
252      *
253      * @param  k the coefficient multiplier.
254      * @return <code>this · k</code>
255      */
256     public abstract Matrix<F> times(F k);
257     
258     /**
259      * Returns the product of this matrix by the specified vector.
260      *
261      * @param  v the vector.
262      * @return <code>this · v</code>
263      * @throws DimensionException if <code>
264      *         v.getDimension() != this.getNumberOfColumns()<code>
265      */
266     public abstract Vector<F> times(Vector<F> v);
267     
268     /**
269      * Returns the product of this matrix with the one specified.
270      *
271      * @param  that the matrix multiplier.
272      * @return <code>this · that</code>.
273      * @throws DimensionException if <code>
274      *         this.getNumberOfColumns() != that.getNumberOfRows()</code>.
275      */
276     public abstract Matrix<F> times(Matrix<F> that);    
277 
278     /**
279      * Returns the inverse of this matrix (must be square).
280      *
281      * @return <code>1 / this</code>
282      * @throws DimensionException if this matrix is not square.
283      */
284     public abstract Matrix<F> inverse();
285 
286     /**
287      * Returns this matrix divided by the one specified.
288      *
289      * @param  that the matrix divisor.
290      * @return <code>this / that</code>.
291      * @throws DimensionException if that matrix is not square or dimensions 
292      *         do not match.
293      */
294     public Matrix<F> divide(Matrix<F> that) {
295         return this.times(that.inverse());
296     }
297 
298     /**
299      * Returns the inverse or pseudo-inverse if this matrix if not square.
300      *
301      * <p> Note: To resolve the equation <code>A * X = B</code>,
302      *           it is usually faster to calculate <code>A.lu().solve(B)</code>
303      *           rather than <code>A.inverse().times(B)</code>.</p>
304      *
305      * @return  the inverse or pseudo-inverse of this matrix.
306      */
307     public Matrix<F> pseudoInverse() {
308         if (isSquare())
309             return this.inverse();
310         Matrix<F> thisTranspose = this.transpose();
311         return (thisTranspose.times(this)).inverse().times(thisTranspose);
312     }
313 
314     /**
315      * Returns the determinant of this matrix.
316      *
317      * @return this matrix determinant.
318      * @throws DimensionException if this matrix is not square.
319      */
320     public abstract F determinant();
321 
322     /**
323      * Returns the transpose of this matrix.
324      *
325      * @return <code>A'</code>.
326      */
327     public abstract Matrix<F> transpose();
328 
329     /**
330      * Returns the cofactor of an element in this matrix. It is the value
331      * obtained by evaluating the determinant formed by the elements not in
332      * that particular row or column.
333      *
334      * @param  i the row index.
335      * @param  j the column index.
336      * @return the cofactor of <code>THIS[i,j]</code>.
337      * @throws DimensionException matrix is not square or its dimension
338      *         is less than 2.
339      */
340     public abstract F cofactor(int i, int j);
341 
342     /**
343      * Returns the adjoint of this matrix. It is obtained by replacing each
344      * element in this matrix with its cofactor and applying a + or - sign
345      * according (-1)**(i+j), and then finding the transpose of the resulting
346      * matrix.
347      *
348      * @return the adjoint of this matrix.
349      * @throws DimensionException if this matrix is not square or if
350      *         its dimension is less than 2.
351      */
352     public abstract Matrix<F> adjoint();
353     
354     /**
355      * Indicates if this matrix is square.
356      *
357      * @return <code>getNumberOfRows() == getNumberOfColumns()</code>
358      */
359     public boolean isSquare() {
360         return getNumberOfRows() == getNumberOfColumns();
361     }
362 
363     /**
364      * Solves this matrix for the specified vector (returns <code>x</code>
365      * such as <code>this · x = y</code>).
366      * 
367      * @param  y the vector for which the solution is calculated.
368      * @return <code>x</code> such as <code>this · x = y</code>
369      * @throws DimensionException if that matrix is not square or dimensions 
370      *         do not match.
371      */
372     public Vector<F> solve(Vector<F> y) {
373         DenseMatrix<F> M = DenseMatrix.newInstance(y.getDimension(), true);
374         M._rows.add(DenseVector.valueOf(y));
375         return solve(M).getColumn(0);
376     }
377 
378     /**
379      * Solves this matrix for the specified matrix (returns <code>x</code>
380      * such as <code>this · x = y</code>).
381      * 
382      * @param  y the matrix for which the solution is calculated.
383      * @return <code>x</code> such as <code>this · x = y</code>
384      * @throws DimensionException if that matrix is not square or dimensions 
385      *         do not match.
386      */
387     public Matrix<F> solve(Matrix<F> y) {
388         return LUDecomposition.valueOf(this).solve(y); // Default implementation.
389     }
390 
391     /**
392      * Returns this matrix raised at the specified exponent.
393      *
394      * @param  exp the exponent.
395      * @return <code>this<sup>exp</sup></code>
396      * @throws DimensionException if this matrix is not square.
397      */
398     public Matrix<F> pow(int exp) {
399         if (exp > 0) {
400             PoolContext.enter();
401             try {
402                 Matrix<F> pow2 = this;
403                 Matrix<F> result = null;
404                 while (exp >= 1) { // Iteration.
405                     if ((exp & 1) == 1) {
406                         result = (result == null) ? pow2 : result.times(pow2);
407                     }
408                     pow2 = pow2.times(pow2);
409                     exp >>>= 1;
410                 }
411                 result.export();
412                 return result;
413             } finally {
414                 PoolContext.exit();
415             }
416         } else if (exp == 0) {
417             return this.times(this.inverse()); // Identity.
418         } else {
419             return this.pow(-exp).inverse();
420         }
421     }
422 
423     /**
424      * Returns the trace of this matrix.
425      *
426      * @return the sum of the diagonal elements.
427      */
428     public F trace() {
429         F sum = this.get(0, 0);
430         for (int i = MathLib.min(getNumberOfColumns(), getNumberOfRows()); --i > 0;) {
431             sum = sum.plus(get(i, i));
432         }
433         return sum;
434     }
435 
436     /**
437      * Returns the linear algebraic matrix tensor product of this matrix
438      * and another (Kronecker product). The default implementation returns
439      * a {@link DenseMatrix}. 
440      *
441      * @param  that the second matrix.
442      * @return <code>this &otimes; that</code>
443      * @see    <a HREF="http://en.wikipedia.org/wiki/Kronecker_product">
444      *         Wikipedia: Kronecker Product</a>
445      */
446     public abstract Matrix<F> tensor(Matrix<F> that);
447 
448     /**
449      * Returns the vectorization of this matrix. The vectorization of 
450      * a matrix is the column vector obtain by stacking the columns of the
451      * matrix on top of one another. The default implementation returns 
452      * a {@link DenseVector}.
453      *
454      * @return the vectorization of this matrix.
455      * @see    <a HREF="http://en.wikipedia.org/wiki/Vectorization_%28mathematics%29">
456      *         Wikipedia: Vectorization.</a>
457      */
458     public abstract Vector<F> vectorization();
459     
460     /**
461      * Returns the text representation of this matrix.
462      *
463      * @return the text representation of this matrix.
464      */
465     public Text toText() {
466         final int m = this.getNumberOfRows();
467         final int n = this.getNumberOfColumns();
468         TextBuilder tmp = TextBuilder.newInstance();
469         tmp.append('{');
470         for (int i = 0; i < m; i++) {
471             tmp.append('{');
472             for (int j = 0; j < n; j++) {
473                 tmp.append(get(i, j).toText());
474                 if (j != n - 1) {
475                     tmp.append(", ");
476                 }
477             }
478             if (i != m - 1) {
479                 tmp.append("},\n");
480             }
481         }
482         tmp.append("}}");
483         Text txt = tmp.toText();
484         TextBuilder.recycle(tmp);
485         return txt;
486     }
487 
488     /**
489      * Indicates if this matrix can be considered equals to the one 
490      * specified using the specified comparator when testing for 
491      * element equality. The specified comparator may allow for some 
492      * tolerance in the difference between the matrix elements.
493      *
494      * @param  that the matrix to compare for equality.
495      * @param  cmp the comparator to use when testing for element equality.
496      * @return <code>true</code> if this matrix and the specified matrix are
497      *         both matrices with equal elements according to the specified
498      *         comparator; <code>false</code> otherwise.
499      */
500     public boolean equals(Matrix<F> that, Comparator  <F> cmp) {
501         if (this == that)
502             return true;
503         final int m = this.getNumberOfRows();
504         final int n = this.getNumberOfColumns();
505         if ((that.getNumberOfRows() != m) || (that.getNumberOfColumns() != n))
506             return false;
507         for (int i = m; --i >= 0;) {
508             for (int j = n; --j >= 0;) {
509                 if (cmp.compare(this.get(i, j), that.get(i, j)) != 0)
510                     return false;
511             }
512         }
513         return true;
514     }
515 
516     /**
517      * Indicates if this matrix is strictly equal to the object specified.
518      *
519      * @param  that the object to compare for equality.
520      * @return <code>true</code> if this matrix and the specified object are
521      *         both matrices with equal elements; <code>false</code> otherwise.
522      * @see    #equals(Matrix, Comparator)
523      */
524     public boolean equals(Object   that) {
525         if (this == that)
526             return true;
527         if (!(that instanceof Matrix))
528             return false;
529         final int m = this.getNumberOfRows();
530         final int n = this.getNumberOfColumns();
531         Matrix M = (Matrix) that;
532         if ((M.getNumberOfRows() != m) || (M.getNumberOfColumns() != n))
533             return false;
534         for (int i = m; --i >= 0;) {
535             for (int j = n; --j >= 0;) {
536                 if (!this.get(i, j).equals(M.get(i, j)))
537                     return false;
538             }
539         }
540         return true;
541     }
542 
543     /**
544      * Returns a hash code value for this matrix.
545      * Equals objects have equal hash codes.
546      *
547      * @return this matrix hash code value.
548      * @see    #equals
549      */
550     public int hashCode() {
551         final int m = this.getNumberOfRows();
552         final int n = this.getNumberOfColumns();
553         int code = 0;
554         for (int i = m; --i >= 0;) {
555             for (int j = n; --j >= 0;) {
556                 code += get(i, j).hashCode();
557             }
558         }
559         return code;
560     }
561     
562 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags