Source code

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