001/* 002 * $Id: RReductionSeq.java 4286 2012-11-04 11:22:02Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.Map; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.gb.ReductionAbstract; 015import edu.jas.poly.ExpVector; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenSolvablePolynomial; 018import edu.jas.structure.RegularRingElem; 019 020 021/** 022 * Polynomial Regular ring Reduction sequential use algorithm. Implements 023 * normalform and boolean closure stuff. 024 * @param <C> coefficient type 025 * @author Heinz Kredel 026 */ 027 028public class RReductionSeq<C extends RegularRingElem<C>> extends ReductionAbstract<C> implements 029 RReduction<C> { 030 031 032 private static final Logger logger = Logger.getLogger(RReductionSeq.class); 033 034 035 private final boolean debug = logger.isDebugEnabled(); 036 037 038 /** 039 * Constructor. 040 */ 041 public RReductionSeq() { 042 } 043 044 045 /** 046 * Is top reducible. Condition is a b != 0, for a=ldcf(A) and b=ldcf(B) and 047 * lt(B) | lt(A) for some B in F. 048 * @param A polynomial. 049 * @param P polynomial list. 050 * @return true if A is top reducible with respect to P. 051 */ 052 @Override 053 public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) { 054 if (P == null || P.isEmpty()) { 055 return false; 056 } 057 if (A == null || A.isZERO()) { 058 return false; 059 } 060 boolean mt = false; 061 ExpVector e = A.leadingExpVector(); 062 C a = A.leadingBaseCoefficient(); 063 a = a.idempotent(); 064 for (GenPolynomial<C> p : P) { 065 mt = e.multipleOf(p.leadingExpVector()); 066 if (mt) { 067 C b = p.leadingBaseCoefficient(); 068 //C r = a.multiply( b ); 069 //C r = a.multiply( b.idempotent() ); 070 C r = a.idempotentAnd(b); 071 mt = !r.isZERO(); 072 if (mt) { 073 return true; 074 } 075 } 076 } 077 return false; 078 } 079 080 081 /** 082 * Is strong top reducible. Condition is idempotent(a) == idempotent(b), for 083 * a=ldcf(A) and b=ldcf(B) and lt(B) | lt(A) for some B in F. 084 * @param A polynomial. 085 * @param P polynomial list. 086 * @return true if A is string top reducible with respect to P. 087 */ 088 public boolean isStrongTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) { 089 if (P == null || P.isEmpty()) { 090 return false; 091 } 092 if (A == null || A.isZERO()) { 093 return false; 094 } 095 boolean mt = false; 096 ExpVector e = A.leadingExpVector(); 097 C a = A.leadingBaseCoefficient(); 098 a = a.idempotent(); 099 for (GenPolynomial<C> p : P) { 100 mt = e.multipleOf(p.leadingExpVector()); 101 if (mt) { 102 C b = p.leadingBaseCoefficient(); 103 mt = a.equals(b.idempotent()); 104 if (mt) { 105 return true; 106 } 107 } 108 } 109 return false; 110 } 111 112 113 /** 114 * Is in Normalform. 115 * @param Ap polynomial. 116 * @param Pp polynomial list. 117 * @return true if Ap is in normalform with respect to Pp. 118 */ 119 @Override 120 @SuppressWarnings("unchecked") 121 public boolean isNormalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 122 if (Pp == null || Pp.isEmpty()) { 123 return true; 124 } 125 if (Ap == null || Ap.isZERO()) { 126 return true; 127 } 128 int l; 129 GenPolynomial<C>[] P; 130 synchronized (Pp) { 131 l = Pp.size(); 132 P = new GenPolynomial[l]; 133 //P = Pp.toArray(); 134 for (int i = 0; i < Pp.size(); i++) { 135 P[i] = Pp.get(i); 136 } 137 } 138 ExpVector[] htl = new ExpVector[l]; 139 C[] lbc = (C[]) new RegularRingElem[l]; // want <C> 140 GenPolynomial<C>[] p = new GenPolynomial[l]; 141 Map.Entry<ExpVector, C> m; 142 int i; 143 int j = 0; 144 for (i = 0; i < l; i++) { 145 if (P[i] == null) { 146 continue; 147 } 148 p[i] = P[i]; 149 m = p[i].leadingMonomial(); 150 if (m != null) { 151 p[j] = p[i]; 152 htl[j] = m.getKey(); 153 lbc[j] = m.getValue(); 154 j++; 155 } 156 } 157 l = j; 158 boolean mt = false; 159 Map<ExpVector, C> Am = Ap.getMap(); 160 for (Map.Entry<ExpVector, C> me : Am.entrySet()) { 161 ExpVector e = me.getKey(); 162 C a = me.getValue(); 163 for (i = 0; i < l; i++) { 164 mt = e.multipleOf(htl[i]); 165 if (mt) { 166 //C r = a.multiply( lbc[i] ); 167 //C r = a.idempotent().multiply( lbc[i].idempotent() ); 168 C r = a.idempotentAnd(lbc[i]); 169 mt = !r.isZERO(); 170 if (mt) { 171 return false; 172 } 173 } 174 } 175 } 176 return true; 177 } 178 179 180 /** 181 * Normalform using r-reduction. 182 * @param Ap polynomial. 183 * @param Pp polynomial list. 184 * @return r-nf(Ap) with respect to Pp. 185 */ 186 @SuppressWarnings("unchecked") 187 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 188 if (Pp == null || Pp.isEmpty()) { 189 return Ap; 190 } 191 if (Ap == null || Ap.isZERO()) { 192 return Ap; 193 } 194 int l; 195 GenPolynomial<C>[] P; 196 synchronized (Pp) { 197 l = Pp.size(); 198 P = (GenPolynomial<C>[]) new GenPolynomial[l]; 199 //P = Pp.toArray(); 200 for (int i = 0; i < Pp.size(); i++) { 201 P[i] = Pp.get(i); 202 } 203 } 204 //System.out.println("l = " + l); 205 Map.Entry<ExpVector, C> m; 206 ExpVector[] htl = new ExpVector[l]; 207 C[] lbc = (C[]) new RegularRingElem[l]; // want <C> 208 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l]; 209 int i; 210 int j = 0; 211 for (i = 0; i < l; i++) { 212 if (P[i] == null) { 213 continue; 214 } 215 p[i] = P[i].abs(); 216 m = p[i].leadingMonomial(); 217 if (m != null) { 218 p[j] = p[i]; 219 htl[j] = m.getKey(); 220 lbc[j] = m.getValue(); 221 j++; 222 } 223 } 224 l = j; 225 ExpVector e, f; 226 C a, b; 227 C r = null; 228 boolean mt = false; 229 GenPolynomial<C> R = Ap.ring.getZERO(); 230 GenPolynomial<C> Q = null; 231 GenPolynomial<C> S = Ap; 232 while (S.length() > 0) { 233 m = S.leadingMonomial(); 234 e = m.getKey(); 235 a = m.getValue(); 236 if (debug) { 237 if ( a.isZERO() ) { 238 throw new RuntimeException("a.isZERO(): S = " + S); 239 } 240 } 241 for (i = 0; i < l; i++) { 242 mt = e.multipleOf(htl[i]); 243 if (mt) { 244 //r = a.multiply( lbc[i] ); 245 //r = a.idempotent().multiply( lbc[i].idempotent() ); 246 r = a.idempotentAnd(lbc[i]); 247 mt = !r.isZERO(); // && mt 248 if (mt) { 249 b = a.divide(lbc[i]); 250 if (b.isZERO()) { // strange case in regular rings 251 System.out.println("b == zero: r = " + r); 252 continue; 253 } 254 f = e.subtract(htl[i]); 255 //logger.info("red div = " + f); 256 Q = p[i].multiply(b, f); 257 S = S.subtract(Q); // not ok with reductum 258 f = S.leadingExpVector(); 259 if (!e.equals(f)) { 260 a = Ap.ring.coFac.getZERO(); 261 break; 262 } 263 a = S.leadingBaseCoefficient(); 264 } 265 } 266 } 267 if (!a.isZERO()) { //! mt ) { 268 //logger.debug("irred"); 269 R = R.sum(a, e); 270 S = S.reductum(); 271 } 272 } 273 return R; //.abs(); // not monic if not boolean closed 274 } 275 276 277 /** 278 * GB criterium 4. Use only for commutative polynomial rings. <b>Note:</b> 279 * Experimental version for r-Groebner bases. 280 * @param A polynomial. 281 * @param B polynomial. 282 * @param e = lcm(ht(A),ht(B)) 283 * @return true if the S-polynomial(i,j) is required, else false. 284 */ 285 @Override 286 public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B, ExpVector e) { 287 if (logger.isInfoEnabled()) { 288 if (!A.ring.equals(B.ring)) { 289 logger.error("rings equal"); 290 } 291 if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) { 292 logger.error("GBCriterion4 not applicabable to SolvablePolynomials"); 293 return true; 294 } 295 } 296 ExpVector ei = A.leadingExpVector(); 297 ExpVector ej = B.leadingExpVector(); 298 ExpVector g = ei.sum(ej); 299 // boolean t = g == e ; 300 ExpVector h = g.subtract(e); 301 int s = h.signum(); 302 if (s == 0) { // disjoint ht 303 C a = A.leadingBaseCoefficient(); 304 C b = B.leadingBaseCoefficient(); 305 C d = a.multiply(b); 306 if (d.isZERO()) { // a guess 307 //System.out.println("d1 = " + d + ", a = " + a + ", b = " + b); 308 return false; // can skip pair 309 } 310 } 311 return true; //! ( s == 0 ); 312 } 313 314 315 /** 316 * GB criterium 4. Use only for commutative polynomial rings. <b>Note:</b> 317 * Experimental version for r-Groebner bases. 318 * @param A polynomial. 319 * @param B polynomial. 320 * @return true if the S-polynomial(i,j) is required, else false. 321 */ 322 @Override 323 public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B) { 324 if (logger.isInfoEnabled()) { 325 if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) { 326 logger.error("GBCriterion4 not applicabable to SolvablePolynomials"); 327 return true; 328 } 329 } 330 ExpVector ei = A.leadingExpVector(); 331 ExpVector ej = B.leadingExpVector(); 332 ExpVector g = ei.sum(ej); 333 ExpVector e = ei.lcm(ej); 334 // boolean t = g == e ; 335 ExpVector h = g.subtract(e); 336 int s = h.signum(); 337 if (s == 0) { // disjoint ht 338 C a = A.leadingBaseCoefficient(); 339 C b = B.leadingBaseCoefficient(); 340 C d = a.multiply(b); 341 if (d.isZERO()) { // a guess 342 return false; // can skip pair 343 } 344 } 345 return true; //! ( s == 0 ); 346 } 347 348 349 /** 350 * Normalform with recording. 351 * @param row recording matrix, is modified. 352 * @param Pp a polynomial list for reduction. 353 * @param Ap a polynomial. 354 * @return Ap - row*Pp = nf(Pp,Ap) , the normal form of Ap wrt. Pp. 355 */ 356 @SuppressWarnings("unchecked") 357 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, 358 GenPolynomial<C> Ap) { 359 if (Pp == null || Pp.isEmpty()) { 360 return Ap; 361 } 362 if (Ap == null || Ap.isZERO()) { 363 return Ap; 364 } 365 int l; 366 GenPolynomial<C>[] P; 367 synchronized (Pp) { 368 l = Pp.size(); 369 P = (GenPolynomial<C>[]) new GenPolynomial[l]; 370 //P = Pp.toArray(); 371 for (int i = 0; i < Pp.size(); i++) { 372 P[i] = Pp.get(i); 373 } 374 } 375 //System.out.println("l = " + l); 376 Map.Entry<ExpVector, C> m; 377 ExpVector[] htl = new ExpVector[l]; 378 C[] lbc = (C[]) new RegularRingElem[l]; // want <C> 379 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l]; 380 int i; 381 int j = 0; 382 for (i = 0; i < l; i++) { 383 p[i] = P[i]; 384 m = p[i].leadingMonomial(); 385 if (m != null) { 386 p[j] = p[i]; 387 htl[j] = m.getKey(); 388 lbc[j] = m.getValue(); 389 j++; 390 } 391 } 392 l = j; 393 ExpVector e, f; 394 C a; 395 C r = null; 396 boolean mt = false; 397 GenPolynomial<C> fac = null; 398 GenPolynomial<C> zero = Ap.ring.getZERO(); 399 GenPolynomial<C> R = Ap.ring.getZERO(); 400 GenPolynomial<C> Q = null; 401 GenPolynomial<C> S = Ap; 402 while (S.length() > 0) { 403 m = S.leadingMonomial(); 404 e = m.getKey(); 405 a = m.getValue(); 406 for (i = 0; i < l; i++) { 407 mt = e.multipleOf(htl[i]); 408 if (mt) { 409 //r = a.idempotent().multiply( lbc[i].idempotent() ); 410 //r = a.multiply( lbc[i] ); 411 r = a.idempotentAnd(lbc[i]); 412 //System.out.println("r = " + r); 413 mt = !r.isZERO(); // && mt 414 if (mt) { 415 a = a.divide(lbc[i]); 416 if (a.isZERO()) { // strange case in regular rings 417 System.out.println("b == zero: r = " + r); 418 continue; 419 } 420 f = e.subtract(htl[i]); 421 //logger.info("red div = " + f); 422 Q = p[i].multiply(a, f); 423 S = S.subtract(Q); // not ok with reductum 424 425 fac = row.get(i); 426 if (fac == null) { 427 fac = zero.sum(a, f); 428 } else { 429 fac = fac.sum(a, f); 430 } 431 row.set(i, fac); 432 433 f = S.leadingExpVector(); 434 if (!e.equals(f)) { 435 a = Ap.ring.coFac.getZERO(); 436 break; 437 } 438 a = S.leadingBaseCoefficient(); 439 } 440 } 441 } 442 if (!a.isZERO()) { //! mt ) { 443 //logger.debug("irred"); 444 R = R.sum(a, e); 445 S = S.reductum(); 446 } 447 } 448 return R; //.abs(); not for recording 449 } 450 451 452 /** 453 * Irreducible set. May not be boolean closed. 454 * @param Pp polynomial list. 455 * @return a list P of polynomials which are in normalform wrt. P. 456 */ 457 @Override 458 public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) { 459 ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>(); 460 if (Pp == null) { 461 return null; 462 } 463 for (GenPolynomial<C> a : Pp) { 464 if (!a.isZERO()) { 465 P.add(a); 466 } 467 } 468 int l = P.size(); 469 if (l <= 1) 470 return P; 471 472 int irr = 0; 473 ExpVector e; 474 ExpVector f; 475 GenPolynomial<C> a; 476 logger.debug("irr = "); 477 while (irr != l) { 478 //a = P.get(0); 479 a = P.remove(0); 480 e = a.leadingExpVector(); 481 a = normalform(P, a); 482 // no not make monic because of boolean closure 483 logger.debug(String.valueOf(irr)); 484 if (a.isZERO()) { 485 l--; 486 if (l <= 1) { 487 return P; 488 } 489 } else { 490 f = a.leadingExpVector(); 491 if (e.equals(f)) { 492 // lbcf(a) eventually shorter 493 // correct since longer coeffs can reduce shorter coeffs 494 irr++; 495 } else { 496 irr = 0; 497 } 498 P.add(a); 499 } 500 } 501 //System.out.println(); 502 return P; 503 } 504 505 506 /* 507 * -------- boolean closure stuff ----------------------------------------- 508 */ 509 510 /** 511 * Is boolean closed, test if A == idempotent(ldcf(A)) A. 512 * @param A polynomial. 513 * @return true if A is boolean closed, else false. 514 */ 515 public boolean isBooleanClosed(GenPolynomial<C> A) { 516 if (A == null || A.isZERO()) { 517 return true; 518 } 519 C a = A.leadingBaseCoefficient(); 520 C i = a.idempotent(); 521 GenPolynomial<C> B = A.multiply(i); 522 // better run idemAnd on coefficients 523 if (A.equals(B)) { 524 return true; 525 } 526 return false; 527 } 528 529 530 /** 531 * Is boolean closed, test if all A in F are boolean closed. 532 * @param F polynomial list. 533 * @return true if F is boolean closed, else false. 534 */ 535 public boolean isBooleanClosed(List<GenPolynomial<C>> F) { 536 if (F == null || F.size() == 0) { 537 return true; 538 } 539 for (GenPolynomial<C> a : F) { 540 if (a == null || a.isZERO()) { 541 continue; 542 } 543 //System.out.println("a = " + a); 544 if (!isBooleanClosed(a)) { 545 return false; 546 } 547 } 548 return true; 549 } 550 551 552 /** 553 * Is reduced boolean closed, test if all A in F are boolean closed or br(A) 554 * reduces to zero. 555 * @param F polynomial list. 556 * @return true if F is boolean closed, else false. 557 */ 558 public boolean isReducedBooleanClosed(List<GenPolynomial<C>> F) { 559 if (F == null || F.size() == 0) { 560 return true; 561 } 562 GenPolynomial<C> b; 563 GenPolynomial<C> r; 564 for (GenPolynomial<C> a : F) { 565 //System.out.println("a = " + a); 566 if (a == null) { 567 continue; 568 } 569 while (!a.isZERO()) { 570 if (!isBooleanClosed(a)) { 571 b = booleanClosure(a); 572 b = normalform(F, b); 573 if (!b.isZERO()) { //F.contains(r) 574 return false; 575 } 576 } 577 r = booleanRemainder(a); 578 r = normalform(F, r); 579 if (!r.isZERO()) { //F.contains(r) 580 return false; 581 } 582 //System.out.println("r = " + r); 583 a = r; 584 } 585 } 586 return true; 587 } 588 589 590 /** 591 * Boolean closure, compute idempotent(ldcf(A)) A. 592 * @param A polynomial. 593 * @return bc(A). 594 */ 595 public GenPolynomial<C> booleanClosure(GenPolynomial<C> A) { 596 if (A == null || A.isZERO()) { 597 return A; 598 } 599 C a = A.leadingBaseCoefficient(); 600 C i = a.idempotent(); 601 GenPolynomial<C> B = A.multiply(i); 602 return B; 603 } 604 605 606 /** 607 * Boolean remainder, compute idemComplement(ldcf(A)) A. 608 * @param A polynomial. 609 * @return br(A). 610 */ 611 public GenPolynomial<C> booleanRemainder(GenPolynomial<C> A) { 612 if (A == null || A.isZERO()) { 613 return A; 614 } 615 C a = A.leadingBaseCoefficient(); 616 C i = a.idemComplement(); 617 GenPolynomial<C> B = A.multiply(i); 618 return B; 619 } 620 621 622 /** 623 * Boolean closure, compute BC(A) for all A in F. 624 * @param F polynomial list. 625 * @return bc(F). 626 */ 627 public List<GenPolynomial<C>> booleanClosure(List<GenPolynomial<C>> F) { 628 if (F == null || F.size() == 0) { 629 return F; 630 } 631 List<GenPolynomial<C>> B = new ArrayList<GenPolynomial<C>>(F.size()); 632 for (GenPolynomial<C> a : F) { 633 if (a == null) { 634 continue; 635 } 636 while (!a.isZERO()) { 637 GenPolynomial<C> b = booleanClosure(a); 638 B.add(b); 639 a = booleanRemainder(a); 640 } 641 } 642 return B; 643 } 644 645 646 /** 647 * Reduced boolean closure, compute BC(A) for all A in F. 648 * @param F polynomial list. 649 * @return red(bc(F)) = bc(red(F)). 650 */ 651 public List<GenPolynomial<C>> reducedBooleanClosure(List<GenPolynomial<C>> F) { 652 if (F == null || F.size() == 0) { 653 return F; 654 } 655 List<GenPolynomial<C>> B = new ArrayList<GenPolynomial<C>>(F); 656 GenPolynomial<C> a; 657 GenPolynomial<C> b; 658 GenPolynomial<C> c; 659 int len = B.size(); 660 for (int i = 0; i < len; i++) { // not B.size(), it changes 661 a = B.remove(0); 662 if (a == null) { 663 continue; 664 } 665 while (!a.isZERO()) { 666 //System.out.println("a = " + a); 667 b = booleanClosure(a); 668 //System.out.println("b = " + b); 669 b = booleanClosure(normalform(B, b)); 670 if (b.isZERO()) { 671 break; 672 } 673 B.add(b); // adds as last 674 c = a.subtract(b); // = BR(a mod B) 675 //System.out.println("c = " + c); 676 c = normalform(B, c); 677 a = c; 678 } 679 } 680 return B; 681 } 682 683 684 /** 685 * Reduced boolean closure, compute BC(A) modulo F. 686 * @param A polynomial. 687 * @param F polynomial list. 688 * @return red(bc(A)). 689 */ 690 public List<GenPolynomial<C>> reducedBooleanClosure(List<GenPolynomial<C>> F, GenPolynomial<C> A) { 691 List<GenPolynomial<C>> B = new ArrayList<GenPolynomial<C>>(); 692 if (A == null || A.isZERO()) { 693 return B; 694 } 695 GenPolynomial<C> a = A; 696 GenPolynomial<C> b; 697 GenPolynomial<C> c; 698 while (!a.isZERO()) { 699 //System.out.println("a = " + a); 700 b = booleanClosure(a); 701 //System.out.println("b = " + b); 702 b = booleanClosure(normalform(F, b)); 703 if (b.isZERO()) { 704 break; 705 } 706 B.add(b); // adds as last 707 c = a.subtract(b); // = BR(a mod F) 708 //System.out.println("c = " + c); 709 c = normalform(F, c); 710 //System.out.println("c = " + c); 711 a = c; 712 } 713 return B; 714 } 715 716}