001/* 002 * $Id: SolvableGroebnerBaseAbstract.java 5280 2015-07-30 16:18:15Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.ListIterator; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.poly.ExpVector; 015import edu.jas.poly.GenPolynomial; 016import edu.jas.poly.GenPolynomialRing; 017import edu.jas.poly.GenSolvablePolynomial; 018import edu.jas.poly.GenSolvablePolynomialRing; 019import edu.jas.poly.QLRSolvablePolynomialRing; 020import edu.jas.poly.PolyUtil; 021import edu.jas.poly.PolynomialList; 022import edu.jas.poly.ModuleList; 023import edu.jas.poly.TermOrder; 024import edu.jas.structure.RingElem; 025import edu.jas.structure.RingFactory; 026import edu.jas.vector.BasicLinAlg; 027 028 029/** 030 * Solvable Groebner Bases abstract class. Implements common left, right and 031 * twosided Groebner bases and left, right and twosided GB tests. 032 * @param <C> coefficient type 033 * @author Heinz Kredel. 034 */ 035 036public abstract class SolvableGroebnerBaseAbstract<C extends RingElem<C>> implements SolvableGroebnerBase<C> { 037 038 039 private static final Logger logger = Logger.getLogger(SolvableGroebnerBaseAbstract.class); 040 041 042 private 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 = " + pi + ", pj = " + pj); 217 logger.info("s = " + s + ", h = " + 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 //System.out.println("is: q generated = " + q + ", p = " + p + ", x = " + x); 285 if (!q.isZERO()) { 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 return false; 308 } 309 } 310 } 311 return true; 312 } 313 314 315 /** 316 * Twosided Groebner base idempotence test. 317 * @param F solvable polynomial list. 318 * @return true, if F is equal to GB(F), else false. 319 */ 320 public boolean isTwosidedGBidem(List<GenSolvablePolynomial<C>> F) { 321 return isTwosidedGBidem(0, F); 322 } 323 324 325 /** 326 * Twosided Groebner base idempotence test. 327 * @param modv module variable number. 328 * @param F solvable polynomial list. 329 * @return true, if F is equal to GB(F), else false. 330 */ 331 public boolean isTwosidedGBidem(int modv, List<GenSolvablePolynomial<C>> F) { 332 if (F == null || F.isEmpty()) { 333 return true; 334 } 335 GenSolvablePolynomialRing<C> pring = F.get(0).ring; 336 List<GenSolvablePolynomial<C>> G = twosidedGB(modv, F); 337 PolynomialList<C> Fp = new PolynomialList<C>(pring, F); 338 PolynomialList<C> Gp = new PolynomialList<C>(pring, G); 339 return Fp.compareTo(Gp) == 0; 340 } 341 342 343 /** 344 * Right Groebner base test. 345 * @param F solvable polynomial list. 346 * @return true, if F is a right Groebner base, else false. 347 */ 348 public boolean isRightGB(List<GenSolvablePolynomial<C>> F) { 349 return isRightGB(0, F); 350 } 351 352 353 /** 354 * Right Groebner base test. 355 * @param modv number of module variables. 356 * @param F solvable polynomial list. 357 * @return true, if F is a right Groebner base, else false. 358 */ 359 public boolean isRightGB(int modv, List<GenSolvablePolynomial<C>> F) { 360 GenSolvablePolynomial<C> pi, pj, s, h; 361 for (int i = 0; i < F.size(); i++) { 362 pi = F.get(i); 363 //System.out.println("pi right = " + pi); 364 for (int j = i + 1; j < F.size(); j++) { 365 pj = F.get(j); 366 //System.out.println("pj right = " + pj); 367 if (!red.moduleCriterion(modv, pi, pj)) { 368 continue; 369 } 370 // if ( ! red.criterion4( pi, pj ) ) { continue; } 371 s = sred.rightSPolynomial(pi, pj); 372 if (s.isZERO()) { 373 continue; 374 } 375 //System.out.println("s right = " + s); 376 h = sred.rightNormalform(F, s); 377 if (!h.isZERO()) { 378 logger.info("isRightGB non zero h = " + h + " :: " + h.ring); 379 logger.info("p" + i + " = " + pi + ", p" + j + " = " + pj); 380 return false; 381 //} else { 382 //logger.info("isRightGB zero h = " + h); 383 } 384 } 385 } 386 return true; 387 } 388 389 390 /** 391 * Right Groebner base idempotence test. 392 * @param F solvable polynomial list. 393 * @return true, if F is equal to GB(F), else false. 394 */ 395 public boolean isRightGBidem(List<GenSolvablePolynomial<C>> F) { 396 return isRightGBidem(0, F); 397 } 398 399 400 /** 401 * Right Groebner base idempotence test. 402 * @param modv module variable number. 403 * @param F solvable polynomial list. 404 * @return true, if F is equal to GB(F), else false. 405 */ 406 public boolean isRightGBidem(int modv, List<GenSolvablePolynomial<C>> F) { 407 if (F == null || F.isEmpty()) { 408 return true; 409 } 410 GenSolvablePolynomialRing<C> pring = F.get(0).ring; 411 List<GenSolvablePolynomial<C>> G = rightGB(modv, F); 412 PolynomialList<C> Fp = new PolynomialList<C>(pring, F); 413 PolynomialList<C> Gp = new PolynomialList<C>(pring, G); 414 return Fp.compareTo(Gp) == 0; 415 } 416 417 418 /** 419 * Left Groebner base using pairlist class. 420 * @param F solvable polynomial list. 421 * @return leftGB(F) a left Groebner base of F. 422 */ 423 public List<GenSolvablePolynomial<C>> leftGB(List<GenSolvablePolynomial<C>> F) { 424 return leftGB(0, F); 425 } 426 427 428 /** 429 * Solvable Extended Groebner base using critical pair class. 430 * @param F solvable polynomial list. 431 * @return a container for an extended left Groebner base of F. 432 */ 433 public SolvableExtendedGB<C> extLeftGB(List<GenSolvablePolynomial<C>> F) { 434 return extLeftGB(0, F); 435 } 436 437 438 /** 439 * Solvable Extended Groebner base using critical pair class. 440 * @param modv module variable number. 441 * @param F polynomial list. 442 * @return a container for an extended left Groebner base G of F together 443 * with back-and-forth transformations. 444 */ 445 public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) { 446 throw new UnsupportedOperationException("extLeftGB not implemented in " 447 + this.getClass().getSimpleName()); 448 } 449 450 451 /** 452 * Left minimal ordered groebner basis. 453 * @param Gp a left Groebner base. 454 * @return leftGBmi(F) a minimal left Groebner base of Gp. 455 */ 456 public List<GenSolvablePolynomial<C>> leftMinimalGB(List<GenSolvablePolynomial<C>> Gp) { 457 ArrayList<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(); 458 ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator(); 459 for (GenSolvablePolynomial<C> a : Gp) { 460 // a = (SolvablePolynomial) it.next(); 461 if (a.length() != 0) { // always true 462 // already monic a = a.monic(); 463 G.add(a); 464 } 465 } 466 if (G.size() <= 1) { 467 return G; 468 } 469 470 ExpVector e; 471 ExpVector f; 472 GenSolvablePolynomial<C> a, p; 473 ArrayList<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(); 474 boolean mt; 475 476 while (G.size() > 0) { 477 a = G.remove(0); 478 e = a.leadingExpVector(); 479 480 it = G.listIterator(); 481 mt = false; 482 while (it.hasNext() && !mt) { 483 p = it.next(); 484 f = p.leadingExpVector(); 485 mt = e.multipleOf(f); 486 } 487 it = F.listIterator(); 488 while (it.hasNext() && !mt) { 489 p = it.next(); 490 f = p.leadingExpVector(); 491 mt = e.multipleOf(f); 492 } 493 if (!mt) { 494 F.add(a); 495 } else { 496 // System.out.println("dropped " + a.length()); 497 } 498 } 499 G = F; 500 if (G.size() <= 1) { 501 return G; 502 } 503 504 F = new ArrayList<GenSolvablePolynomial<C>>(); 505 while (G.size() > 0) { 506 a = G.remove(0); 507 // System.out.println("doing " + a.length()); 508 a = sred.leftNormalform(G, a); 509 a = sred.leftNormalform(F, a); 510 F.add(a); 511 } 512 return F; 513 } 514 515 516 /** 517 * Right minimal ordered groebner basis. 518 * @param Gp a right Groebner base. 519 * @return rightGBmi(F) a minimal right Groebner base of Gp. 520 */ 521 public List<GenSolvablePolynomial<C>> rightMinimalGB(List<GenSolvablePolynomial<C>> Gp) { 522 ArrayList<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(); 523 ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator(); 524 for (GenSolvablePolynomial<C> a : Gp) { 525 if (a.length() != 0) { // always true 526 G.add(a); 527 } 528 } 529 if (G.size() <= 1) { 530 return G; 531 } 532 533 ExpVector e; 534 ExpVector f; 535 GenSolvablePolynomial<C> a, p; 536 ArrayList<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(); 537 boolean mt; 538 539 while (G.size() > 0) { 540 a = G.remove(0); 541 e = a.leadingExpVector(); 542 543 it = G.listIterator(); 544 mt = false; 545 while (it.hasNext() && !mt) { 546 p = it.next(); 547 f = p.leadingExpVector(); 548 mt = e.multipleOf(f); 549 } 550 it = F.listIterator(); 551 while (it.hasNext() && !mt) { 552 p = it.next(); 553 f = p.leadingExpVector(); 554 mt = e.multipleOf(f); 555 } 556 if (!mt) { 557 F.add(a); 558 } else { 559 // System.out.println("dropped " + a.length()); 560 } 561 } 562 G = F; 563 if (G.size() <= 1) { 564 return G; 565 } 566 567 F = new ArrayList<GenSolvablePolynomial<C>>(); 568 while (G.size() > 0) { 569 a = G.remove(0); 570 // System.out.println("doing " + a.length()); 571 a = sred.rightNormalform(G, a); 572 a = sred.rightNormalform(F, a); 573 F.add(a); 574 } 575 return F; 576 } 577 578 579 /** 580 * Twosided Groebner base using pairlist class. 581 * @param Fp solvable polynomial list. 582 * @return tsGB(Fp) a twosided Groebner base of Fp. 583 */ 584 public List<GenSolvablePolynomial<C>> twosidedGB(List<GenSolvablePolynomial<C>> Fp) { 585 return twosidedGB(0, Fp); 586 } 587 588 589 /** 590 * Right Groebner base using opposite ring left GB. 591 * @param F solvable polynomial list. 592 * @return rightGB(F) a right Groebner base of F. 593 */ 594 public List<GenSolvablePolynomial<C>> rightGB(List<GenSolvablePolynomial<C>> F) { 595 return rightGB(0, F); 596 } 597 598 599 /** 600 * Right Groebner base using opposite ring left GB. 601 * @param modv number of module variables. 602 * @param F solvable polynomial list. 603 * @return rightGB(F) a right Groebner base of F. 604 */ 605 @SuppressWarnings("unchecked") 606 public List<GenSolvablePolynomial<C>> rightGB(int modv, List<GenSolvablePolynomial<C>> F) { 607 List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F); 608 if (G.size() <= 1) { 609 return G; 610 } 611 GenSolvablePolynomialRing<C> ring = G.get(0).ring; // assert != null 612 GenSolvablePolynomialRing<C> rring = ring.reverse(true); //true 613 //System.out.println("reversed ring = " + rring); 614 GenSolvablePolynomial<C> q; 615 List<GenSolvablePolynomial<C>> rF; 616 rF = new ArrayList<GenSolvablePolynomial<C>>(F.size()); 617 for (GenSolvablePolynomial<C> p : F) { 618 if (p != null) { 619 q = (GenSolvablePolynomial<C>) p.reverse(rring); 620 rF.add(q); 621 } 622 } 623 if (logger.isInfoEnabled()) { 624 PolynomialList<C> pl = new PolynomialList<C>(rring, rF); 625 logger.info("reversed problem = " + pl.toScript()); 626 } 627 List<GenSolvablePolynomial<C>> rG = leftGB(modv, rF); 628 if (debug) { 629 //PolynomialList<C> pl = new PolynomialList<C>(rring,rG); 630 //logger.info("reversed GB = " + pl); 631 long t = System.currentTimeMillis(); 632 boolean isit = isLeftGB(rG); 633 t = System.currentTimeMillis() - t; 634 logger.info("is left GB = " + isit + ", in " + t + " milliseconds"); 635 } 636 //System.out.println("reversed left GB = " + rG); 637 ring = rring.reverse(true); // true 638 G = new ArrayList<GenSolvablePolynomial<C>>(rG.size()); 639 for (GenSolvablePolynomial<C> p : rG) { 640 if (p != null) { 641 q = (GenSolvablePolynomial<C>) p.reverse(ring); 642 G.add(q); 643 } 644 } 645 if (debug) { 646 //PolynomialList<C> pl = new PolynomialList<C>(ring,G); 647 //logger.info("GB = " + pl); 648 long t = System.currentTimeMillis(); 649 boolean isit = isRightGB(G); 650 t = System.currentTimeMillis() - t; 651 logger.info("is right GB = " + isit + ", in " + t + " milliseconds"); 652 } 653 return G; 654 } 655 656 657 /** 658 * Module left Groebner base test. 659 * @param M a module basis. 660 * @return true, if M is a left Groebner base, else false. 661 */ 662 public boolean isLeftGB(ModuleList<C> M) { 663 if (M == null || M.list == null) { 664 return true; 665 } 666 if (M.rows == 0 || M.cols == 0) { 667 return true; 668 } 669 int modv = M.cols; // > 0 670 PolynomialList<C> F = M.getPolynomialList(); 671 return isLeftGB(modv, F.castToSolvableList()); 672 } 673 674 675 /** 676 * Left Groebner base using pairlist class. 677 * @param M a module basis. 678 * @return leftGB(M) a left Groebner base for M. 679 */ 680 @SuppressWarnings("unchecked") 681 public ModuleList<C> leftGB(ModuleList<C> M) { 682 ModuleList<C> N = M; 683 if (M == null || M.list == null) { 684 return N; 685 } 686 if (M.rows == 0 || M.cols == 0) { 687 return N; 688 } 689 PolynomialList<C> F = M.getPolynomialList(); 690 if (debug) { 691 logger.info("F left +++++++++++++++++++ \n" + F); 692 } 693 GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) F.ring; 694 int modv = M.cols; 695 List<GenSolvablePolynomial<C>> G = leftGB(modv, F.castToSolvableList()); 696 F = new PolynomialList<C>(sring, G); 697 if (debug) { 698 logger.info("G left +++++++++++++++++++ \n" + F); 699 } 700 N = F.getModuleList(modv); 701 return N; 702 } 703 704 705 /** 706 * Module twosided Groebner base test. 707 * @param M a module basis. 708 * @return true, if M is a twosided Groebner base, else false. 709 */ 710 public boolean isTwosidedGB(ModuleList<C> M) { 711 if (M == null || M.list == null) { 712 return true; 713 } 714 if (M.rows == 0 || M.cols == 0) { 715 return true; 716 } 717 PolynomialList<C> F = M.getPolynomialList(); 718 int modv = M.cols; // > 0 719 return isTwosidedGB(modv, F.castToSolvableList()); 720 } 721 722 723 /** 724 * Twosided Groebner base using pairlist class. 725 * @param M a module basis. 726 * @return tsGB(M) a twosided Groebner base for M. 727 */ 728 @SuppressWarnings("unchecked") 729 public ModuleList<C> twosidedGB(ModuleList<C> M) { 730 ModuleList<C> N = M; 731 if (M == null || M.list == null) { 732 return N; 733 } 734 if (M.rows == 0 || M.cols == 0) { 735 return N; 736 } 737 PolynomialList<C> F = M.getPolynomialList(); 738 GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) F.ring; 739 int modv = M.cols; 740 List<GenSolvablePolynomial<C>> G = twosidedGB(modv, F.castToSolvableList()); 741 F = new PolynomialList<C>(sring, G); 742 N = F.getModuleList(modv); 743 return N; 744 } 745 746 747 /** 748 * Module right Groebner base test. 749 * @param M a module basis. 750 * @return true, if M is a right Groebner base, else false. 751 */ 752 public boolean isRightGB(ModuleList<C> M) { 753 if (M == null || M.list == null) { 754 return true; 755 } 756 if (M.rows == 0 || M.cols == 0) { 757 return true; 758 } 759 int modv = M.cols; // > 0 760 PolynomialList<C> F = M.getPolynomialList(); 761 //System.out.println("F test = " + F); 762 return isRightGB(modv, F.castToSolvableList()); 763 } 764 765 766 /** 767 * Right Groebner base using pairlist class. 768 * @param M a module basis. 769 * @return rightGB(M) a right Groebner base for M. 770 */ 771 @SuppressWarnings("unchecked") 772 public ModuleList<C> rightGB(ModuleList<C> M) { 773 ModuleList<C> N = M; 774 if (M == null || M.list == null) { 775 return N; 776 } 777 if (M.rows == 0 || M.cols == 0) { 778 return N; 779 } 780 if (debug) { 781 logger.info("M ====================== \n" + M); 782 } 783 TermOrder to = M.ring.tord; 784 if (to.getSplit() <= M.ring.nvar) { 785 throw new IllegalArgumentException("extended TermOrders not supported for rightGBs: " + to); 786 } 787 List<List<GenSolvablePolynomial<C>>> mlist = M.castToSolvableList(); 788 GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) M.ring; 789 GenSolvablePolynomialRing<C> rring = sring.reverse(true); //true 790 sring = rring.reverse(true); // true 791 792 List<List<GenSolvablePolynomial<C>>> nlist = new ArrayList<List<GenSolvablePolynomial<C>>>(M.rows); 793 for (List<GenSolvablePolynomial<C>> row : mlist) { 794 List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row.size()); 795 for (GenSolvablePolynomial<C> elem : row) { 796 GenSolvablePolynomial<C> nelem = (GenSolvablePolynomial<C>) elem.reverse(rring); 797 nrow.add(nelem); 798 } 799 nlist.add(nrow); 800 } 801 ModuleList<C> rM = new ModuleList<C>(rring, nlist); 802 if (debug) { 803 logger.info("rM -------------------- \n" + rM); 804 } 805 ModuleList<C> rMg = leftGB(rM); 806 if (debug) { 807 logger.info("rMg -------------------- \n" + rMg); 808 logger.info("isLeftGB(rMg) ---------- " + isLeftGB(rMg)); 809 } 810 mlist = rMg.castToSolvableList(); 811 nlist = new ArrayList<List<GenSolvablePolynomial<C>>>(rMg.rows); 812 for (List<GenSolvablePolynomial<C>> row : mlist) { 813 List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row.size()); 814 for (GenSolvablePolynomial<C> elem : row) { 815 GenSolvablePolynomial<C> nelem = (GenSolvablePolynomial<C>) elem.reverse(sring); 816 nrow.add(nelem); 817 } 818 nlist.add(nrow); 819 } 820 ModuleList<C> Mg = new ModuleList<C>(sring, nlist); 821 if (debug) { 822 logger.info("Mg -------------------- \n" + Mg); 823 logger.info("isRightGB(Mg) --------- " + isRightGB(Mg)); 824 } 825 return Mg; 826 } 827 828 829 /** 830 * Test if left reduction matrix. 831 * @param exgb an SolvableExtendedGB container. 832 * @return true, if exgb contains a left reduction matrix, else false. 833 */ 834 public boolean isLeftReductionMatrix(SolvableExtendedGB<C> exgb) { 835 if (exgb == null) { 836 return true; 837 } 838 return isLeftReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F); 839 } 840 841 842 /** 843 * Test if left reduction matrix. 844 * @param F a solvable polynomial list. 845 * @param G a left Groebner base. 846 * @param Mf a possible left reduction matrix. 847 * @param Mg a possible left reduction matrix. 848 * @return true, if Mg and Mf are left reduction matrices, else false. 849 */ 850 public boolean isLeftReductionMatrix(List<GenSolvablePolynomial<C>> F, List<GenSolvablePolynomial<C>> G, 851 List<List<GenSolvablePolynomial<C>>> Mf, List<List<GenSolvablePolynomial<C>>> Mg) { 852 // no more check G and Mg: G * Mg[i] == 0 853 // check F and Mg: F * Mg[i] == G[i] 854 int k = 0; 855 for (List<GenSolvablePolynomial<C>> row : Mg) { 856 boolean t = sred.isLeftReductionNF(row, F, G.get(k), null); 857 if (!t) { 858 System.out.println("row = " + row); 859 System.out.println("F = " + F); 860 System.out.println("Gk = " + G.get(k)); 861 logger.info("F isLeftReductionMatrix s, k = " + F.size() + ", " + k); 862 return false; 863 } 864 k++; 865 } 866 // check G and Mf: G * Mf[i] == F[i] 867 k = 0; 868 for (List<GenSolvablePolynomial<C>> row : Mf) { 869 boolean t = sred.isLeftReductionNF(row, G, F.get(k), null); 870 if (!t) { 871 logger.error("G isLeftReductionMatrix s, k = " + G.size() + ", " + k); 872 return false; 873 } 874 k++; 875 } 876 return true; 877 } 878 879 880 /** 881 * Ideal common zero test. 882 * @return -1, 0 or 1 if dimension(this) &eq; -1, 0 or ≥ 1. 883 */ 884 public int commonZeroTest(List<GenSolvablePolynomial<C>> A) { 885 List<GenPolynomial<C>> cA = PolynomialList.<C> castToList(A); 886 return cbb.commonZeroTest(cA); 887 } 888 889 890 /** 891 * Univariate head term degrees. 892 * @param A list of solvable polynomials. 893 * @return a list of the degrees of univariate head terms. 894 */ 895 public List<Long> univariateDegrees(List<GenSolvablePolynomial<C>> A) { 896 List<GenPolynomial<C>> cA = PolynomialList.<C> castToList(A); 897 return cbb.univariateDegrees(cA); 898 } 899 900 901 /** 902 * Construct univariate solvable polynomial of minimal degree in variable i 903 * of a zero dimensional ideal(G). 904 * @param i variable index. 905 * @param G list of solvable polynomials, a monic reduced left Gröbner 906 * base of a zero dimensional ideal. 907 * @return univariate solvable polynomial of minimal degree in variable i in 908 * ideal_left(G) 909 */ 910 public GenSolvablePolynomial<C> constructUnivariate(int i, List<GenSolvablePolynomial<C>> G) { 911 if (G == null || G.size() == 0) { 912 throw new IllegalArgumentException("G may not be null or empty"); 913 } 914 List<Long> ud = univariateDegrees(G); 915 if (ud.size() <= i) { 916 //logger.info("univ pol, ud = " + ud); 917 throw new IllegalArgumentException("ideal(G) not zero dimensional " + ud); 918 } 919 int ll = 0; 920 Long di = ud.get(i); 921 if (di != null) { 922 ll = (int) (long) di; 923 } else { 924 throw new IllegalArgumentException("ideal(G) not zero dimensional"); 925 } 926 long vsdim = 1; 927 for (Long d : ud) { 928 if (d != null) { 929 vsdim *= d; 930 } 931 } 932 logger.info("univariate construction, deg = " + ll + ", vsdim = " + vsdim); 933 GenSolvablePolynomialRing<C> pfac = G.get(0).ring; 934 RingFactory<C> cfac = pfac.coFac; 935 936 GenPolynomialRing<C> cpfac = new GenPolynomialRing<C>(cfac, ll, new TermOrder(TermOrder.INVLEX)); 937 GenSolvablePolynomialRing<GenPolynomial<C>> rfac = new GenSolvablePolynomialRing<GenPolynomial<C>>( 938 cpfac, pfac); // relations 939 GenSolvablePolynomial<GenPolynomial<C>> P = rfac.getZERO(); 940 for (int k = 0; k < ll; k++) { 941 GenSolvablePolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, k); 942 GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - k); 943 Pp = Pp.multiply(cp); 944 P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(Pp); 945 } 946 if (debug) { 947 logger.info("univariate construction, P = " + P); 948 logger.info("univariate construction, deg_*(G) = " + ud); 949 //throw new RuntimeException("check"); 950 } 951 GroebnerBaseAbstract<C> bbc = new GroebnerBaseSeq<C>(); 952 GenSolvablePolynomial<C> X; 953 GenSolvablePolynomial<C> XP; 954 // solve system of linear equations for the coefficients of the univariate polynomial 955 List<GenPolynomial<C>> ls; 956 int z = -1; 957 do { 958 //System.out.println("ll = " + ll); 959 GenSolvablePolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, ll); 960 GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - ll); 961 Pp = Pp.multiply(cp); 962 P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(Pp); 963 X = pfac.univariate(i, ll); 964 XP = sred.leftNormalform(G, X); 965 //System.out.println("XP = " + XP); 966 GenSolvablePolynomial<GenPolynomial<C>> XPp = PolyUtil.<C> toRecursive(rfac, XP); 967 GenSolvablePolynomial<GenPolynomial<C>> XPs = (GenSolvablePolynomial<GenPolynomial<C>>) XPp 968 .sum(P); 969 ls = new ArrayList<GenPolynomial<C>>(XPs.getMap().values()); 970 //System.out.println("ls,1 = " + ls); 971 ls = red.irreducibleSet(ls); 972 z = bbc.commonZeroTest(ls); 973 if (z != 0) { 974 ll++; 975 if (ll > vsdim) { 976 logger.info("univariate construction, P = " + P); 977 logger.info("univariate construction, nf(P) = " + XP); 978 logger.info("G = " + G); 979 throw new ArithmeticException( 980 "univariate polynomial degree greater than vector space dimansion"); 981 } 982 cpfac = cpfac.extend(1); 983 rfac = new GenSolvablePolynomialRing<GenPolynomial<C>>(cpfac, pfac); 984 P = PolyUtil.<C> extendCoefficients(rfac, P, 0, 0L); 985 XPp = PolyUtil.<C> extendCoefficients(rfac, XPp, 0, 1L); 986 P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(XPp); 987 } 988 } while (z != 0); // && ll <= 5 && !XP.isZERO() 989 // construct result polynomial 990 String var = pfac.getVars()[pfac.nvar - 1 - i]; 991 GenSolvablePolynomialRing<C> ufac = new GenSolvablePolynomialRing<C>(cfac, 1, new TermOrder( 992 TermOrder.INVLEX), new String[] { var }); 993 GenSolvablePolynomial<C> pol = ufac.univariate(0, ll); 994 for (GenPolynomial<C> pc : ls) { 995 ExpVector e = pc.leadingExpVector(); 996 if (e == null) { 997 continue; 998 } 999 int[] v = e.dependencyOnVariables(); 1000 if (v == null || v.length == 0) { 1001 continue; 1002 } 1003 int vi = v[0]; 1004 C tc = pc.trailingBaseCoefficient(); 1005 tc = tc.negate(); 1006 GenSolvablePolynomial<C> pi = ufac.univariate(0, ll - 1 - vi); 1007 pi = pi.multiply(tc); 1008 pol = (GenSolvablePolynomial<C>) pol.sum(pi); 1009 } 1010 if (logger.isInfoEnabled()) { 1011 logger.info("univariate construction, pol = " + pol); 1012 } 1013 return pol; 1014 } 1015 1016 1017 /** 1018 * Construct univariate solvable polynomials of minimal degree in all 1019 * variables in zero dimensional left ideal(G). 1020 * @return list of univariate polynomial of minimal degree in each variable 1021 * in ideal_left(G) 1022 */ 1023 public List<GenSolvablePolynomial<C>> constructUnivariate(List<GenSolvablePolynomial<C>> G) { 1024 List<GenSolvablePolynomial<C>> univs = new ArrayList<GenSolvablePolynomial<C>>(); 1025 if (G == null || G.isEmpty()) { 1026 return univs; 1027 } 1028 for (int i = G.get(0).ring.nvar - 1; i >= 0; i--) { 1029 GenSolvablePolynomial<C> u = constructUnivariate(i, G); 1030 univs.add(u); 1031 } 1032 return univs; 1033 } 1034 1035 1036 /** 1037 * Cleanup and terminate ThreadPool. 1038 */ 1039 public void terminate() { 1040 logger.info("terminate not implemented"); 1041 //throw new RuntimeException("get a stack trace"); 1042 } 1043 1044 1045 /** 1046 * Cancel ThreadPool. 1047 */ 1048 public int cancel() { 1049 logger.info("cancel not implemented"); 1050 return 0; 1051 } 1052 1053}