001/* 002 * $Id$ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.ListIterator; 011 012import org.apache.logging.log4j.Logger; 013import org.apache.logging.log4j.LogManager; 014 015import edu.jas.poly.ExpVector; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenPolynomialRing; 018import edu.jas.poly.GenSolvablePolynomial; 019import edu.jas.poly.GenSolvablePolynomialRing; 020import edu.jas.poly.QLRSolvablePolynomialRing; 021import edu.jas.poly.PolyUtil; 022import edu.jas.poly.PolynomialList; 023import edu.jas.poly.ModuleList; 024import edu.jas.poly.TermOrder; 025import edu.jas.structure.RingElem; 026import edu.jas.structure.RingFactory; 027import edu.jas.vector.BasicLinAlg; 028 029 030/** 031 * Solvable Groebner Bases abstract class. Implements common left, right and 032 * twosided Groebner bases and left, right and twosided GB tests. 033 * @param <C> coefficient type 034 * @author Heinz Kredel 035 */ 036public abstract class SolvableGroebnerBaseAbstract<C extends RingElem<C>> implements SolvableGroebnerBase<C> { 037 038 039 private static final Logger logger = LogManager.getLogger(SolvableGroebnerBaseAbstract.class); 040 041 042 private static final boolean debug = logger.isDebugEnabled(); 043 044 045 /** 046 * Solvable reduction engine. 047 */ 048 public SolvableReduction<C> sred; 049 050 051 /** 052 * Reduction engine. 053 */ 054 public final Reduction<C> red; 055 056 057 /** 058 * Strategy for pair selection. 059 */ 060 public final PairList<C> strategy; 061 062 063 /** 064 * Linear algebra engine. 065 */ 066 protected final BasicLinAlg<GenPolynomial<C>> blas; 067 068 069 /** 070 * Commutative Groebner bases engine. 071 */ 072 public final GroebnerBaseAbstract<C> cbb; 073 074 075 /** 076 * Constructor. 077 */ 078 public SolvableGroebnerBaseAbstract() { 079 this(new SolvableReductionSeq<C>()); 080 } 081 082 083 /** 084 * Constructor. 085 * @param sred Solvable reduction engine 086 */ 087 public SolvableGroebnerBaseAbstract(SolvableReduction<C> sred) { 088 this(sred, new OrderedPairlist<C>()); 089 } 090 091 092 /** 093 * Constructor. 094 * @param pl pair selection strategy 095 */ 096 public SolvableGroebnerBaseAbstract(PairList<C> pl) { 097 this(new SolvableReductionSeq<C>(), pl); 098 } 099 100 101 /** 102 * Constructor. 103 * @param sred Solvable reduction engine 104 * @param pl pair selection strategy 105 */ 106 public SolvableGroebnerBaseAbstract(SolvableReduction<C> sred, PairList<C> pl) { 107 this.red = new ReductionSeq<C>(); 108 this.sred = sred; 109 this.strategy = pl; 110 blas = new BasicLinAlg<GenPolynomial<C>>(); 111 cbb = new GroebnerBaseSeq<C>(); 112 } 113 114 115 /** 116 * Normalize polynomial list. 117 * @param A list of polynomials. 118 * @return list of polynomials with zeros removed and ones/units reduced. 119 */ 120 public List<GenSolvablePolynomial<C>> normalizeZerosOnes(List<GenSolvablePolynomial<C>> A) { 121 //List<GenPolynomial<C>> a = PolynomialList.<C> castToList(A); 122 //List<GenPolynomial<C>> n = cbb.normalizeZeroOnes(a); 123 //List<GenSolvablePolynomial<C>> N = PolynomialList.<C> castToSolvableList(n); 124 if (A == null) { 125 return A; 126 } 127 List<GenSolvablePolynomial<C>> N = new ArrayList<GenSolvablePolynomial<C>>(A.size()); 128 if (A.isEmpty()) { 129 return N; 130 } 131 for (GenSolvablePolynomial<C> p : A) { 132 if (p == null || p.isZERO()) { 133 continue; 134 } 135 if (p.isUnit()) { 136 N.clear(); 137 N.add(p.ring.getONE()); 138 return N; 139 } 140 N.add((GenSolvablePolynomial<C>) p.abs()); 141 } 142 //N.trimToSize(); 143 return N; 144 } 145 146 147 /** 148 * Left Groebner base test. 149 * @param F solvable polynomial list. 150 * @return true, if F is a left Groebner base, else false. 151 */ 152 public boolean isLeftGB(List<GenSolvablePolynomial<C>> F) { 153 return isLeftGB(0, F, true); 154 } 155 156 157 /** 158 * Left Groebner base test. 159 * @param F solvable polynomial list. 160 * @param b true for simple test, false for GB test. 161 * @return true, if F is a Groebner base, else false. 162 */ 163 public boolean isLeftGB(List<GenSolvablePolynomial<C>> F, boolean b) { 164 return isLeftGB(0, F, b); 165 } 166 167 168 /** 169 * Left Groebner base test. 170 * @param modv module variable number. 171 * @param F solvable polynomial list. 172 * @return true, if F is a Groebner base, else false. 173 */ 174 public boolean isLeftGB(int modv, List<GenSolvablePolynomial<C>> F) { 175 return isLeftGB(modv, F, true); 176 } 177 178 179 /** 180 * Left Groebner base test. 181 * @param modv module variable number. 182 * @param F solvable polynomial list. 183 * @param b true for simple test, false for GB test. 184 * @return true, if F is a Groebner base, else false. 185 */ 186 public boolean isLeftGB(int modv, List<GenSolvablePolynomial<C>> F, boolean b) { 187 if (b) { 188 return isLeftGBsimple(modv, F); 189 } 190 return isLeftGBidem(modv, F); 191 } 192 193 194 /** 195 * Left Groebner base test. 196 * @param modv number of module variables. 197 * @param F solvable polynomial list. 198 * @return true, if F is a left Groebner base, else false. 199 */ 200 public boolean isLeftGBsimple(int modv, List<GenSolvablePolynomial<C>> F) { 201 GenSolvablePolynomial<C> pi, pj, s, h; 202 for (int i = 0; i < F.size(); i++) { 203 pi = F.get(i); 204 for (int j = i + 1; j < F.size(); j++) { 205 pj = F.get(j); 206 if (!red.moduleCriterion(modv, pi, pj)) { 207 continue; 208 } 209 // if ( ! red.criterion4( pi, pj ) ) { continue; } 210 s = sred.leftSPolynomial(pi, pj); 211 if (s.isZERO()) { 212 continue; 213 } 214 h = sred.leftNormalform(F, s); 215 if (!h.isZERO()) { 216 logger.info("no left GB: pi = {}, pj = {}", pi, pj); 217 logger.info("s = {}, h = {}", s, h); 218 return false; 219 } 220 } 221 } 222 return true; 223 } 224 225 226 /** 227 * Left Groebner base idempotence test. 228 * @param modv module variable number. 229 * @param F solvable polynomial list. 230 * @return true, if F is equal to GB(F), else false. 231 */ 232 public boolean isLeftGBidem(int modv, List<GenSolvablePolynomial<C>> F) { 233 if (F == null || F.isEmpty()) { 234 return true; 235 } 236 GenSolvablePolynomialRing<C> pring = F.get(0).ring; 237 List<GenSolvablePolynomial<C>> G = leftGB(modv, F); 238 PolynomialList<C> Fp = new PolynomialList<C>(pring, F); 239 PolynomialList<C> Gp = new PolynomialList<C>(pring, G); 240 return Fp.compareTo(Gp) == 0; 241 } 242 243 244 /** 245 * Twosided Groebner base test. 246 * @param Fp solvable polynomial list. 247 * @return true, if Fp is a two-sided Groebner base, else false. 248 */ 249 public boolean isTwosidedGB(List<GenSolvablePolynomial<C>> Fp) { 250 return isTwosidedGB(0, Fp); 251 } 252 253 254 /** 255 * Twosided Groebner base test. 256 * @param modv number of module variables. 257 * @param Fp solvable polynomial list. 258 * @return true, if Fp is a two-sided Groebner base, else false. 259 */ 260 public boolean isTwosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) { 261 if (Fp == null || Fp.size() == 0) { // 0 not 1 262 return true; 263 } 264 if (Fp.size() == 1 && Fp.get(0).isONE()) { 265 return true; 266 } 267 GenSolvablePolynomialRing<C> ring = Fp.get(0).ring; // assert != null 268 // add also coefficient generators 269 List<GenSolvablePolynomial<C>> X; 270 X = PolynomialList.castToSolvableList(ring.generators(modv)); 271 logger.info("right multipliers = {}", X); 272 List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(Fp.size() * (1 + X.size())); 273 F.addAll(Fp); 274 GenSolvablePolynomial<C> p, q, x, pi, pj, s, h; 275 for (int i = 0; i < Fp.size(); i++) { 276 p = Fp.get(i); 277 for (int j = 0; j < X.size(); j++) { 278 x = X.get(j); 279 if (x.isONE()) { 280 continue; 281 } 282 q = p.multiply(x); 283 q = sred.leftNormalform(F, q); 284 if (!q.isZERO()) { 285 //System.out.println("is: q generated = " + q + ", p = " + p + ", x = " + x); 286 return false; 287 //F.add(q); 288 } 289 } 290 } 291 //System.out.println("F to check = " + F); 292 for (int i = 0; i < F.size(); i++) { 293 pi = F.get(i); 294 for (int j = i + 1; j < F.size(); j++) { 295 pj = F.get(j); 296 if (!red.moduleCriterion(modv, pi, pj)) { 297 continue; 298 } 299 // if ( ! red.criterion4( pi, pj ) ) { continue; } 300 s = sred.leftSPolynomial(pi, pj); 301 if (s.isZERO()) { 302 continue; 303 } 304 h = sred.leftNormalform(F, s); 305 if (!h.isZERO()) { 306 logger.info("is not TwosidedGB: {}", h); 307 //System.out.println("is: h = " + h + ", s = " + s); 308 return false; 309 } 310 } 311 } 312 return true; 313 } 314 315 316 /** 317 * Twosided Groebner base idempotence test. 318 * @param F solvable polynomial list. 319 * @return true, if F is equal to GB(F), else false. 320 */ 321 public boolean isTwosidedGBidem(List<GenSolvablePolynomial<C>> F) { 322 return isTwosidedGBidem(0, F); 323 } 324 325 326 /** 327 * Twosided Groebner base idempotence test. 328 * @param modv module variable number. 329 * @param F solvable polynomial list. 330 * @return true, if F is equal to GB(F), else false. 331 */ 332 public boolean isTwosidedGBidem(int modv, List<GenSolvablePolynomial<C>> F) { 333 if (F == null || F.isEmpty()) { 334 return true; 335 } 336 GenSolvablePolynomialRing<C> pring = F.get(0).ring; 337 List<GenSolvablePolynomial<C>> G = twosidedGB(modv, F); 338 PolynomialList<C> Fp = new PolynomialList<C>(pring, F); 339 PolynomialList<C> Gp = new PolynomialList<C>(pring, G); 340 return Fp.compareTo(Gp) == 0; 341 } 342 343 344 /** 345 * Right Groebner base test. 346 * @param F solvable polynomial list. 347 * @return true, if F is a right Groebner base, else false. 348 */ 349 public boolean isRightGB(List<GenSolvablePolynomial<C>> F) { 350 return isRightGB(0, F); 351 } 352 353 354 /** 355 * Right Groebner base test. 356 * @param modv number of module variables. 357 * @param F solvable polynomial list. 358 * @return true, if F is a right Groebner base, else false. 359 */ 360 public boolean isRightGB(int modv, List<GenSolvablePolynomial<C>> F) { 361 GenSolvablePolynomial<C> pi, pj, s, h; 362 for (int i = 0; i < F.size(); i++) { 363 pi = F.get(i); 364 //System.out.println("pi right = " + pi); 365 for (int j = i + 1; j < F.size(); j++) { 366 pj = F.get(j); 367 //System.out.println("pj right = " + pj); 368 if (!red.moduleCriterion(modv, pi, pj)) { 369 continue; 370 } 371 // if ( ! red.criterion4( pi, pj ) ) { continue; } 372 s = sred.rightSPolynomial(pi, pj); 373 if (s.isZERO()) { 374 continue; 375 } 376 //System.out.println("s right = " + s); 377 h = sred.rightNormalform(F, s); 378 if (!h.isZERO()) { 379 logger.info("isRightGB non zero h = {} :: {}, rspol = {}", h, h.ring.toScript(), s); 380 logger.info("p{} = {}, p{} = {}", i, pi, j, pj); 381 return false; 382 } 383 } 384 } 385 return true; 386 } 387 388 389 /** 390 * Right Groebner base idempotence test. 391 * @param F solvable polynomial list. 392 * @return true, if F is equal to GB(F), else false. 393 */ 394 public boolean isRightGBidem(List<GenSolvablePolynomial<C>> F) { 395 return isRightGBidem(0, F); 396 } 397 398 399 /** 400 * Right Groebner base idempotence test. 401 * @param modv module variable number. 402 * @param F solvable polynomial list. 403 * @return true, if F is equal to GB(F), else false. 404 */ 405 public boolean isRightGBidem(int modv, List<GenSolvablePolynomial<C>> F) { 406 if (F == null || F.isEmpty()) { 407 return true; 408 } 409 GenSolvablePolynomialRing<C> pring = F.get(0).ring; 410 List<GenSolvablePolynomial<C>> G = rightGB(modv, F); 411 PolynomialList<C> Fp = new PolynomialList<C>(pring, F); 412 PolynomialList<C> Gp = new PolynomialList<C>(pring, G); 413 return Fp.compareTo(Gp) == 0; 414 } 415 416 417 /** 418 * Left Groebner base using pairlist class. 419 * @param F solvable polynomial list. 420 * @return leftGB(F) a left Groebner base of F. 421 */ 422 public List<GenSolvablePolynomial<C>> leftGB(List<GenSolvablePolynomial<C>> F) { 423 return leftGB(0, F); 424 } 425 426 427 /** 428 * Solvable Extended Groebner base using critical pair class. 429 * @param F solvable polynomial list. 430 * @return a container for an extended left Groebner base of F. 431 */ 432 public SolvableExtendedGB<C> extLeftGB(List<GenSolvablePolynomial<C>> F) { 433 return extLeftGB(0, F); 434 } 435 436 437 /** 438 * Solvable Extended Groebner base using critical pair class. 439 * @param modv module variable number. 440 * @param F polynomial list. 441 * @return a container for an extended left Groebner base G of F together 442 * with back-and-forth transformations. 443 */ 444 public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) { 445 throw new UnsupportedOperationException("extLeftGB not implemented in " 446 + this.getClass().getSimpleName()); 447 } 448 449 450 /** 451 * Left minimal ordered groebner basis. 452 * @param Gp a left Groebner base. 453 * @return leftGBmi(F) a minimal left Groebner base of Gp. 454 */ 455 public List<GenSolvablePolynomial<C>> leftMinimalGB(List<GenSolvablePolynomial<C>> Gp) { 456 ArrayList<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(); 457 ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator(); 458 for (GenSolvablePolynomial<C> a : Gp) { 459 // a = (SolvablePolynomial) it.next(); 460 if (a.length() != 0) { // always true 461 // already monic a = a.monic(); 462 G.add(a); 463 } 464 } 465 if (G.size() <= 1) { 466 return G; 467 } 468 469 ExpVector e; 470 ExpVector f; 471 GenSolvablePolynomial<C> a, p; 472 ArrayList<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(); 473 boolean mt; 474 475 while (G.size() > 0) { 476 a = G.remove(0); 477 e = a.leadingExpVector(); 478 479 it = G.listIterator(); 480 mt = false; 481 while (it.hasNext() && !mt) { 482 p = it.next(); 483 f = p.leadingExpVector(); 484 mt = e.multipleOf(f); 485 } 486 it = F.listIterator(); 487 while (it.hasNext() && !mt) { 488 p = it.next(); 489 f = p.leadingExpVector(); 490 mt = e.multipleOf(f); 491 } 492 if (!mt) { 493 F.add(a); 494 } else { 495 // System.out.println("dropped " + a.length()); 496 } 497 } 498 G = F; 499 if (G.size() <= 1) { 500 return G; 501 } 502 503 F = new ArrayList<GenSolvablePolynomial<C>>(); 504 while (G.size() > 0) { 505 a = G.remove(0); 506 // System.out.println("doing " + a.length()); 507 a = sred.leftNormalform(G, a); 508 a = sred.leftNormalform(F, a); 509 F.add(a); 510 } 511 return F; 512 } 513 514 515 /** 516 * Right minimal ordered groebner basis. 517 * @param Gp a right Groebner base. 518 * @return rightGBmi(F) a minimal right Groebner base of Gp. 519 */ 520 public List<GenSolvablePolynomial<C>> rightMinimalGB(List<GenSolvablePolynomial<C>> Gp) { 521 ArrayList<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(); 522 ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator(); 523 for (GenSolvablePolynomial<C> a : Gp) { 524 if (a.length() != 0) { // always true 525 G.add(a); 526 } 527 } 528 if (G.size() <= 1) { 529 return G; 530 } 531 532 ExpVector e; 533 ExpVector f; 534 GenSolvablePolynomial<C> a, p; 535 ArrayList<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(); 536 boolean mt; 537 538 while (G.size() > 0) { 539 a = G.remove(0); 540 e = a.leadingExpVector(); 541 542 it = G.listIterator(); 543 mt = false; 544 while (it.hasNext() && !mt) { 545 p = it.next(); 546 f = p.leadingExpVector(); 547 mt = e.multipleOf(f); 548 } 549 it = F.listIterator(); 550 while (it.hasNext() && !mt) { 551 p = it.next(); 552 f = p.leadingExpVector(); 553 mt = e.multipleOf(f); 554 } 555 if (!mt) { 556 F.add(a); 557 } else { 558 // System.out.println("dropped " + a.length()); 559 } 560 } 561 G = F; 562 if (G.size() <= 1) { 563 return G; 564 } 565 566 F = new ArrayList<GenSolvablePolynomial<C>>(); 567 while (G.size() > 0) { 568 a = G.remove(0); 569 // System.out.println("doing " + a.length()); 570 a = sred.rightNormalform(G, a); 571 a = sred.rightNormalform(F, a); 572 F.add(a); 573 } 574 return F; 575 } 576 577 578 /** 579 * Twosided Groebner base using pairlist class. 580 * @param Fp solvable polynomial list. 581 * @return tsGB(Fp) a twosided Groebner base of Fp. 582 */ 583 public List<GenSolvablePolynomial<C>> twosidedGB(List<GenSolvablePolynomial<C>> Fp) { 584 return twosidedGB(0, Fp); 585 } 586 587 588 /** 589 * Right Groebner base using opposite ring left GB. 590 * @param F solvable polynomial list. 591 * @return rightGB(F) a right Groebner base of F. 592 */ 593 public List<GenSolvablePolynomial<C>> rightGB(List<GenSolvablePolynomial<C>> F) { 594 return rightGB(0, F); 595 } 596 597 598 /** 599 * Right Groebner base using opposite ring left GB. 600 * @param modv number of module variables. 601 * @param F solvable polynomial list. 602 * @return rightGB(F) a right Groebner base of F. 603 */ 604 @SuppressWarnings("unchecked") 605 public List<GenSolvablePolynomial<C>> rightGB(int modv, List<GenSolvablePolynomial<C>> F) { 606 List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F); 607 if (G.size() <= 1) { 608 return G; 609 } 610 GenSolvablePolynomialRing<C> ring = G.get(0).ring; // assert != null 611 GenSolvablePolynomialRing<C> rring = ring.reverse(true); //true 612 //System.out.println("rightGB: ring = " + ring.toScript() + ", reversed ring = " + rring.toScript()); 613 GenSolvablePolynomial<C> q; 614 List<GenSolvablePolynomial<C>> rF; 615 rF = new ArrayList<GenSolvablePolynomial<C>>(F.size()); 616 for (GenSolvablePolynomial<C> p : F) { 617 if (p != null) { 618 q = (GenSolvablePolynomial<C>) p.reverse(rring); 619 rF.add(q); 620 } 621 } 622 if (logger.isInfoEnabled()) { 623 PolynomialList<C> pl = new PolynomialList<C>(rring, rF); 624 logger.info("reversed problem = {}", pl.toScript()); 625 } 626 List<GenSolvablePolynomial<C>> rG = leftGB(modv, rF); 627 if (debug) { 628 //PolynomialList<C> pl = new PolynomialList<C>(rring,rG); 629 //logger.info("reversed GB = {}", pl); 630 long t = System.currentTimeMillis(); 631 boolean isit = isLeftGB(rG); 632 t = System.currentTimeMillis() - t; 633 logger.info("is left GB = {}, in {} milliseconds", isit, t); 634 } 635 //System.out.println("reversed left GB = " + rG); 636 ring = rring.reverse(true); // true 637 G = new ArrayList<GenSolvablePolynomial<C>>(rG.size()); 638 for (GenSolvablePolynomial<C> p : rG) { 639 if (p != null) { 640 q = (GenSolvablePolynomial<C>) p.reverse(ring); 641 G.add(q); 642 } 643 } 644 if (debug) { 645 //PolynomialList<C> pl = new PolynomialList<C>(ring,G); 646 //logger.info("GB = {}", pl); 647 long t = System.currentTimeMillis(); 648 boolean isit = isRightGB(G); 649 t = System.currentTimeMillis() - t; 650 logger.info("is right GB = {}, in {} milliseconds", isit, t); 651 } 652 return G; 653 } 654 655 656 /** 657 * Solvable Extended Groebner base using critical pair class. 658 * @param F solvable polynomial list. 659 * @return a container for an extended right Groebner base of F. 660 */ 661 public SolvableExtendedGB<C> extRightGB(List<GenSolvablePolynomial<C>> F) { 662 return extRightGB(0, F); 663 } 664 665 666 /** 667 * Solvable Extended Groebner base using critical pair class. 668 * @param modv module variable number. 669 * @param F polynomial list. 670 * @return a container for an extended right Groebner base G of F together 671 * with back-and-forth transformations. 672 */ 673 public SolvableExtendedGB<C> extRightGB(int modv, List<GenSolvablePolynomial<C>> F) { 674 throw new UnsupportedOperationException("extRightGB not implemented in " 675 + this.getClass().getSimpleName()); 676 } 677 678 679 /** 680 * Module left Groebner base test. 681 * @param M a module basis. 682 * @return true, if M is a left Groebner base, else false. 683 */ 684 public boolean isLeftGB(ModuleList<C> M) { 685 return isLeftGB(M,false); 686 } 687 688 689 /** 690 * Module left Groebner base test. 691 * @param M a module basis. 692 * @param top true for TOP term order, false for POT term order. 693 * @return true, if M is a left Groebner base, else false. 694 */ 695 public boolean isLeftGB(ModuleList<C> M, boolean top) { 696 if (M == null || M.list == null) { 697 return true; 698 } 699 if (M.rows == 0 || M.cols == 0) { 700 return true; 701 } 702 int modv = M.cols; // > 0 703 PolynomialList<C> F = M.getPolynomialList(top); 704 return isLeftGB(modv, F.castToSolvableList()); 705 } 706 707 708 /** 709 * Left Groebner base using pairlist class. 710 * @param M a module basis. 711 * @return leftGB(M) a left Groebner base for M. 712 */ 713 public ModuleList<C> leftGB(ModuleList<C> M) { 714 return leftGB(M,false); 715 } 716 717 718 /** 719 * Left Groebner base using pairlist class. 720 * @param M a module basis. 721 * @param top true for TOP term order, false for POT term order. 722 * @return leftGB(M) a left Groebner base for M. 723 */ 724 @SuppressWarnings("unchecked") 725 public ModuleList<C> leftGB(ModuleList<C> M, boolean top) { 726 ModuleList<C> N = M; 727 if (M == null || M.list == null) { 728 return N; 729 } 730 if (M.rows == 0 || M.cols == 0) { 731 return N; 732 } 733 PolynomialList<C> F = M.getPolynomialList(top); 734 if (debug) { 735 logger.info("F left +++++++++++++++++++ \n{}", F); 736 } 737 GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) F.ring; 738 int modv = M.cols; 739 List<GenSolvablePolynomial<C>> G = leftGB(modv, F.castToSolvableList()); 740 F = new PolynomialList<C>(sring, G); 741 if (debug) { 742 logger.info("G left +++++++++++++++++++ \n{}", F); 743 } 744 N = F.getModuleList(modv); 745 return N; 746 } 747 748 749 /** 750 * Module twosided Groebner base test. 751 * @param M a module basis. 752 * @return true, if M is a twosided Groebner base, else false. 753 */ 754 public boolean isTwosidedGB(ModuleList<C> M) { 755 return isTwosidedGB(M,false); 756 } 757 758 759 /** 760 * Module twosided Groebner base test. 761 * @param M a module basis. 762 * @param top true for TOP term order, false for POT term order. 763 * @return true, if M is a twosided Groebner base, else false. 764 */ 765 public boolean isTwosidedGB(ModuleList<C> M, boolean top) { 766 if (M == null || M.list == null) { 767 return true; 768 } 769 if (M.rows == 0 || M.cols == 0) { 770 return true; 771 } 772 PolynomialList<C> F = M.getPolynomialList(top); 773 int modv = M.cols; // > 0 774 return isTwosidedGB(modv, F.castToSolvableList()); 775 } 776 777 778 /** 779 * Twosided Groebner base using pairlist class. 780 * @param M a module basis. 781 * @return twosidedGB(M) a twosided Groebner base for M. 782 */ 783 public ModuleList<C> twosidedGB(ModuleList<C> M) { 784 return twosidedGB(M,false); 785 } 786 787 788 /** 789 * Twosided Groebner base using pairlist class. 790 * @param M a module basis. 791 * @param top true for TOP term order, false for POT term order. 792 * @return tsGB(M) a twosided Groebner base for M. 793 */ 794 @SuppressWarnings("unchecked") 795 public ModuleList<C> twosidedGB(ModuleList<C> M, boolean top) { 796 ModuleList<C> N = M; 797 if (M == null || M.list == null) { 798 return N; 799 } 800 if (M.rows == 0 || M.cols == 0) { 801 return N; 802 } 803 PolynomialList<C> F = M.getPolynomialList(top); 804 GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) F.ring; 805 int modv = M.cols; 806 List<GenSolvablePolynomial<C>> G = twosidedGB(modv, F.castToSolvableList()); 807 F = new PolynomialList<C>(sring, G); 808 N = F.getModuleList(modv); 809 return N; 810 } 811 812 813 /** 814 * Module right Groebner base test. 815 * @param M a module basis. 816 * @return true, if M is a right Groebner base, else false. 817 */ 818 public boolean isRightGB(ModuleList<C> M) { 819 return isRightGB(M,false); 820 } 821 822 823 /** 824 * Module right Groebner base test. 825 * @param M a module basis. 826 * @param top true for TOP term order, false for POT term order. 827 * @return true, if M is a right Groebner base, else false. 828 */ 829 public boolean isRightGB(ModuleList<C> M, boolean top) { 830 if (M == null || M.list == null) { 831 return true; 832 } 833 if (M.rows == 0 || M.cols == 0) { 834 return true; 835 } 836 if (top) { 837 logger.warn("computation of rightGB with TOP not possible"); 838 } 839 int modv = M.cols; // > 0 840 PolynomialList<C> F = M.getPolynomialList(top); 841 //System.out.println("F test = " + F); 842 return isRightGB(modv, F.castToSolvableList()); 843 } 844 845 846 /** 847 * Right Groebner base using pairlist class. 848 * @param M a module basis. 849 * @return rightGB(M) a right Groebner base for M. 850 */ 851 @SuppressWarnings("unchecked") 852 public ModuleList<C> rightGB(ModuleList<C> M) { // boolean top 853 ModuleList<C> N = M; 854 if (M == null || M.list == null) { 855 return N; 856 } 857 if (M.rows == 0 || M.cols == 0) { 858 return N; 859 } 860 if (debug) { 861 logger.info("M ====================== \n{}", M); 862 } 863 TermOrder to = M.ring.tord; 864 if (to.getSplit() <= M.ring.nvar) { 865 throw new IllegalArgumentException("extended TermOrders not supported for rightGBs: " + to); 866 } 867 List<List<GenSolvablePolynomial<C>>> mlist = M.castToSolvableList(); 868 GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) M.ring; 869 GenSolvablePolynomialRing<C> rring = sring.reverse(true); //true 870 sring = rring.reverse(true); // true 871 872 List<List<GenSolvablePolynomial<C>>> nlist = new ArrayList<List<GenSolvablePolynomial<C>>>(M.rows); 873 for (List<GenSolvablePolynomial<C>> row : mlist) { 874 List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row.size()); 875 for (GenSolvablePolynomial<C> elem : row) { 876 GenSolvablePolynomial<C> nelem = (GenSolvablePolynomial<C>) elem.reverse(rring); 877 nrow.add(nelem); 878 } 879 nlist.add(nrow); 880 } 881 ModuleList<C> rM = new ModuleList<C>(rring, nlist); 882 if (debug) { 883 logger.info("rM -------------------- \n{}", rM); 884 } 885 ModuleList<C> rMg = leftGB(rM); // top ? 886 if (debug) { 887 logger.info("rMg -------------------- \n{}", rMg); 888 logger.info("isLeftGB(rMg) ---------- {}", isLeftGB(rMg)); 889 } 890 mlist = rMg.castToSolvableList(); 891 nlist = new ArrayList<List<GenSolvablePolynomial<C>>>(rMg.rows); 892 for (List<GenSolvablePolynomial<C>> row : mlist) { 893 List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row.size()); 894 for (GenSolvablePolynomial<C> elem : row) { 895 GenSolvablePolynomial<C> nelem = (GenSolvablePolynomial<C>) elem.reverse(sring); 896 nrow.add(nelem); 897 } 898 nlist.add(nrow); 899 } 900 ModuleList<C> Mg = new ModuleList<C>(sring, nlist); 901 if (debug) { 902 logger.info("Mg -------------------- \n{}", Mg); 903 logger.info("isRightGB(Mg) --------- {}", isRightGB(Mg)); 904 } 905 return Mg; 906 } 907 908 909 /** 910 * Test if left reduction matrix. 911 * @param exgb an SolvableExtendedGB container. 912 * @return true, if exgb contains a left reduction matrix, else false. 913 */ 914 public boolean isLeftReductionMatrix(SolvableExtendedGB<C> exgb) { 915 if (exgb == null) { 916 return true; 917 } 918 return isLeftReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F); 919 } 920 921 922 /** 923 * Test if left reduction matrix. 924 * @param F a solvable polynomial list. 925 * @param G a left Groebner base. 926 * @param Mf a possible left reduction matrix. 927 * @param Mg a possible left reduction matrix. 928 * @return true, if Mg and Mf are left reduction matrices, else false. 929 */ 930 public boolean isLeftReductionMatrix(List<GenSolvablePolynomial<C>> F, List<GenSolvablePolynomial<C>> G, 931 List<List<GenSolvablePolynomial<C>>> Mf, List<List<GenSolvablePolynomial<C>>> Mg) { 932 // no more check G and Mg: G * Mg[i] == 0 933 // check F and Mg: F * Mg[i] == G[i] 934 int k = 0; 935 for (List<GenSolvablePolynomial<C>> row : Mg) { 936 boolean t = sred.isLeftReductionNF(row, F, G.get(k), null); 937 if (!t) { 938 System.out.println("row = " + row); 939 System.out.println("F = " + F); 940 System.out.println("G[" + k + "] = " + G.get(k)); 941 logger.info("F isLeftReductionMatrix s, k = {}, {}", F.size(), k); 942 System.out.println("F*row == G[k]: " + sred.isLeftReductionNF(F, row, G.get(k), null)); 943 return false; 944 } 945 k++; 946 } 947 // check G and Mf: G * Mf[i] == F[i] 948 k = 0; 949 for (List<GenSolvablePolynomial<C>> row : Mf) { 950 boolean t = sred.isLeftReductionNF(row, G, F.get(k), null); 951 if (!t) { 952 System.out.println("row = " + row); 953 System.out.println("G = " + G); 954 System.out.println("F[" + k + "] = " + F.get(k)); 955 logger.info("G isLeftReductionMatrix s, k = {}, {}", G.size(), k); 956 return false; 957 } 958 k++; 959 } 960 return true; 961 } 962 963 964 /** 965 * Ideal common zero test. 966 * @return -1, 0 or 1 if dimension(this) &eq; -1, 0 or ≥ 1. 967 */ 968 public int commonZeroTest(List<GenSolvablePolynomial<C>> A) { 969 List<GenPolynomial<C>> cA = PolynomialList.<C> castToList(A); 970 return cbb.commonZeroTest(cA); 971 } 972 973 974 /** 975 * Univariate head term degrees. 976 * @param A list of solvable polynomials. 977 * @return a list of the degrees of univariate head terms. 978 */ 979 public List<Long> univariateDegrees(List<GenSolvablePolynomial<C>> A) { 980 List<GenPolynomial<C>> cA = PolynomialList.<C> castToList(A); 981 return cbb.univariateDegrees(cA); 982 } 983 984 985 /** 986 * Construct univariate solvable polynomial of minimal degree in variable i 987 * of a zero dimensional ideal(G). 988 * @param i variable index. 989 * @param G list of solvable polynomials, a monic reduced left Gröbner 990 * base of a zero dimensional ideal. 991 * @return univariate solvable polynomial of minimal degree in variable i in 992 * ideal_left(G) 993 */ 994 public GenSolvablePolynomial<C> constructUnivariate(int i, List<GenSolvablePolynomial<C>> G) { 995 if (G == null || G.size() == 0) { 996 throw new IllegalArgumentException("G may not be null or empty"); 997 } 998 List<Long> ud = univariateDegrees(G); 999 if (ud.size() <= i) { 1000 //logger.info("univ pol, ud = {}", ud); 1001 throw new IllegalArgumentException("ideal(G) not zero dimensional " + ud); 1002 } 1003 int ll = 0; 1004 Long di = ud.get(i); 1005 if (di != null) { 1006 ll = (int) (long) di; 1007 } else { 1008 throw new IllegalArgumentException("ideal(G) not zero dimensional"); 1009 } 1010 long vsdim = 1; 1011 for (Long d : ud) { 1012 if (d != null) { 1013 vsdim *= d; 1014 } 1015 } 1016 logger.info("univariate construction, deg = {}, vsdim = {}", ll, vsdim); 1017 GenSolvablePolynomialRing<C> pfac = G.get(0).ring; 1018 RingFactory<C> cfac = pfac.coFac; 1019 1020 GenPolynomialRing<C> cpfac = new GenPolynomialRing<C>(cfac, ll, new TermOrder(TermOrder.INVLEX)); 1021 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = new GenSolvablePolynomialRing<GenPolynomial<C>>( 1022 cpfac, pfac); // relations 1023 GenSolvablePolynomial<GenPolynomial<C>> P = rfac.getZERO(); 1024 for (int k = 0; k < ll; k++) { 1025 GenSolvablePolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, k); 1026 GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - k); 1027 Pp = Pp.multiply(cp); 1028 P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(Pp); 1029 } 1030 if (debug) { 1031 logger.info("univariate construction, P = {}", P); 1032 logger.info("univariate construction, deg_*(G) = {}", ud); 1033 //throw new RuntimeException("check"); 1034 } 1035 GroebnerBaseAbstract<C> bbc = new GroebnerBaseSeq<C>(); 1036 GenSolvablePolynomial<C> X; 1037 GenSolvablePolynomial<C> XP; 1038 // solve system of linear equations for the coefficients of the univariate polynomial 1039 List<GenPolynomial<C>> ls; 1040 int z = -1; 1041 do { 1042 //System.out.println("ll = " + ll); 1043 GenSolvablePolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, ll); 1044 GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - ll); 1045 Pp = Pp.multiply(cp); 1046 P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(Pp); 1047 X = pfac.univariate(i, ll); 1048 XP = sred.leftNormalform(G, X); 1049 //System.out.println("XP = " + XP); 1050 GenSolvablePolynomial<GenPolynomial<C>> XPp = PolyUtil.<C> toRecursive(rfac, XP); 1051 GenSolvablePolynomial<GenPolynomial<C>> XPs = (GenSolvablePolynomial<GenPolynomial<C>>) XPp 1052 .sum(P); 1053 ls = new ArrayList<GenPolynomial<C>>(XPs.getMap().values()); 1054 //System.out.println("ls,1 = " + ls); 1055 ls = red.irreducibleSet(ls); 1056 z = bbc.commonZeroTest(ls); 1057 if (z != 0) { 1058 ll++; 1059 if (ll > vsdim) { 1060 logger.info("univariate construction, P = {}", P); 1061 logger.info("univariate construction, nf(P) = {}", XP); 1062 logger.info("G = {}", G); 1063 throw new ArithmeticException( 1064 "univariate polynomial degree greater than vector space dimansion"); 1065 } 1066 cpfac = cpfac.extend(1); 1067 rfac = new GenSolvablePolynomialRing<GenPolynomial<C>>(cpfac, pfac); 1068 P = PolyUtil.<C> extendCoefficients(rfac, P, 0, 0L); 1069 XPp = PolyUtil.<C> extendCoefficients(rfac, XPp, 0, 1L); 1070 P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(XPp); 1071 } 1072 } while (z != 0); // && ll <= 5 && !XP.isZERO() 1073 // construct result polynomial 1074 String var = pfac.getVars()[pfac.nvar - 1 - i]; 1075 GenSolvablePolynomialRing<C> ufac = new GenSolvablePolynomialRing<C>(cfac, 1, new TermOrder( 1076 TermOrder.INVLEX), new String[] { var }); 1077 GenSolvablePolynomial<C> pol = ufac.univariate(0, ll); 1078 for (GenPolynomial<C> pc : ls) { 1079 ExpVector e = pc.leadingExpVector(); 1080 if (e == null) { 1081 continue; 1082 } 1083 int[] v = e.dependencyOnVariables(); 1084 if (v == null || v.length == 0) { 1085 continue; 1086 } 1087 int vi = v[0]; 1088 C tc = pc.trailingBaseCoefficient(); 1089 tc = tc.negate(); 1090 GenSolvablePolynomial<C> pi = ufac.univariate(0, ll - 1 - vi); 1091 pi = pi.multiply(tc); 1092 pol = (GenSolvablePolynomial<C>) pol.sum(pi); 1093 } 1094 if (logger.isInfoEnabled()) { 1095 logger.info("univariate construction, pol = {}", pol); 1096 } 1097 return pol; 1098 } 1099 1100 1101 /** 1102 * Construct univariate solvable polynomials of minimal degree in all 1103 * variables in zero dimensional left ideal(G). 1104 * @return list of univariate polynomial of minimal degree in each variable 1105 * in ideal_left(G) 1106 */ 1107 public List<GenSolvablePolynomial<C>> constructUnivariate(List<GenSolvablePolynomial<C>> G) { 1108 List<GenSolvablePolynomial<C>> univs = new ArrayList<GenSolvablePolynomial<C>>(); 1109 if (G == null || G.isEmpty()) { 1110 return univs; 1111 } 1112 for (int i = G.get(0).ring.nvar - 1; i >= 0; i--) { 1113 GenSolvablePolynomial<C> u = constructUnivariate(i, G); 1114 univs.add(u); 1115 } 1116 return univs; 1117 } 1118 1119 1120 /** 1121 * Cleanup and terminate ThreadPool. 1122 */ 1123 public void terminate() { 1124 logger.info("terminate not implemented"); 1125 //throw new RuntimeException("get a stack trace"); 1126 } 1127 1128 1129 /** 1130 * Cancel ThreadPool. 1131 */ 1132 public int cancel() { 1133 logger.info("cancel not implemented"); 1134 return 0; 1135 } 1136 1137}