Source code

001/*
002 * $Id: GenMatrix.java 4125 2012-08-19 19:05:22Z kredel $
003 */
004
005package edu.jas.vector;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.kern.PrettyPrint;
014import edu.jas.structure.AlgebraElem;
015import edu.jas.structure.RingElem;
016
017
018/**
019 * GenMatrix implements a generic matrix algebra over RingElem entries. Matrix
020 * has n columns and m rows over C.
021 * @author Heinz Kredel
022 */
023
024public class GenMatrix<C extends RingElem<C>> implements AlgebraElem<GenMatrix<C>, C> {
025
026
027    private static final Logger logger = Logger.getLogger(GenMatrix.class);
028
029
030    public final GenMatrixRing<C> ring;
031
032
033    public final ArrayList<ArrayList<C>> matrix;
034
035
036    private int hashValue = 0;
037
038
039    /**
040     * Constructor for zero GenMatrix.
041     * @param r matrix ring
042     */
043    public GenMatrix(GenMatrixRing<C> r) {
044        this(r, r.getZERO().matrix);
045    }
046
047
048    /**
049     * Constructor for GenMatrix.
050     * @param r matrix ring
051     * @param m matrix
052     */
053    public GenMatrix(GenMatrixRing<C> r, List<List<C>> m) {
054        ring = r;
055        matrix = new ArrayList<ArrayList<C>>(r.rows);
056        for (List<C> row : m) {
057            ArrayList<C> nr = new ArrayList<C>(row);
058            matrix.add(nr);
059        }
060        logger.info(ring.rows + " x " + ring.cols + " matrix constructed");
061    }
062
063
064    /**
065     * Constructor for GenMatrix.
066     * @param r matrix ring
067     * @param m matrix
068     */
069    public GenMatrix(GenMatrixRing<C> r, ArrayList<ArrayList<C>> m) {
070        if (r == null || m == null) {
071            throw new IllegalArgumentException("Empty r or m not allowed, r = " + r + ", m = " + m);
072        }
073        ring = r;
074        matrix = new ArrayList<ArrayList<C>>(m);
075        logger.info(ring.rows + " x " + ring.cols + " matrix constructed");
076    }
077
078
079    /**
080     * Get element at row i, column j.
081     * @param i row index.
082     * @param j column index.
083     * @return this(i,j).
084     */
085    public C get(int i, int j) {
086        return matrix.get(i).get(j);
087    }
088
089
090    /**
091     * Set element at row i, column j. Mutates this matrix.
092     * @param i row index.
093     * @param j column index.
094     * @param el element to set.
095     */
096    public void setMutate(int i, int j, C el) {
097        ArrayList<C> ri = matrix.get(i);
098        ri.set(j, el);
099        hashValue = 0; // invalidate
100    }
101
102
103    /**
104     * Set element at row i, column j.
105     * @param i row index.
106     * @param j column index.
107     * @param el element to set.
108     * @return new matrix m, with m(i,j) == el.
109     */
110    public GenMatrix<C> set(int i, int j, C el) {
111        GenMatrix<C> mat = this.copy();
112        mat.setMutate(i, j, el);
113        return mat;
114    }
115
116
117    /**
118     * Get the String representation as RingElem.
119     * @see java.lang.Object#toString()
120     */
121    @Override
122    public String toString() {
123        StringBuffer s = new StringBuffer();
124        boolean firstRow = true;
125        s.append("[\n");
126        for (List<C> val : matrix) {
127            if (firstRow) {
128                firstRow = false;
129            } else {
130                s.append(",\n");
131            }
132            boolean first = true;
133            s.append("[ ");
134            for (C c : val) {
135                if (first) {
136                    first = false;
137                } else {
138                    s.append(", ");
139                }
140                s.append(c.toString());
141            }
142            s.append(" ]");
143        }
144        s.append(" ] ");
145        if (!PrettyPrint.isTrue()) {
146            s.append(":: " + ring.toString());
147            s.append("\n");
148        }
149        return s.toString();
150    }
151
152
153    /**
154     * Get a scripting compatible string representation.
155     * @return script compatible representation for this Element.
156     * @see edu.jas.structure.Element#toScript()
157     */
158    //JAVA6only: @Override
159    public String toScript() {
160        // Python case
161        StringBuffer s = new StringBuffer();
162        boolean firstRow = true;
163        s.append("( ");
164        for (List<C> val : matrix) {
165            if (firstRow) {
166                firstRow = false;
167            } else {
168                s.append(", ");
169            }
170            boolean first = true;
171            s.append("( ");
172            for (C c : val) {
173                if (first) {
174                    first = false;
175                } else {
176                    s.append(", ");
177                }
178                s.append(c.toScript());
179            }
180            s.append(" )");
181        }
182        s.append(" ) ");
183        return s.toString();
184    }
185
186
187    /**
188     * Get a scripting compatible string representation of the factory.
189     * @return script compatible representation for this ElemFactory.
190     * @see edu.jas.structure.Element#toScriptFactory()
191     */
192    //JAVA6only: @Override
193    public String toScriptFactory() {
194        // Python case
195        return factory().toScript();
196    }
197
198
199    /**
200     * Get the corresponding element factory.
201     * @return factory for this Element.
202     * @see edu.jas.structure.Element#factory()
203     */
204    public GenMatrixRing<C> factory() {
205        return ring;
206    }
207
208
209    /**
210     * clone method.
211     * @see java.lang.Object#clone()
212     */
213    @Override
214    @SuppressWarnings("unchecked")
215    public GenMatrix<C> copy() {
216        //return ring.copy(this);
217        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
218        ArrayList<C> v;
219        for (ArrayList<C> val : matrix) {
220            v = (ArrayList<C>) val.clone();
221            m.add(v);
222        }
223        return new GenMatrix<C>(ring, m);
224    }
225
226
227    /**
228     * Test if this is equal to a zero matrix.
229     */
230    public boolean isZERO() {
231        for (List<C> row : matrix) {
232            for (C elem : row) {
233                if (!elem.isZERO()) {
234                    return false;
235                }
236            }
237        }
238        return true;
239    }
240
241
242    /**
243     * Test if this is one.
244     * @return true if this is 1, else false.
245     */
246    public boolean isONE() {
247        int i = 0;
248        for (List<C> row : matrix) {
249            int j = 0;
250            for (C elem : row) {
251                if (i == j) {
252                    if (!elem.isONE()) {
253                        return false;
254                    }
255                } else if (!elem.isZERO()) {
256                    return false;
257                }
258                j++;
259            }
260            i++;
261        }
262        return true;
263    }
264
265
266    /**
267     * Comparison with any other object.
268     * @see java.lang.Object#equals(java.lang.Object)
269     */
270    @Override
271    @SuppressWarnings("unchecked")
272    public boolean equals(Object other) {
273        if (!(other instanceof GenMatrix)) {
274            return false;
275        }
276        GenMatrix om = (GenMatrix) other;
277        if (!ring.equals(om.ring)) {
278            return false;
279        }
280        if (!matrix.equals(om.matrix)) {
281            return false;
282        }
283        return true;
284    }
285
286
287    /**
288     * Hash code for this GenMatrix.
289     * @see java.lang.Object#hashCode()
290     */
291    @Override
292    public int hashCode() {
293        if (hashValue == 0) {
294            hashValue = 37 * matrix.hashCode() + ring.hashCode();
295            if (hashValue == 0) {
296                hashValue = 1;
297            }
298        }
299        return hashValue;
300    }
301
302
303    /**
304     * compareTo, lexicogaphical comparison.
305     * @param b other
306     * @return 1 if (this &lt; b), 0 if (this == b) or -1 if (this &gt; b).
307     */
308    //JAVA6only: @Override
309    public int compareTo(GenMatrix<C> b) {
310        if (!ring.equals(b.ring)) {
311            return -1;
312        }
313        ArrayList<ArrayList<C>> om = b.matrix;
314        int i = 0;
315        for (ArrayList<C> val : matrix) {
316            ArrayList<C> ov = om.get(i++);
317            int j = 0;
318            for (C c : val) {
319                int s = c.compareTo(ov.get(j++));
320                if (s != 0) {
321                    return s;
322                }
323            }
324        }
325        return 0;
326    }
327
328
329    /**
330     * Test if this is a unit. I.e. there exists x with this.multiply(x).isONE()
331     * == true. Tests if all diagonal elements are units and all other elements
332     * are zero.
333     * @return true if this is a unit, else false.
334     */
335    public boolean isUnit() {
336        int i = 0;
337        for (ArrayList<C> val : matrix) {
338            int j = 0;
339            for (C el : val) {
340                if (i == j) {
341                    if (!el.isUnit()) {
342                        return false;
343                    }
344                } else {
345                    if (!el.isZERO()) {
346                        return false;
347                    }
348                }
349                j++;
350            }
351            i++;
352        }
353        return true;
354    }
355
356
357    /**
358     * sign of matrix.
359     * @return 1 if (this &lt; 0), 0 if (this == 0) or -1 if (this &gt; 0).
360     */
361    public int signum() {
362        return compareTo(ring.getZERO());
363    }
364
365
366    /**
367     * Sum of matrices.
368     * @return this+b
369     */
370    public GenMatrix<C> sum(GenMatrix<C> b) {
371        ArrayList<ArrayList<C>> om = b.matrix;
372        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
373        int i = 0;
374        for (ArrayList<C> val : matrix) {
375            ArrayList<C> ov = om.get(i++);
376            ArrayList<C> v = new ArrayList<C>(ring.cols);
377            int j = 0;
378            for (C c : val) {
379                C e = c.sum(ov.get(j++));
380                v.add(e);
381            }
382            m.add(v);
383        }
384        return new GenMatrix<C>(ring, m);
385    }
386
387
388    /**
389     * Difference of matrices.
390     * @return this-b
391     */
392    public GenMatrix<C> subtract(GenMatrix<C> b) {
393        ArrayList<ArrayList<C>> om = b.matrix;
394        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
395        int i = 0;
396        for (ArrayList<C> val : matrix) {
397            ArrayList<C> ov = om.get(i++);
398            ArrayList<C> v = new ArrayList<C>(ring.cols);
399            int j = 0;
400            for (C c : val) {
401                C e = c.subtract(ov.get(j++));
402                v.add(e);
403            }
404            m.add(v);
405        }
406        return new GenMatrix<C>(ring, m);
407    }
408
409
410    /**
411     * Negative of this matrix.
412     * @return -this
413     */
414    public GenMatrix<C> negate() {
415        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
416        //int i = 0;
417        for (ArrayList<C> val : matrix) {
418            ArrayList<C> v = new ArrayList<C>(ring.cols);
419            for (C c : val) {
420                C e = c.negate();
421                v.add(e);
422            }
423            m.add(v);
424        }
425        return new GenMatrix<C>(ring, m);
426    }
427
428
429    /**
430     * Absolute value of this matrix.
431     * @return abs(this)
432     */
433    public GenMatrix<C> abs() {
434        if (signum() < 0) {
435            return negate();
436        }
437        return this;
438    }
439
440
441    /**
442     * Product of this matrix with scalar.
443     * @return this*s
444     */
445    public GenMatrix<C> scalarMultiply(C s) {
446        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
447        //int i = 0;
448        for (ArrayList<C> val : matrix) {
449            ArrayList<C> v = new ArrayList<C>(ring.cols);
450            for (C c : val) {
451                C e = c.multiply(s);
452                v.add(e);
453            }
454            m.add(v);
455        }
456        return new GenMatrix<C>(ring, m);
457    }
458
459
460    /**
461     * Left product of this matrix with scalar.
462     * @return s*this
463     */
464    public GenMatrix<C> leftScalarMultiply(C s) {
465        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
466        //int i = 0;
467        for (ArrayList<C> val : matrix) {
468            ArrayList<C> v = new ArrayList<C>(ring.cols);
469            for (C c : val) {
470                C e = s.multiply(c);
471                v.add(e);
472            }
473            m.add(v);
474        }
475        return new GenMatrix<C>(ring, m);
476    }
477
478
479    /**
480     * Linear compination of this matrix with scalar multiple of other matrix.
481     * @return this*s+b*t
482     */
483    public GenMatrix<C> linearCombination(C s, GenMatrix<C> b, C t) {
484        ArrayList<ArrayList<C>> om = b.matrix;
485        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
486        int i = 0;
487        for (ArrayList<C> val : matrix) {
488            ArrayList<C> ov = om.get(i++);
489            ArrayList<C> v = new ArrayList<C>(ring.cols);
490            int j = 0;
491            for (C c : val) {
492                C c1 = c.multiply(s);
493                C c2 = ov.get(j++).multiply(t);
494                C e = c1.sum(c2);
495                v.add(e);
496            }
497            m.add(v);
498        }
499        return new GenMatrix<C>(ring, m);
500    }
501
502
503    /**
504     * Linear combination of this matrix with scalar multiple of other matrix.
505     * @return this+b*t
506     */
507    public GenMatrix<C> linearCombination(GenMatrix<C> b, C t) {
508        ArrayList<ArrayList<C>> om = b.matrix;
509        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
510        int i = 0;
511        for (ArrayList<C> val : matrix) {
512            ArrayList<C> ov = om.get(i++);
513            ArrayList<C> v = new ArrayList<C>(ring.cols);
514            int j = 0;
515            for (C c : val) {
516                C c2 = ov.get(j++).multiply(t);
517                C e = c.sum(c2);
518                v.add(e);
519            }
520            m.add(v);
521        }
522        return new GenMatrix<C>(ring, m);
523    }
524
525
526    /**
527     * Left linear combination of this matrix with scalar multiple of other
528     * matrix.
529     * @return this+t*b
530     */
531    public GenMatrix<C> linearCombination(C t, GenMatrix<C> b) {
532        ArrayList<ArrayList<C>> om = b.matrix;
533        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
534        int i = 0;
535        for (ArrayList<C> val : matrix) {
536            ArrayList<C> ov = om.get(i++);
537            ArrayList<C> v = new ArrayList<C>(ring.cols);
538            int j = 0;
539            for (C c : val) {
540                C c2 = t.multiply(ov.get(j++));
541                C e = c.sum(c2);
542                v.add(e);
543            }
544            m.add(v);
545        }
546        return new GenMatrix<C>(ring, m);
547    }
548
549
550    /**
551     * left linear compination of this matrix with scalar multiple of other
552     * matrix.
553     * @return s*this+t*b
554     */
555    public GenMatrix<C> leftLinearCombination(C s, C t, GenMatrix<C> b) {
556        ArrayList<ArrayList<C>> om = b.matrix;
557        ArrayList<ArrayList<C>> m = new ArrayList<ArrayList<C>>(ring.rows);
558        int i = 0;
559        for (ArrayList<C> val : matrix) {
560            ArrayList<C> ov = om.get(i++);
561            ArrayList<C> v = new ArrayList<C>(ring.cols);
562            int j = 0;
563            for (C c : val) {
564                C c1 = s.multiply(c);
565                C c2 = t.multiply(ov.get(j++));
566                C e = c1.sum(c2);
567                v.add(e);
568            }
569            m.add(v);
570        }
571        return new GenMatrix<C>(ring, m);
572    }
573
574
575    /**
576     * Transposed matrix.
577     * @return transpose(this)
578     */
579    public GenMatrix<C> transpose(GenMatrixRing<C> tr) {
580        GenMatrix<C> t = tr.getZERO().copy();
581        ArrayList<ArrayList<C>> m = t.matrix;
582        int i = 0;
583        for (ArrayList<C> val : matrix) {
584            int j = 0;
585            for (C c : val) {
586                (m.get(j)).set(i, c); //A[j,i] = A[i,j]
587                j++;
588            }
589            i++;
590        }
591        // return new GenMatrix<C>(tr,m);
592        return t;
593    }
594
595
596    /**
597     * Multiply this with S.
598     * @param S
599     * @return this * S.
600     */
601    public GenMatrix<C> multiply(GenMatrix<C> S) {
602        int na = ring.blocksize;
603        int nb = ring.blocksize;
604        //System.out.println("#blocks = " + (matrix.size()/na) + ", na = " + na 
605        //    + " SeqMultBlockTrans");
606        ArrayList<ArrayList<C>> m = matrix;
607        //ArrayList<ArrayList<C>> s = S.matrix;
608
609        GenMatrixRing<C> tr = S.ring.transpose();
610        GenMatrix<C> T = S.transpose(tr);
611        ArrayList<ArrayList<C>> t = T.matrix;
612        //System.out.println("T = " + T); 
613
614        GenMatrixRing<C> pr = ring.product(S.ring);
615        GenMatrix<C> P = pr.getZERO().copy();
616        ArrayList<ArrayList<C>> p = P.matrix;
617        //System.out.println("P = " + P); 
618
619        for (int ii = 0; ii < m.size(); ii += na) {
620            for (int jj = 0; jj < t.size(); jj += nb) {
621
622                for (int i = ii; i < Math.min((ii + na), m.size()); i++) {
623                    ArrayList<C> Ai = m.get(i); //A[i];
624                    for (int j = jj; j < Math.min((jj + nb), t.size()); j++) {
625                        ArrayList<C> Bj = t.get(j); //B[j];
626                        C c = ring.coFac.getZERO();
627                        for (int k = 0; k < Bj.size(); k++) {
628                            c = c.sum(Ai.get(k).multiply(Bj.get(k)));
629                            //  c += Ai[k] * Bj[k];
630                        }
631                        (p.get(i)).set(j, c); // C[i][j] = c;
632                    }
633                }
634
635            }
636        }
637        return new GenMatrix<C>(pr, p);
638    }
639
640
641    /**
642     * Multiply this with S. Simple unblocked algorithm.
643     * @param S
644     * @return this * S.
645     */
646    public GenMatrix<C> multiplySimple(GenMatrix<C> S) {
647        ArrayList<ArrayList<C>> m = matrix;
648        ArrayList<ArrayList<C>> B = S.matrix;
649
650        GenMatrixRing<C> pr = ring.product(S.ring);
651        GenMatrix<C> P = pr.getZERO().copy();
652        ArrayList<ArrayList<C>> p = P.matrix;
653
654        for (int i = 0; i < pr.rows; i++) {
655            ArrayList<C> Ai = m.get(i); //A[i];
656            for (int j = 0; j < pr.cols; j++) {
657                C c = ring.coFac.getZERO();
658                for (int k = 0; k < S.ring.rows; k++) {
659                    c = c.sum(Ai.get(k).multiply(B.get(k).get(j)));
660                    //  c += A[i][k] * B[k][j];
661                }
662                (p.get(i)).set(j, c); // C[i][j] = c;
663            }
664        }
665        return new GenMatrix<C>(pr, p);
666    }
667
668
669    /**
670     * Divide this by S.
671     * @param S
672     * @return this / S.
673     */
674    public GenMatrix<C> divide(GenMatrix<C> S) {
675        throw new UnsupportedOperationException("divide not yet implemented");
676    }
677
678
679    /**
680     * Remainder after division of this by S.
681     * @param S
682     * @return this - (this / S) * S.
683     */
684    public GenMatrix<C> remainder(GenMatrix<C> S) {
685        throw new UnsupportedOperationException("remainder not implemented");
686    }
687
688
689    /**
690     * Inverse of this.
691     * @return x with this * x = 1, if it exists.
692     */
693    public GenMatrix<C> inverse() {
694        throw new UnsupportedOperationException("inverse not yet implemented");
695    }
696
697
698    /**
699     * Greatest common divisor.
700     * @param b other element.
701     * @return gcd(this,b).
702     */
703    public GenMatrix<C> gcd(GenMatrix<C> b) {
704        throw new UnsupportedOperationException("gcd not implemented");
705    }
706
707
708    /**
709     * Extended greatest common divisor.
710     * @param b other element.
711     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
712     */
713    public GenMatrix<C>[] egcd(GenMatrix<C> b) {
714        throw new UnsupportedOperationException("egcd not implemented");
715    }
716
717}