001/* 002 * $Id: GenMatrix.java 4987 2014-11-22 18:26:30Z 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 @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 @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 = new ArrayList<C>(val); // 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 < b), 0 if (this == b) or -1 if (this > b). 307 */ 308 @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 < 0), 0 if (this == 0) or -1 if (this > 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 * Quotient and remainder by division of this by S. 691 * @param S a GenMatrix 692 * @return [this/S, this - (this/S)*S]. 693 */ 694 public GenMatrix<C>[] quotientRemainder(GenMatrix<C> S) { 695 throw new UnsupportedOperationException("quotientRemainder not implemented, input = " + S); 696 } 697 698 699 /** 700 * Inverse of this. 701 * @return x with this * x = 1, if it exists. 702 */ 703 public GenMatrix<C> inverse() { 704 throw new UnsupportedOperationException("inverse not yet implemented"); 705 } 706 707 708 /** 709 * Greatest common divisor. 710 * @param b other element. 711 * @return gcd(this,b). 712 */ 713 public GenMatrix<C> gcd(GenMatrix<C> b) { 714 throw new UnsupportedOperationException("gcd not implemented"); 715 } 716 717 718 /** 719 * Extended greatest common divisor. 720 * @param b other element. 721 * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b). 722 */ 723 public GenMatrix<C>[] egcd(GenMatrix<C> b) { 724 throw new UnsupportedOperationException("egcd not implemented"); 725 } 726 727}