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