DenseMatrix


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.Iterator  ;
12  import java.util.List  ;
13  
14  import javolution.context.ConcurrentContext;
15  import javolution.lang.MathLib;
16  import javolution.util.FastTable;
17  import javolution.util.Index;
18  
19  import org.jscience.mathematics.structures.Field;
20  
21  /**
22   * <p> This class represents a matrix made of {@link DenseVector dense
23   *     vectors} (as rows). To create a dense matrix made of column vectors the 
24   *     {@link #transpose} method can be used. 
25   *     For example:[code]
26   *        DenseVector<Rational> column0 = DenseVector.valueOf(...);
27   *        DenseVector<Rational> column1 = DenseVector.valueOf(...);
28   *        DenseMatrix<Rational> M = DenseMatrix.valueOf(column0, column1).transpose();
29   *     [/code]</p>
30   * <p> As for any concrete {@link org.jscience.mathematics.structures.Structure
31   *     structure}, this class is declared <code>final</code> (otherwise most
32   *     operations would have to be overridden to return the appropriate type).
33   *     Specialized dense matrix should sub-class {@link Matrix} directly.
34   *     For example:[code]
35   *        // Extension through composition.
36   *        final class TriangularMatrix <F extends Field<F>> extends Matrix<F> {
37   *             private DenseMatrix<F> _value; // Possible implementation.
38   *             ...
39   *             public TriangularMatrix opposite() { // Returns the right type.
40   *                 return TriangularMatrix.valueOf(_value.opposite());
41   *             }
42   *             ...
43   *        }[/code]
44   *     </p>   
45   * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
46   * @version 3.3, January 2, 2007
47   */
48  public final class DenseMatrix<F extends Field<F>> extends Matrix<F> {
49  
50      /**
51       * Holds the number of columns n.
52       */
53      int _n;
54  
55      /**
56       * Indicates if this matrix is transposed (the rows are then the columns).
57       */
58      boolean _transposed;
59  
60      /**
61       * Holds this matrix rows (or columns when transposed).
62       */
63      final FastTable<DenseVector<F>> _rows = new FastTable<DenseVector<F>>();
64  
65      /**
66       * Returns a dense matrix from the specified 2-dimensional array.
67       * The first dimension being the row and the second being the column.
68       * 
69       * @param elements this matrix elements.
70       * @return the matrix having the specified elements.
71       * @throws DimensionException if rows have different length.
72       * @see    DenseMatrix 
73       */
74      public static <F extends Field<F>> DenseMatrix<F> valueOf(F[][] elements) {
75          int m = elements.length;
76          int n = elements[0].length;
77          DenseMatrix<F> M = DenseMatrix.newInstance(n, false);
78          for (int i = 0; i < m; i++) {
79              DenseVector<F> row = DenseVector.valueOf(elements[i]);
80              if (row.getDimension() != n)
81                  throw new DimensionException();
82              M._rows.add(row);
83          }
84          return M;
85      }
86  
87      /**
88       * Returns a dense matrix holding the specified row vectors 
89       * (column vectors if {@link #transpose transposed}).
90       *
91       * @param rows the row vectors.
92       * @return the matrix having the specified rows.
93       * @throws DimensionException if the rows do not have the same dimension.
94       */
95      public static <F extends Field<F>> DenseMatrix<F> valueOf(
96              DenseVector<F>... rows) {
97          final int n = rows[0].getDimension();
98          DenseMatrix<F> M = DenseMatrix.newInstance(n, false);
99          for (int i = 0, m = rows.length; i < m; i++) {
100             DenseVector<F> rowi = rows[i];
101             if (rowi.getDimension() != n)
102                 throw new DimensionException(
103                         "All vectors must have the same dimension.");
104             M._rows.add(rowi);
105         }
106         return M;
107     }
108 
109     /**
110      * Returns a dense matrix holding the row vectors from the specified 
111      * collection (column vectors if {@link #transpose transposed}).
112      *
113      * @param rows the list of row vectors.
114      * @return the matrix having the specified rows.
115      * @throws DimensionException if the rows do not have the same dimension.
116      */
117     public static <F extends Field<F>> DenseMatrix<F> valueOf(
118             List  <DenseVector<F>> rows) {
119         final int n = rows.get(0).getDimension();
120         DenseMatrix<F> M = DenseMatrix.newInstance(n, false);
121         Iterator  <DenseVector<F>> iterator = rows.iterator();
122         for (int i = 0, m = rows.size(); i < m; i++) {
123             DenseVector<F> rowi = iterator.next();
124             if (rowi.getDimension() != n)
125                 throw new DimensionException(
126                         "All vectors must have the same dimension.");
127             M._rows.add(rowi);
128         }
129         return M;
130     }
131 
132     /**
133      * Returns a dense matrix equivalent to the specified matrix.
134      *
135      * @param that the matrix to convert.
136      * @return <code>that</code> or a dense matrix holding the same elements
137      *         as the specified matrix.
138      */
139     public static <F extends Field<F>> DenseMatrix<F> valueOf(Matrix<F> that) {
140         if (that instanceof DenseMatrix)
141             return (DenseMatrix<F>) that;
142         int n = that.getNumberOfColumns();
143         int m = that.getNumberOfRows();
144         DenseMatrix<F> M = DenseMatrix.newInstance(n, false);
145         for (int i = 0; i < m; i++) {
146             DenseVector<F> rowi = DenseVector.valueOf(that.getRow(i));
147             M._rows.add(rowi);
148         }
149         return M;
150     }
151 
152     @Override  
153     public int getNumberOfRows() {
154         return _transposed ? _n : _rows.size();
155     }
156 
157     @Override  
158     public int getNumberOfColumns() {
159         return _transposed ? _rows.size() : _n;
160     }
161 
162     @Override  
163     public F get(int i, int j) {
164         return _transposed ? _rows.get(j).get(i) : _rows.get(i).get(j);
165     }
166 
167     @Override  
168     public DenseVector<F> getRow(int i) {
169         if (!_transposed)
170             return _rows.get(i);
171         // Else transposed.
172         int n = _rows.size();
173         int m = _n;
174         if ((i < 0) || (i >= m))
175             throw new DimensionException();
176         DenseVector<F> V = DenseVector.newInstance();
177         for (int j = 0; j < n; j++) {
178             V._elements.add(_rows.get(j).get(i));
179         }
180         return V;
181     }
182 
183     @Override  
184     public DenseVector<F> getColumn(int j) {
185         if (_transposed)
186             return _rows.get(j);
187         int m = _rows.size();
188         if ((j < 0) || (j >= _n))
189             throw new DimensionException();
190         DenseVector<F> V = DenseVector.newInstance();
191         for (int i = 0; i < m; i++) {
192             V._elements.add(_rows.get(i).get(j));
193         }
194         return V;
195     }
196 
197     @Override  
198     public DenseVector<F> getDiagonal() {
199         int m = this.getNumberOfRows();
200         int n = this.getNumberOfColumns();
201         int dimension = MathLib.min(m, n);
202         DenseVector<F> V = DenseVector.newInstance();
203         for (int i = 0; i < dimension; i++) {
204             V._elements.add(this.get(i, i));
205         }
206         return V;
207     }
208 
209     @Override  
210     public DenseMatrix<F> opposite() {
211         DenseMatrix<F> M = DenseMatrix.newInstance(_n, _transposed);
212         for (int i = 0, p = _rows.size(); i < p; i++) {
213             M._rows.add(_rows.get(i).opposite());
214         }
215         return M;
216     }
217 
218     @Override  
219     public DenseMatrix<F> plus(Matrix<F> that) {
220         if (this.getNumberOfRows() != that.getNumberOfRows())
221             throw new DimensionException();
222         DenseMatrix<F> M = DenseMatrix.newInstance(_n, _transposed);
223         for (int i = 0, p = _rows.size(); i < p; i++) {
224             M._rows.add(_rows.get(i).plus(
225                     _transposed ? that.getColumn(i) : that.getRow(i)));
226         }
227         return M;
228     }
229 
230     @Override  
231     public DenseMatrix<F> minus(Matrix<F> that) { // Returns more specialized type.
232         return this.plus(that.opposite());
233     }
234 
235     @Override  
236     public DenseMatrix<F> times(F k) {
237         DenseMatrix<F> M = DenseMatrix.newInstance(_n, _transposed);
238         for (int i = 0, p = _rows.size(); i < p; i++) {
239             M._rows.add(_rows.get(i).times(k));
240         }
241         return M;
242     }
243 
244     @Override  
245     public DenseVector<F> times(Vector<F> v) {
246         if (v.getDimension() != this.getNumberOfColumns())
247             throw new DimensionException();
248         final int m = this.getNumberOfRows();
249         DenseVector<F> V = DenseVector.newInstance();
250         for (int i = 0; i < m; i++) {
251             V._elements.add(this.getRow(i).times(v));
252         }
253         return V;
254     }
255 
256     @Override  
257     public DenseMatrix<F> times(Matrix<F> that) {
258         if (_transposed) // this.inverse().transpose() == this.transpose().inverse()
259             return this.transpose().inverse().transpose();
260         // this is a row matrix.
261         final int m = this.getNumberOfRows();
262         final int p = that.getNumberOfColumns();
263         if (that.getNumberOfRows() != _n)
264             throw new DimensionException();
265         // Creates a mxp matrix in transposed form (p columns vectors of size m)
266         DenseMatrix<F> M = DenseMatrix.newInstance(m, true); // Transposed.
267         multiply(that, Index.valueOf(0), Index.valueOf(p), M._rows);
268         return M;
269     }
270     
271     // Multiplies this row matrix with the columns of the specified matrix.
272     private void multiply(
273             Matrix<F> that, Index startColumn, Index endColumn, FastTable<DenseVector<F>> columnsResult) {
274         final int start = startColumn.intValue();
275         final int end = endColumn.intValue();
276         if (end - start < 32) {  // Direct calculation.
277             final int m = this._rows.size();
278             for (int j = start; j < end; j++) {
279                 Vector<F> thatColj = that.getColumn(j);
280                 DenseVector<F> column = DenseVector.newInstance();
281                 columnsResult.add(column);
282                 for (int i = 0; i < m; i++) {
283                     DenseVector<F> thisRowi = this._rows.get(i);
284                     column._elements.add(thisRowi.times(thatColj));
285                 }
286             }   
287         } else { // Concurrent execution.
288             FastTable<DenseVector<F>> r1 = FastTable.newInstance();
289             FastTable<DenseVector<F>> r2 = FastTable.newInstance();
290             Index half = Index.valueOf((start + end) >> 1);
291             ConcurrentContext.enter();
292             try {
293                 ConcurrentContext.execute(MULTIPLY, this, that, startColumn, half, r1);
294                 ConcurrentContext.execute(MULTIPLY, this, that, half, endColumn, r2);
295             } finally {
296                 ConcurrentContext.exit();
297             }
298             columnsResult.addAll(r1);
299             columnsResult.addAll(r2);
300             FastTable.recycle(r1);
301             FastTable.recycle(r2);
302         }    
303     }
304     private static ConcurrentContext.Logic MULTIPLY = new ConcurrentContext.Logic() {
305         @SuppressWarnings  ("unchecked")
306         public void run() {
307             DenseMatrix _this = getArgument(0);
308             Matrix _that = getArgument(1);
309             Index _startColumn = getArgument(2);
310             Index _endColumn = getArgument(3);
311             FastTable _columnsResult = getArgument(4);
312             _this.multiply(_that, _startColumn, _endColumn, _columnsResult);
313         }
314     };
315 
316     @Override  
317     public DenseMatrix<F> inverse() {
318         if (!isSquare())
319             throw new DimensionException("Matrix not square");
320         return LUDecomposition.valueOf(this).inverse();
321     }
322 
323     @Override  
324     public F determinant() {
325         return LUDecomposition.valueOf(this).determinant();
326     }
327 
328     @Override  
329     public DenseMatrix<F> transpose() {
330         DenseMatrix<F> M = DenseMatrix.newInstance(_n, !_transposed);
331         M._rows.addAll(this._rows);
332         return M;
333     }
334 
335     @Override  
336     public F cofactor(int i, int j) {
337         if (_transposed) {
338             int k = i;
339             i = j;
340             j = k; // Swaps i,j
341         }
342         int m = _rows.size();
343         DenseMatrix<F> M = DenseMatrix.newInstance(m - 1, _transposed);
344         for (int k1 = 0; k1 < m; k1++) {
345             if (k1 == i)
346                 continue;
347             DenseVector<F> row = _rows.get(k1);
348             DenseVector<F> V = DenseVector.newInstance();
349             M._rows.add(V);
350             for (int k2 = 0; k2 < _n; k2++) {
351                 if (k2 == j)
352                     continue;
353                 V._elements.add(row.get(k2));
354             }
355         }
356         return M.determinant();
357     }
358 
359     @Override  
360     public DenseMatrix<F> adjoint() {
361         DenseMatrix<F> M = DenseMatrix.newInstance(_n, _transposed);
362         int m = _rows.size();
363         for (int i = 0; i < m; i++) {
364             DenseVector<F> row = DenseVector.newInstance();
365             M._rows.add(row);
366             for (int j = 0; j < _n; j++) {
367                 F cofactor = _transposed ? cofactor(j, i) : cofactor(i, j);
368                 row._elements.add(((i + j) % 2 == 0) ? cofactor : cofactor
369                         .opposite());
370             }
371         }
372         return M.transpose();
373     }
374 
375     @Override  
376     public Matrix<F> tensor(Matrix<F> that) {
377         final int thism = this.getNumberOfRows();
378         final int thisn = this.getNumberOfColumns();
379         final int thatm = that.getNumberOfRows();
380         final int thatn = that.getNumberOfColumns();
381         int n = thisn * thatn; // Number of columns,
382         int m = thism * thatm; // Number of rows.
383         DenseMatrix<F> M = DenseMatrix.newInstance(n, false);
384         for (int i=0; i < m; i++) { // Row index.
385             final int i_rem_thatm = i % thatm;
386             final int i_div_thatm = i / thatm;
387             DenseVector<F> row = DenseVector.newInstance();
388             M._rows.add(row);
389             for (int j=0; j < thisn; j++) {
390                 F a = this.get(i_div_thatm, j);
391                 for (int k=0; k < thatn; k++) {
392                     row._elements.add(a.times(that.get(i_rem_thatm, k)));
393                 }
394             }
395         }
396         return M;
397     }
398 
399     @Override  
400     public Vector<F> vectorization() {
401         DenseVector<F> V = DenseVector.newInstance();
402         for (int j=0, n = this.getNumberOfColumns(); j < n; j++) {
403             Vector<F> column = this.getColumn(j);
404             for (int i=0, m=column.getDimension(); i < m; i++) {
405                 V._elements.add(column.get(i));
406             }
407         }
408         return V;
409     }
410 
411     @Override  
412     public boolean move(ObjectSpace os) {
413         if (super.move(os)) {
414             // The rows table itself is intrinsic (all final members are)
415             // and implicitely moves with this matrix.
416             // But it may refer to locally/stack allocated vectors which
417             // need to be moved along.
418             for (int i=0, n=_rows.size(); i < n; i++) {
419                 _rows.get(i).move(os);
420             }
421             return true;
422         }
423         return false;
424     }  
425     
426     ///////////////////////////////
427     // Package Private Utilities //
428     ///////////////////////////////
429 
430     void set(int i, int j, F e) {
431         if (_transposed) {
432             _rows.get(j)._elements.set(i, e);
433         } else {
434             _rows.get(i)._elements.set(j, e);
435         }
436     }
437 
438     DenseMatrix<F> copy() {
439         DenseMatrix<F> M = DenseMatrix.newInstance(_n, _transposed);
440         for (int i = 0, m = _rows.size(); i < m; i++) {
441             DenseVector<F> V = DenseVector.newInstance();
442             V._elements.addAll(_rows.get(i)._elements);
443             M._rows.add(V);
444         }
445         return M;
446     }
447 
448     ///////////////////////
449     // Factory creation. //
450     ///////////////////////
451 
452     @SuppressWarnings  ("unchecked")
453     static <F extends Field<F>> DenseMatrix<F> newInstance(int n,
454             boolean transposed) {
455         DenseMatrix<F> M = FACTORY.object();
456         M._n = n;
457         M._transposed = transposed;
458         return M;
459     }
460 
461     private static Factory<DenseMatrix> FACTORY = new Factory<DenseMatrix>() {
462         @Override  
463         protected DenseMatrix create() {
464             return new DenseMatrix();
465         }
466 
467         @Override  
468         protected void cleanup(DenseMatrix matrix) {
469             matrix._rows.reset();
470         }
471     };
472 
473     private DenseMatrix() {
474     }
475 
476     private static final long serialVersionUID = 1L;
477 
478 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags