001/* 002 * $Id: SolvableIdeal.java 5267 2015-07-27 17:57:50Z kredel $ 003 */ 004 005package edu.jas.application; 006 007 008import java.io.Serializable; 009import java.util.ArrayList; 010import java.util.List; 011 012import org.apache.log4j.Logger; 013 014import edu.jas.gb.SolvableExtendedGB; 015import edu.jas.gb.SolvableGroebnerBaseAbstract; 016import edu.jas.gb.SolvableGroebnerBaseSeq; 017import edu.jas.gb.SolvableReduction; 018import edu.jas.gb.SolvableReductionSeq; 019import edu.jas.gbufd.PolyGBUtil; 020import edu.jas.gbufd.SGBFactory; 021import edu.jas.gbufd.SolvableSyzygyAbstract; 022import edu.jas.gbufd.SolvableSyzygySeq; 023import edu.jas.poly.GenSolvablePolynomial; 024import edu.jas.poly.GenSolvablePolynomialRing; 025import edu.jas.poly.PolyUtil; 026import edu.jas.poly.PolynomialList; 027import edu.jas.structure.GcdRingElem; 028import edu.jas.structure.NotInvertibleException; 029 030 031/** 032 * Solvable Ideal implements some methods for ideal arithmetic, for example sum, 033 * intersection, quotient. <b>Note:</b> only left ideals at the moment. 034 * @author Heinz Kredel 035 */ 036public class SolvableIdeal<C extends GcdRingElem<C>> implements Comparable<SolvableIdeal<C>>, Serializable { 037 038 039 private static final Logger logger = Logger.getLogger(SolvableIdeal.class); 040 041 042 private final boolean debug = logger.isDebugEnabled(); 043 044 045 /** 046 * Side variant of ideal. 047 */ 048 public static enum Side { 049 left, right, twosided 050 } 051 052 053 /** 054 * The data structure is a PolynomialList. 055 */ 056 protected PolynomialList<C> list; 057 058 059 /** 060 * Indicator if list is a Groebner Base. 061 */ 062 protected boolean isGB; 063 064 065 /** 066 * Indicator of side of Groebner Base. 067 */ 068 protected Side sided; 069 070 071 /** 072 * Indicator if test has been performed if this is a Groebner Base. 073 */ 074 protected boolean testGB; 075 076 077 /** 078 * Indicator if list has optimized term order. 079 */ 080 protected boolean isTopt; 081 082 083 /** 084 * Groebner base engine. 085 */ 086 protected final SolvableGroebnerBaseAbstract<C> bb; 087 088 089 /** 090 * Reduction engine. 091 */ 092 protected final SolvableReduction<C> red; 093 094 095 /** 096 * Constructor. 097 * @param ring solvable polynomial ring 098 */ 099 public SolvableIdeal(GenSolvablePolynomialRing<C> ring) { 100 this(ring, new ArrayList<GenSolvablePolynomial<C>>()); 101 } 102 103 104 /** 105 * Constructor. 106 * @param ring solvable polynomial ring 107 * @param F list of solvable polynomials 108 */ 109 public SolvableIdeal(GenSolvablePolynomialRing<C> ring, List<GenSolvablePolynomial<C>> F) { 110 this(new PolynomialList<C>(ring, F)); 111 } 112 113 114 /** 115 * Constructor. 116 * @param ring solvable polynomial ring 117 * @param F list of solvable polynomials 118 * @param gb true if F is known to be a Groebner Base, else false 119 */ 120 public SolvableIdeal(GenSolvablePolynomialRing<C> ring, List<GenSolvablePolynomial<C>> F, boolean gb) { 121 this(new PolynomialList<C>(ring, F), gb); 122 } 123 124 125 /** 126 * Constructor. 127 * @param ring solvable polynomial ring 128 * @param F list of solvable polynomials 129 * @param gb true if F is known to be a Groebner Base, else false 130 * @param topt true if term order is optimized, else false 131 */ 132 public SolvableIdeal(GenSolvablePolynomialRing<C> ring, List<GenSolvablePolynomial<C>> F, boolean gb, 133 boolean topt) { 134 this(new PolynomialList<C>(ring, F), gb, topt); 135 } 136 137 138 /** 139 * Constructor. 140 * @param ring solvable polynomial ring 141 * @param F list of solvable polynomials 142 * @param gb true if F is known to be a Groebner Base, else false 143 * @param s side variant of ideal or Groebner Base 144 */ 145 public SolvableIdeal(GenSolvablePolynomialRing<C> ring, List<GenSolvablePolynomial<C>> F, boolean gb, 146 Side s) { 147 this(new PolynomialList<C>(ring, F), gb, false, s); 148 } 149 150 151 /** 152 * Constructor. 153 * @param list solvable polynomial list 154 */ 155 public SolvableIdeal(PolynomialList<C> list) { 156 this(list, false); 157 } 158 159 160 /** 161 * Constructor. 162 * @param list solvable polynomial list 163 * @param bb Groebner Base engine 164 * @param red Reduction engine 165 */ 166 public SolvableIdeal(PolynomialList<C> list, SolvableGroebnerBaseAbstract<C> bb, SolvableReduction<C> red) { 167 this(list, false, bb, red); 168 } 169 170 171 /** 172 * Constructor. 173 * @param list solvable polynomial list 174 * @param gb true if list is known to be a Groebner Base, else false 175 */ 176 public SolvableIdeal(PolynomialList<C> list, boolean gb) { 177 //this(list, gb, new SolvableGroebnerBaseSeq<C>(), new SolvableReductionSeq<C>()); 178 this(list, gb, SGBFactory.getImplementation(list.ring.coFac), new SolvableReductionSeq<C>()); 179 } 180 181 182 /** 183 * Constructor. 184 * @param list solvable polynomial list 185 * @param gb true if list is known to be a Groebner Base, else false 186 * @param topt true if term order is optimized, else false 187 */ 188 public SolvableIdeal(PolynomialList<C> list, boolean gb, boolean topt) { 189 //this(list, gb, topt, new SolvableGroebnerBaseSeq<C>(), new SolvableReductionSeq<C>()); 190 this(list, gb, topt, SGBFactory.getImplementation(list.ring.coFac), new SolvableReductionSeq<C>()); 191 } 192 193 194 /** 195 * Constructor. 196 * @param list solvable polynomial list 197 * @param gb true if list is known to be a Groebner Base, else false 198 * @param s side variant of ideal or Groebner Base 199 */ 200 public SolvableIdeal(PolynomialList<C> list, boolean gb, Side s) { 201 //this(list, gb, false, new SolvableGroebnerBaseSeq<C>(), new SolvableReductionSeq<C>()); 202 this(list, gb, false, SGBFactory.getImplementation(list.ring.coFac), new SolvableReductionSeq<C>(), s); 203 } 204 205 206 /** 207 * Constructor. 208 * @param list solvable polynomial list 209 * @param gb true if list is known to be a Groebner Base, else false 210 * @param topt true if term order is optimized, else false 211 * @param s side variant of ideal or Groebner Base 212 */ 213 public SolvableIdeal(PolynomialList<C> list, boolean gb, boolean topt, Side s) { 214 //this(list, gb, topt, new SolvableGroebnerBaseSeq<C>(), new SolvableReductionSeq<C>()); 215 this(list, gb, topt, SGBFactory.getImplementation(list.ring.coFac), new SolvableReductionSeq<C>(), s); 216 } 217 218 219 /** 220 * Constructor. 221 * @param list solvable polynomial list 222 * @param gb true if list is known to be a Groebner Base, else false 223 * @param bb Groebner Base engine 224 * @param red Reduction engine 225 */ 226 public SolvableIdeal(PolynomialList<C> list, boolean gb, SolvableGroebnerBaseAbstract<C> bb, 227 SolvableReduction<C> red) { 228 this(list, gb, false, bb, red); 229 } 230 231 232 /** 233 * Constructor. 234 * @param list solvable polynomial list 235 * @param gb true if list is known to be a Groebner Base, else false 236 * @param bb Groebner Base engine 237 */ 238 public SolvableIdeal(PolynomialList<C> list, boolean gb, SolvableGroebnerBaseAbstract<C> bb) { 239 this(list, gb, false, bb, bb.sred); 240 } 241 242 243 /** 244 * Constructor. 245 * @param list solvable polynomial list 246 * @param gb true if list is known to be a Groebner Base, else false 247 * @param topt true if term order is optimized, else false 248 * @param bb Groebner Base engine 249 */ 250 public SolvableIdeal(PolynomialList<C> list, boolean gb, boolean topt, SolvableGroebnerBaseAbstract<C> bb) { 251 this(list, gb, topt, bb, bb.sred); 252 } 253 254 255 /** 256 * Constructor. 257 * @param list solvable polynomial list 258 * @param gb true if list is known to be a Groebner Base, else false 259 * @param topt true if term order is optimized, else false 260 * @param bb Groebner Base engine 261 * @param red Reduction engine 262 */ 263 public SolvableIdeal(PolynomialList<C> list, boolean gb, boolean topt, 264 SolvableGroebnerBaseAbstract<C> bb, SolvableReduction<C> red) { 265 this(list, gb, topt, bb, bb.sred, Side.left ); 266 } 267 268 269 /** 270 * Constructor. 271 * @param list solvable polynomial list 272 * @param gb true if list is known to be a Groebner Base, else false 273 * @param topt true if term order is optimized, else false 274 * @param bb Groebner Base engine 275 * @param red Reduction engine 276 * @param s side variant of ideal or Groebner Base 277 */ 278 public SolvableIdeal(PolynomialList<C> list, boolean gb, boolean topt, 279 SolvableGroebnerBaseAbstract<C> bb, SolvableReduction<C> red, Side s) { 280 if (list == null || list.list == null) { 281 throw new IllegalArgumentException("list and list.list may not be null"); 282 } 283 this.list = list; 284 this.isGB = gb; 285 this.isTopt = topt; 286 this.testGB = (gb ? true : false); // ?? 287 this.bb = bb; 288 this.red = red; 289 if (s == null) { 290 s = Side.left; // default 291 } 292 this.sided = s; 293 } 294 295 296 /** 297 * Clone this. 298 * @return a copy of this. 299 */ 300 public SolvableIdeal<C> copy() { 301 return new SolvableIdeal<C>(list.copy(), isGB, isTopt, bb, red, sided); 302 } 303 304 305 /** 306 * Get the List of GenSolvablePolynomials. 307 * @return (cast) list.list 308 */ 309 public List<GenSolvablePolynomial<C>> getList() { 310 return list.getSolvableList(); 311 } 312 313 314 /** 315 * Get the GenSolvablePolynomialRing. 316 * @return (cast) list.ring 317 */ 318 public GenSolvablePolynomialRing<C> getRing() { 319 return list.getSolvableRing(); 320 } 321 322 323 /** 324 * Get the zero ideal. 325 * @return ideal(0) 326 */ 327 public SolvableIdeal<C> getZERO() { 328 List<GenSolvablePolynomial<C>> z = new ArrayList<GenSolvablePolynomial<C>>(0); 329 PolynomialList<C> pl = new PolynomialList<C>(getRing(), z); 330 return new SolvableIdeal<C>(pl, true, isTopt, bb, red, sided); 331 } 332 333 334 /** 335 * Get the one ideal. 336 * @return ideal(1) 337 */ 338 public SolvableIdeal<C> getONE() { 339 List<GenSolvablePolynomial<C>> one = new ArrayList<GenSolvablePolynomial<C>>(1); 340 one.add(getRing().getONE()); 341 PolynomialList<C> pl = new PolynomialList<C>(getRing(), one); 342 return new SolvableIdeal<C>(pl, true, isTopt, bb, red, sided); 343 } 344 345 346 /** 347 * String representation of the solvable ideal. 348 * @see java.lang.Object#toString() 349 */ 350 @Override 351 public String toString() { 352 return list.toString() + " # " + sided; 353 } 354 355 356 /** 357 * Get a scripting compatible string representation. 358 * @return script compatible representation for this Element. 359 * @see edu.jas.structure.Element#toScript() 360 */ 361 public String toScript() { 362 // any script case 363 return list.toScript() + " # " + sided; 364 } 365 366 367 /** 368 * Comparison with any other object. <b>Note:</b> If not both ideals are 369 * Groebner Bases, then false may be returned even the ideals are equal. 370 * @see java.lang.Object#equals(java.lang.Object) 371 */ 372 @Override 373 @SuppressWarnings("unchecked") 374 public boolean equals(Object b) { 375 if (!(b instanceof SolvableIdeal)) { 376 logger.warn("equals no Ideal"); 377 return false; 378 } 379 SolvableIdeal<C> B = null; 380 try { 381 B = (SolvableIdeal<C>) b; 382 } catch (ClassCastException ignored) { 383 return false; 384 } 385 //if ( isGB && B.isGB ) { 386 // return list.equals( B.list ); requires also monic polys 387 //} else { // compute GBs ? 388 return this.contains(B) && B.contains(this); 389 //} 390 } 391 392 393 /** 394 * SolvableIdeal comparison. 395 * @param L other solvable ideal. 396 * @return compareTo() of polynomial lists. 397 */ 398 public int compareTo(SolvableIdeal<C> L) { 399 return list.compareTo(L.list); 400 } 401 402 403 /** 404 * Hash code for this solvable ideal. 405 * @see java.lang.Object#hashCode() 406 */ 407 @Override 408 public int hashCode() { 409 int h; 410 h = list.hashCode(); 411 if (isGB) { 412 h = h << 1; 413 } 414 if (testGB) { 415 h += 1; 416 } 417 return h; 418 } 419 420 421 /** 422 * Test if ZERO ideal. 423 * @return true, if this is the 0 ideal, else false 424 */ 425 public boolean isZERO() { 426 return list.isZERO(); 427 } 428 429 430 /** 431 * Test if ONE is contained in the ideal. To test for a proper ideal use 432 * <code>! id.isONE()</code>. 433 * @return true, if this is the 1 ideal, else false 434 */ 435 public boolean isONE() { 436 return list.isONE(); 437 } 438 439 440 /** 441 * Test if this is a left Groebner base. 442 * @return true, if this is a left Groebner base, else false 443 */ 444 public boolean isGB() { 445 if (testGB && sided == Side.left) { 446 return isGB; 447 } 448 logger.warn("isLeftGB computing"); 449 boolean igb = bb.isLeftGB(getList()); 450 if (sided != Side.left) { 451 logger.warn("wrong usage for is left sided GB: " + sided); 452 //sided = Side.left; 453 } else { 454 isGB = igb; 455 testGB = true; 456 } 457 return igb; 458 } 459 460 461 /** 462 * Do Groebner Base. compute the left Groebner Base for this ideal. 463 */ 464 @SuppressWarnings("unchecked") 465 public void doGB() { 466 if (isGB && sided == Side.left) { 467 return; 468 } 469 if (isGB && sided == Side.twosided) { 470 return; 471 } 472 if (sided == Side.right) { 473 logger.warn("wrong usage for left sided GB: " + sided); 474 throw new IllegalArgumentException("wrong usage for left sided GB: " + sided); 475 } 476 List<GenSolvablePolynomial<C>> G = getList(); 477 logger.info("leftGB computing = " + G); 478 G = bb.leftGB(G); 479 //if (isTopt) { 480 // List<Integer> perm = ((OptimizedPolynomialList<C>) list).perm; 481 // list = new OptimizedPolynomialList<C>(perm, getRing(), G); 482 //} else { 483 list = new PolynomialList<C>(getRing(), G); 484 //} 485 isGB = true; 486 testGB = true; 487 sided = Side.left; 488 return; 489 } 490 491 492 /** 493 * Groebner Base. Get a left Groebner Base for this ideal. 494 * @return leftGB(this) 495 */ 496 public SolvableIdeal<C> GB() { 497 if (isGB && sided == Side.left) { 498 return this; 499 } 500 doGB(); 501 return this; 502 } 503 504 505 /** 506 * Test if this is a twosided Groebner base. 507 * @return true, if this is a twosided Groebner base, else false 508 */ 509 public boolean isTwosidedGB() { 510 if (testGB && sided == Side.twosided) { 511 return isGB; 512 } 513 logger.warn("isTwosidedGB computing"); 514 isGB = bb.isTwosidedGB(getList()); 515 testGB = true; 516 sided = Side.twosided; 517 return isGB; 518 } 519 520 521 /** 522 * Groebner Base. Get a twosided Groebner Base for this ideal. 523 * @return twosidedGB(this) 524 */ 525 public SolvableIdeal<C> twosidedGB() { 526 if (isGB && sided == Side.twosided) { 527 return this; 528 } 529 //logger.warn("GB computing"); 530 List<GenSolvablePolynomial<C>> G = getList(); 531 logger.info("twosidedGB computing = " + G); 532 G = bb.twosidedGB(G); 533 PolynomialList<C> li = new PolynomialList<C>(getRing(), G); 534 SolvableIdeal<C> tsgb = new SolvableIdeal<C>(li, true, true, bb, red, Side.twosided); 535 return tsgb; 536 } 537 538 539 /** 540 * Test if this is a right Groebner base. 541 * @return true, if this is a right Groebner base, else false 542 */ 543 public boolean isRightGB() { 544 if (testGB && sided == Side.right) { 545 return isGB; 546 } 547 if (isGB && sided == Side.twosided) { 548 return true; 549 } 550 logger.warn("isRightGB computing"); 551 isGB = bb.isRightGB(getList()); 552 testGB = true; 553 sided = Side.right; 554 return isGB; 555 } 556 557 558 /** 559 * Groebner Base. Get a right Groebner Base for this ideal. 560 * @return rightGB(this) 561 */ 562 public SolvableIdeal<C> rightGB() { 563 if (isGB && sided == Side.twosided) { 564 return this; 565 } 566 if (isGB && sided == Side.right) { 567 return this; 568 } 569 //logger.warn("GB computing"); 570 List<GenSolvablePolynomial<C>> G = getList(); 571 logger.info("rightGB computing = " + G); 572 G = bb.rightGB(G); 573 PolynomialList<C> li = new PolynomialList<C>(getRing(), G); 574 SolvableIdeal<C> rgb = new SolvableIdeal<C>(li, true, true, bb, red, Side.right); 575 return rgb; 576 } 577 578 579 /** 580 * Solvable ideal containment. Test if B is contained in this ideal. Note: 581 * this is eventually modified to become a Groebner Base. 582 * @param B solvable ideal 583 * @return true, if B is contained in this, else false 584 */ 585 public boolean contains(SolvableIdeal<C> B) { 586 if (B == null || B.isZERO()) { 587 return true; 588 } 589 return contains(B.getList()); 590 } 591 592 593 /** 594 * Solvable ideal containment. Test if b is contained in this ideal. Note: 595 * this is eventually modified to become a Groebner Base. 596 * @param b solvable polynomial 597 * @return true, if b is contained in this, else false 598 */ 599 public boolean contains(GenSolvablePolynomial<C> b) { 600 if (b == null || b.isZERO()) { 601 return true; 602 } 603 if (this.isONE()) { 604 return true; 605 } 606 if (this.isZERO()) { 607 return false; 608 } 609 if (!isGB) { 610 doGB(); 611 } 612 GenSolvablePolynomial<C> z = red.leftNormalform(getList(), b); 613 if (z == null || z.isZERO()) { 614 return true; 615 } 616 return false; 617 } 618 619 620 /** 621 * Solvable ideal containment. Test if each b in B is contained in this 622 * ideal. Note: this is eventually modified to become a Groebner Base. 623 * @param B list of solvable polynomials 624 * @return true, if each b in B is contained in this, else false 625 */ 626 public boolean contains(List<GenSolvablePolynomial<C>> B) { 627 if (B == null || B.size() == 0) { 628 return true; 629 } 630 if (this.isONE()) { 631 return true; 632 } 633 if (!isGB) { 634 doGB(); 635 } 636 List<GenSolvablePolynomial<C>> si = getList(); 637 for (GenSolvablePolynomial<C> b : B) { 638 if (b == null) { 639 continue; 640 } 641 GenSolvablePolynomial<C> z = red.leftNormalform(si, b); 642 if (!z.isZERO()) { 643 logger.info("contains nf(b) != 0: " + z + " of " + b); 644 // + ", si = " + si + ", ring = " + z.ring.toScript()); 645 return false; 646 } 647 } 648 return true; 649 } 650 651 652 /** 653 * Solvable ideal summation. Generators for the sum of ideals. Note: if both 654 * ideals are Groebner bases, a Groebner base is returned. 655 * @param B solvable ideal 656 * @return ideal(this+B) 657 */ 658 public SolvableIdeal<C> sum(SolvableIdeal<C> B) { 659 if (B == null || B.isZERO()) { 660 return this; 661 } 662 if (this.isZERO()) { 663 return B; 664 } 665 int s = getList().size() + B.getList().size(); 666 List<GenSolvablePolynomial<C>> c; 667 c = new ArrayList<GenSolvablePolynomial<C>>(s); 668 c.addAll(getList()); 669 c.addAll(B.getList()); 670 SolvableIdeal<C> I = new SolvableIdeal<C>(getRing(), c, false, sided); 671 if (isGB && B.isGB) { 672 I.doGB(); // TODO twosided, right 673 } 674 return I; 675 } 676 677 678 /** 679 * Solvable summation. Generators for the sum of ideal and a polynomial. 680 * Note: if this ideal is a Groebner base, a Groebner base is returned. 681 * @param b solvable polynomial 682 * @return ideal(this+{b}) 683 */ 684 public SolvableIdeal<C> sum(GenSolvablePolynomial<C> b) { 685 if (b == null || b.isZERO()) { 686 return this; 687 } 688 int s = getList().size() + 1; 689 List<GenSolvablePolynomial<C>> c; 690 c = new ArrayList<GenSolvablePolynomial<C>>(s); 691 c.addAll(getList()); 692 c.add(b); 693 SolvableIdeal<C> I = new SolvableIdeal<C>(getRing(), c, false, sided); 694 if (isGB) { 695 I.doGB(); 696 } 697 return I; 698 } 699 700 701 /** 702 * Solvable summation. Generators for the sum of this ideal and a list of 703 * polynomials. Note: if this ideal is a Groebner base, a Groebner base is 704 * returned. 705 * @param L list of solvable polynomials 706 * @return ideal(this+L) 707 */ 708 public SolvableIdeal<C> sum(List<GenSolvablePolynomial<C>> L) { 709 if (L == null || L.isEmpty()) { 710 return this; 711 } 712 int s = getList().size() + L.size(); 713 List<GenSolvablePolynomial<C>> c = new ArrayList<GenSolvablePolynomial<C>>(s); 714 c.addAll(getList()); 715 c.addAll(L); 716 SolvableIdeal<C> I = new SolvableIdeal<C>(getRing(), c, false, sided); 717 if (isGB) { 718 I.doGB(); 719 } 720 return I; 721 } 722 723 724 /** 725 * Product. Generators for the product of ideals. Note: if both ideals are 726 * Groebner bases, a Groebner base is returned. 727 * @param B solvable ideal 728 * @return ideal(this*B) 729 */ 730 public SolvableIdeal<C> product(SolvableIdeal<C> B) { 731 if (B == null || B.isZERO()) { 732 return B; 733 } 734 if (this.isZERO()) { 735 return this; 736 } 737 int s = getList().size() * B.getList().size(); 738 List<GenSolvablePolynomial<C>> c; 739 c = new ArrayList<GenSolvablePolynomial<C>>(s); 740 for (GenSolvablePolynomial<C> p : getList()) { 741 for (GenSolvablePolynomial<C> q : B.getList()) { 742 q = p.multiply(q); 743 c.add(q); 744 } 745 } 746 SolvableIdeal<C> I = new SolvableIdeal<C>(getRing(), c, false, sided); 747 if (isGB && B.isGB) { 748 I.doGB(); 749 } 750 return I; 751 } 752 753 754 /** 755 * Left product. Generators for the product this by a polynomial. 756 * @param b solvable polynomial 757 * @return ideal(this*b) 758 */ 759 public SolvableIdeal<C> product(GenSolvablePolynomial<C> b) { 760 if (b == null || b.isZERO()) { 761 return getZERO(); 762 } 763 if (this.isZERO()) { 764 return this; 765 } 766 List<GenSolvablePolynomial<C>> c; 767 c = new ArrayList<GenSolvablePolynomial<C>>(getList().size()); 768 for (GenSolvablePolynomial<C> p : getList()) { 769 GenSolvablePolynomial<C> q = p.multiply(b); 770 c.add(q); 771 } 772 SolvableIdeal<C> I = new SolvableIdeal<C>(getRing(), c, false, sided); 773 if (isGB) { 774 I.doGB(); 775 } 776 return I; 777 } 778 779 780 /** 781 * Intersection. Generators for the intersection of ideals. Using an 782 * iterative algorithm. 783 * @param Bl list of solvable ideals 784 * @return ideal(cap_i B_i), a Groebner base 785 */ 786 public SolvableIdeal<C> intersect(List<SolvableIdeal<C>> Bl) { 787 if (Bl == null || Bl.size() == 0) { 788 return getZERO(); 789 } 790 SolvableIdeal<C> I = null; 791 for (SolvableIdeal<C> B : Bl) { 792 if (I == null) { 793 I = B; 794 continue; 795 } 796 if (I.isONE()) { 797 return I; 798 } 799 I = I.intersect(B); 800 } 801 return I; 802 } 803 804 805 /** 806 * Intersection. Generators for the intersection of ideals. 807 * @param B solvable ideal 808 * @return ideal(this \cap B), a Groebner base 809 */ 810 public SolvableIdeal<C> intersect(SolvableIdeal<C> B) { 811 if (B == null || B.isZERO()) { // (0) 812 return B; 813 } 814 if (this.isZERO()) { 815 return this; 816 } 817 List<GenSolvablePolynomial<C>> c = PolyGBUtil.<C> intersect(getRing(), getList(), B.getList()); 818 SolvableIdeal<C> I = new SolvableIdeal<C>(getRing(), c, true, sided); 819 return I; 820 } 821 822 823 /** 824 * Intersection. Generators for the intersection of a ideal with a 825 * polynomial ring. The polynomial ring of this ideal must be a contraction 826 * of R and the TermOrder must be an elimination order. 827 * @param R solvable polynomial ring 828 * @return ideal(this \cap R) 829 */ 830 public SolvableIdeal<C> intersect(GenSolvablePolynomialRing<C> R) { 831 if (R == null) { 832 throw new IllegalArgumentException("R may not be null"); 833 } 834 List<GenSolvablePolynomial<C>> H = PolyUtil.<C> intersect(R, getList()); 835 return new SolvableIdeal<C>(R, H, isGB, sided); 836 } 837 838 839 /** 840 * Eliminate. Generators for the intersection of this ideal with a solvable 841 * polynomial ring. The solvable polynomial ring of this ideal must be a 842 * contraction of R and the TermOrder must be an elimination order. 843 * @param R solvable polynomial ring 844 * @return ideal(this \cap R) 845 */ 846 public SolvableIdeal<C> eliminate(GenSolvablePolynomialRing<C> R) { 847 if (R == null) { 848 throw new IllegalArgumentException("R may not be null"); 849 } 850 if (getRing().equals(R)) { 851 return this; 852 } 853 return intersect(R); 854 } 855 856 857 /** 858 * Quotient. Generators for the solvable ideal quotient. 859 * @param h solvable polynomial 860 * @return ideal(this : h), a Groebner base 861 */ 862 public SolvableIdeal<C> quotient(GenSolvablePolynomial<C> h) { 863 if (h == null) { // == (0) 864 return this; 865 } 866 if (h.isZERO()) { 867 return this; 868 } 869 if (this.isZERO()) { 870 return this; 871 } 872 List<GenSolvablePolynomial<C>> H; 873 H = new ArrayList<GenSolvablePolynomial<C>>(1); 874 H.add(h); 875 SolvableIdeal<C> Hi = new SolvableIdeal<C>(getRing(), H, true, sided); 876 877 SolvableIdeal<C> I = this.intersect(Hi); 878 879 List<GenSolvablePolynomial<C>> Q; 880 Q = new ArrayList<GenSolvablePolynomial<C>>(I.getList().size()); 881 GenSolvablePolynomial<C> p; 882 for (GenSolvablePolynomial<C> q : I.getList()) { 883 p = (GenSolvablePolynomial<C>) q.divide(h); // remainder == 0 884 if (!p.isZERO()) { 885 p = p.monic(); 886 Q.add(p); 887 } 888 if (debug) { 889 GenSolvablePolynomial<C> r = (GenSolvablePolynomial<C>) q.remainder(h); 890 if (!r.isZERO()) { 891 System.out.println("error remainder !=0: " + r + ", q = " + q + ", h = " + h); 892 throw new RuntimeException("remainder !=0"); 893 } 894 } 895 } 896 return new SolvableIdeal<C>(getRing(), Q, true /*false?*/, sided); 897 } 898 899 900 /** 901 * Quotient. Generators for the solvable ideal quotient. 902 * @param H solvable ideal 903 * @return ideal(this : H), a Groebner base 904 */ 905 public SolvableIdeal<C> quotient(SolvableIdeal<C> H) { 906 if (H == null || H.isZERO()) { // == (0) 907 return this; 908 } 909 if (this.isZERO()) { 910 return this; 911 } 912 SolvableIdeal<C> Q = null; 913 for (GenSolvablePolynomial<C> h : H.getList()) { 914 SolvableIdeal<C> Hi = this.quotient(h); 915 if (Q == null) { 916 Q = Hi; 917 } else { 918 Q = Q.intersect(Hi); 919 } 920 } 921 return Q; 922 } 923 924 925 /** 926 * Infinite quotient. Generators for the infinite solvable ideal quotient. 927 * @param h solvable polynomial 928 * @return ideal(this : h<sup>s</sup>), a Groebner base 929 */ 930 public SolvableIdeal<C> infiniteQuotientRab(GenSolvablePolynomial<C> h) { 931 if (h == null || h.isZERO()) { // == (0) 932 return getONE(); 933 } 934 if (h.isONE()) { 935 return this; 936 } 937 if (this.isZERO()) { 938 return this; 939 } 940 if (!getRing().isCommutative()) { 941 throw new UnsupportedOperationException("Rabinowich trick only for commutative polynomial rings"); 942 } 943 SolvableIdeal<C> I = this.GB(); // should be already 944 List<GenSolvablePolynomial<C>> a = I.getList(); 945 List<GenSolvablePolynomial<C>> c; 946 c = new ArrayList<GenSolvablePolynomial<C>>(a.size() + 1); 947 948 GenSolvablePolynomialRing<C> tfac = getRing().extend(1); 949 // term order is also adjusted 950 for (GenSolvablePolynomial<C> p : a) { 951 p = (GenSolvablePolynomial<C>) p.extend(tfac, 0, 0L); // p 952 c.add(p); 953 } 954 GenSolvablePolynomial<C> q = (GenSolvablePolynomial<C>) h.extend(tfac, 0, 1L); 955 GenSolvablePolynomial<C> r = tfac.getONE(); // h.extend( tfac, 0, 0L ); 956 GenSolvablePolynomial<C> hs = (GenSolvablePolynomial<C>) q.subtract(r); // 1 - t*h // (1-t)*h 957 c.add(hs); 958 logger.warn("infiniteQuotientRab computing GB "); 959 List<GenSolvablePolynomial<C>> g = bb.leftGB(c); 960 if (debug) { 961 logger.info("infiniteQuotientRab = " + tfac + ", c = " + c); 962 logger.info("infiniteQuotientRab GB = " + g); 963 } 964 SolvableIdeal<C> E = new SolvableIdeal<C>(tfac, g, true, sided); 965 SolvableIdeal<C> Is = E.intersect(getRing()); 966 return Is; 967 } 968 969 970 /** 971 * Infinite quotient exponent. 972 * @param h solvable polynomial 973 * @param Q quotient this : h^\infinity 974 * @return s with Q = this : h<sup>s</sup> 975 */ 976 public int infiniteQuotientExponent(GenSolvablePolynomial<C> h, SolvableIdeal<C> Q) { 977 int s = 0; 978 if (h == null) { // == 0 979 return s; 980 } 981 if (h.isZERO() || h.isONE()) { 982 return s; 983 } 984 if (this.isZERO() || this.isONE()) { 985 return s; 986 } 987 //see below: if (this.contains(Q)) { 988 // return s; 989 //} 990 GenSolvablePolynomial<C> p = getRing().getONE(); 991 for (GenSolvablePolynomial<C> q : Q.getList()) { 992 if (this.contains(q)) { 993 continue; 994 } 995 //System.out.println("q = " + q + ", p = " + p + ", s = " + s); 996 GenSolvablePolynomial<C> qp = q.multiply(p); 997 while (!this.contains(qp)) { 998 p = p.multiply(h); 999 s++; 1000 qp = q.multiply(p); 1001 } 1002 } 1003 return s; 1004 } 1005 1006 1007 /** 1008 * Infinite quotient. Generators for the infinite solvable ideal quotient. 1009 * @param h solvable polynomial 1010 * @return ideal(this : h<sup>s</sup>), a Groebner base 1011 */ 1012 public SolvableIdeal<C> infiniteQuotient(GenSolvablePolynomial<C> h) { 1013 if (h == null) { // == (0) 1014 return this; 1015 } 1016 if (h.isZERO()) { 1017 return this; 1018 } 1019 if (this.isZERO()) { 1020 return this; 1021 } 1022 int s = 0; 1023 SolvableIdeal<C> I = this.GB(); // should be already 1024 GenSolvablePolynomial<C> hs = h; 1025 SolvableIdeal<C> Is = null; 1026 logger.info("infiniteQuotient hs = " + hs); 1027 long dm = -1; 1028 boolean eq = false; 1029 while (!eq) { 1030 Is = I.quotient(hs); 1031 Is = Is.GB(); // should be already 1032 //logger.info("ideal Is = " + Is); 1033 logger.info("infiniteQuotient s = " + s); 1034 if (Is.isZERO()) { 1035 logger.warn("infiniteQuotient does not exist"); 1036 return I; 1037 } 1038 eq = Is.contains(I); // I.contains(Is) always 1039 if (!eq) { 1040 long ds = PolyUtil.<C> totalDegree(Is.list.getList()); 1041 if (dm < 0) { 1042 dm = ds; 1043 } 1044 //System.out.println("deg(Is) = " + ds); 1045 if (ds > dm) { 1046 logger.warn("no convergence in infiniteQuotient (dm,ds): " + dm + " < " + ds); 1047 return I; 1048 //throw new RuntimeException("no convergence in infiniteQuotient"); 1049 } 1050 I = Is; 1051 s++; 1052 // hs = hs.multiply( h ); 1053 } 1054 } 1055 return Is; 1056 } 1057 1058 1059 /** 1060 * Radical membership test. 1061 * @param h solvable polynomial 1062 * @return true if h is contained in the radical of ideal(this), else false. 1063 */ 1064 public boolean isRadicalMember(GenSolvablePolynomial<C> h) { 1065 if (h == null) { // == (0) 1066 return true; 1067 } 1068 if (h.isZERO()) { 1069 return true; 1070 } 1071 if (this.isZERO()) { 1072 return true; 1073 } 1074 SolvableIdeal<C> x = infiniteQuotientRab(h); // may fail 1075 if (debug) { 1076 logger.debug("infiniteQuotientRab = " + x); 1077 } 1078 return x.isONE(); 1079 } 1080 1081 1082 /** 1083 * Infinite Quotient. Generators for the solvable ideal infinite quotient. 1084 * @param H solvable ideal 1085 * @return ideal(this : H<sup>s</sup>), a Groebner base 1086 */ 1087 public SolvableIdeal<C> infiniteQuotient(SolvableIdeal<C> H) { 1088 if (H == null) { // == (0) 1089 return this; 1090 } 1091 if (H.isZERO()) { 1092 return this; 1093 } 1094 if (this.isZERO()) { 1095 return this; 1096 } 1097 SolvableIdeal<C> Q = null; 1098 for (GenSolvablePolynomial<C> h : H.getList()) { 1099 SolvableIdeal<C> Hi = this.infiniteQuotient(h); 1100 if (Q == null) { 1101 Q = Hi; 1102 } else { 1103 Q = Q.intersect(Hi); 1104 } 1105 } 1106 return Q; 1107 } 1108 1109 1110 /** 1111 * Infinite Quotient. Generators for the solvable ideal infinite quotient. 1112 * @param H solvable ideal 1113 * @return ideal(this : H<sup>s</sup>), a Groebner base 1114 */ 1115 public SolvableIdeal<C> infiniteQuotientRab(SolvableIdeal<C> H) { 1116 if (H == null) { // == (0) 1117 return this; 1118 } 1119 if (H.isZERO()) { 1120 return this; 1121 } 1122 if (this.isZERO()) { 1123 return this; 1124 } 1125 SolvableIdeal<C> Q = null; 1126 for (GenSolvablePolynomial<C> h : H.getList()) { 1127 SolvableIdeal<C> Hi = this.infiniteQuotientRab(h); // may fail 1128 if (Q == null) { 1129 Q = Hi; 1130 } else { 1131 Q = Q.intersect(Hi); 1132 } 1133 } 1134 return Q; 1135 } 1136 1137 1138 /** 1139 * Power. Generators for the power of this solvable ideal. Note: if this 1140 * ideal is a Groebner base, a Groebner base is returned. 1141 * @param d integer 1142 * @return ideal(this^d) 1143 */ 1144 public SolvableIdeal<C> power(int d) { 1145 if (d <= 0) { 1146 return getONE(); 1147 } 1148 if (this.isZERO() || this.isONE()) { 1149 return this; 1150 } 1151 SolvableIdeal<C> c = this; 1152 for (int i = 1; i < d; i++) { 1153 c = c.product(this); 1154 } 1155 return c; 1156 } 1157 1158 1159 /** 1160 * Normalform for element. 1161 * @param h solvable polynomial 1162 * @return left normalform of h with respect to this 1163 */ 1164 public GenSolvablePolynomial<C> normalform(GenSolvablePolynomial<C> h) { 1165 if (h == null) { 1166 return h; 1167 } 1168 if (h.isZERO()) { 1169 return h; 1170 } 1171 if (this.isZERO()) { 1172 return h; 1173 } 1174 GenSolvablePolynomial<C> r; 1175 r = red.leftNormalform(getList(), h); 1176 return r; 1177 } 1178 1179 1180 /** 1181 * Normalform for list of solvable elements. 1182 * @param L solvable polynomial list 1183 * @return list of left normalforms of the elements of L with respect to 1184 * this 1185 */ 1186 public List<GenSolvablePolynomial<C>> normalform(List<GenSolvablePolynomial<C>> L) { 1187 if (L == null) { 1188 return L; 1189 } 1190 if (L.size() == 0) { 1191 return L; 1192 } 1193 if (this.isZERO()) { 1194 return L; 1195 } 1196 List<GenSolvablePolynomial<C>> M = new ArrayList<GenSolvablePolynomial<C>>(L.size()); 1197 for (GenSolvablePolynomial<C> h : L) { 1198 GenSolvablePolynomial<C> r = normalform(h); 1199 if (r != null && !r.isZERO()) { 1200 M.add(r); 1201 } 1202 } 1203 return M; 1204 } 1205 1206 1207 /** 1208 * Annihilator for element modulo this ideal. 1209 * @param h solvable polynomial 1210 * @return annihilator of h with respect to this 1211 */ 1212 public SolvableIdeal<C> annihilator(GenSolvablePolynomial<C> h) { 1213 if (h == null || h.isZERO()) { 1214 return getZERO(); 1215 } 1216 if (this.isZERO()) { 1217 return this; 1218 } 1219 doGB(); 1220 List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(1 + getList().size()); 1221 F.add(h); 1222 F.addAll(getList()); 1223 //System.out.println("F = " + F); 1224 SolvableSyzygyAbstract<C> syz = new SolvableSyzygySeq<C>(getRing().coFac); 1225 List<List<GenSolvablePolynomial<C>>> S = syz.leftZeroRelationsArbitrary(F); 1226 //System.out.println("S = " + S); 1227 List<GenSolvablePolynomial<C>> gen = new ArrayList<GenSolvablePolynomial<C>>(S.size()); 1228 for (List<GenSolvablePolynomial<C>> rel : S) { 1229 if (rel == null || rel.isEmpty()) { 1230 continue; 1231 } 1232 GenSolvablePolynomial<C> p = rel.get(0); 1233 if (p == null || p.isZERO()) { 1234 continue; 1235 } 1236 gen.add(p); 1237 } 1238 SolvableIdeal<C> ann = new SolvableIdeal<C>(getRing(), gen, false, sided); 1239 //System.out.println("ann = " + ann); 1240 return ann; 1241 } 1242 1243 1244 /** 1245 * Test for annihilator of element modulo this ideal. 1246 * @param h solvable polynomial 1247 * @param A solvable ideal 1248 * @return true, if A is the annihilator of h with respect to this 1249 */ 1250 public boolean isAnnihilator(GenSolvablePolynomial<C> h, SolvableIdeal<C> A) { 1251 SolvableIdeal<C> B = A.product(h); 1252 return contains(B); 1253 } 1254 1255 1256 /** 1257 * Annihilator for ideal modulo this ideal. 1258 * @param H solvable ideal 1259 * @return annihilator of H with respect to this 1260 */ 1261 public SolvableIdeal<C> annihilator(SolvableIdeal<C> H) { 1262 if (H == null || H.isZERO()) { 1263 return getZERO(); 1264 } 1265 if (this.isZERO()) { 1266 return this; 1267 } 1268 SolvableIdeal<C> ann = null; 1269 for (GenSolvablePolynomial<C> h : H.getList()) { 1270 SolvableIdeal<C> Hi = this.annihilator(h); 1271 if (ann == null) { 1272 ann = Hi; 1273 } else { 1274 ann = ann.intersect(Hi); 1275 } 1276 } 1277 return ann; 1278 } 1279 1280 1281 /** 1282 * Test for annihilator of ideal modulo this ideal. 1283 * @param H solvable ideal 1284 * @param A solvable ideal 1285 * @return true, if A is the annihilator of H with respect to this 1286 */ 1287 public boolean isAnnihilator(SolvableIdeal<C> H, SolvableIdeal<C> A) { 1288 SolvableIdeal<C> B = A.product(H); 1289 return contains(B); 1290 } 1291 1292 1293 /** 1294 * Inverse for element modulo this ideal. 1295 * @param h solvable polynomial 1296 * @return inverse of h with respect to this, if defined 1297 */ 1298 public GenSolvablePolynomial<C> inverse(GenSolvablePolynomial<C> h) { 1299 if (h == null || h.isZERO()) { 1300 throw new NotInvertibleException("zero not invertible"); 1301 } 1302 if (this.isZERO()) { 1303 throw new NotInvertibleException("zero ideal"); 1304 } 1305 if (h.isUnit()) { 1306 return (GenSolvablePolynomial<C>) h.inverse(); 1307 } 1308 doGB(); 1309 List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(1 + list.list.size()); 1310 F.add(h); 1311 F.addAll(getList()); 1312 //System.out.println("F = " + F); 1313 SolvableExtendedGB<C> x = bb.extLeftGB(F); 1314 List<GenSolvablePolynomial<C>> G = x.G; 1315 //System.out.println("G = " + G); 1316 GenSolvablePolynomial<C> one = null; 1317 int i = -1; 1318 for (GenSolvablePolynomial<C> p : G) { 1319 i++; 1320 if (p == null) { 1321 continue; 1322 } 1323 if (p.isUnit()) { 1324 one = p; 1325 break; 1326 } 1327 } 1328 if (one == null) { 1329 throw new NotInvertibleException("one == null: h = " + h); 1330 } 1331 List<GenSolvablePolynomial<C>> row = x.G2F.get(i); // != -1 1332 //System.out.println("row = " + row); 1333 GenSolvablePolynomial<C> g = row.get(0); 1334 if (g == null || g.isZERO()) { 1335 throw new NotInvertibleException("g == 0: h = " + h); 1336 } 1337 GenSolvablePolynomial<C> gp = red.leftNormalform(getList(), g); 1338 if (gp.isZERO()) { // can happen with solvable rings 1339 throw new NotInvertibleException("solv|gp == 0: h = " + h + ", g = " + g); 1340 } 1341 // adjust leading coefficient of g to get g*h == 1 1342 GenSolvablePolynomial<C> f = g.multiply(h); 1343 //System.out.println("f = " + f); 1344 GenSolvablePolynomial<C> k = red.leftNormalform(getList(), f); 1345 //System.out.println("k = " + k); 1346 if (!k.isONE()) { 1347 C lbc = k.leadingBaseCoefficient(); 1348 lbc = lbc.inverse(); 1349 g = g.multiply(lbc); 1350 } 1351 if (debug) { 1352 //logger.info("inv G = " + G); 1353 //logger.info("inv G2F = " + x.G2F); 1354 //logger.info("inv row "+i+" = " + row); 1355 //logger.info("inv h = " + h); 1356 //logger.info("inv g = " + g); 1357 //logger.info("inv f = " + f); 1358 f = g.multiply(h); 1359 k = red.leftNormalform(getList(), f); 1360 logger.debug("inv k = " + k); 1361 if (!k.isUnit()) { 1362 throw new NotInvertibleException(" k = " + k); 1363 } 1364 } 1365 return g; 1366 } 1367 1368 1369 /** 1370 * Test if element is a unit modulo this ideal. 1371 * @param h solvable polynomial 1372 * @return true if h is a unit with respect to this, else false 1373 */ 1374 public boolean isUnit(GenSolvablePolynomial<C> h) { 1375 if (h == null || h.isZERO()) { 1376 return false; 1377 } 1378 if (this.isZERO()) { 1379 return false; 1380 } 1381 List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(1 + list.list.size()); 1382 F.add(h); 1383 F.addAll(getList()); 1384 List<GenSolvablePolynomial<C>> G = bb.leftGB(F); 1385 for (GenSolvablePolynomial<C> p : G) { 1386 if (p == null) { 1387 continue; 1388 } 1389 if (p.isUnit()) { 1390 return true; 1391 } 1392 } 1393 return false; 1394 } 1395 1396 1397 /** 1398 * Ideal common zero test. 1399 * @return -1, 0 or 1 if dimension(this) &eq; -1, 0 or ≥ 1. 1400 */ 1401 public int commonZeroTest() { 1402 if (this.isZERO()) { 1403 return 1; 1404 } 1405 if (!isGB) { 1406 doGB(); 1407 } 1408 if (this.isONE()) { 1409 return -1; 1410 } 1411 return bb.commonZeroTest(getList()); 1412 } 1413 1414 1415 /** 1416 * Test if this ideal is maximal. 1417 * @return true, if this is maximal and not one, else false. 1418 */ 1419 public boolean isMaximal() { 1420 if (commonZeroTest() != 0) { 1421 return false; 1422 } 1423 for (Long d : univariateDegrees()) { 1424 if (d > 1L) { 1425 // todo: test if irreducible 1426 return false; 1427 } 1428 } 1429 return true; 1430 } 1431 1432 1433 /** 1434 * Univariate head term degrees. 1435 * @return a list of the degrees of univariate head terms. 1436 */ 1437 public List<Long> univariateDegrees() { 1438 List<Long> ud = new ArrayList<Long>(); 1439 if (this.isZERO()) { 1440 return ud; 1441 } 1442 if (!isGB) { 1443 doGB(); 1444 } 1445 if (this.isONE()) { 1446 return ud; 1447 } 1448 return bb.univariateDegrees(getList()); 1449 } 1450 1451 1452 /** 1453 * Ideal dimension. 1454 * @return a dimension container (dim,maxIndep,list(maxIndep),vars). 1455 */ 1456 public Dimension dimension() { 1457 Ideal<C> ci = new Ideal<C>(list); 1458 return ci.dimension(); 1459 } 1460 1461 1462 /** 1463 * Construct univariate polynomials of minimal degree in all variables in 1464 * zero dimensional ideal(G). 1465 * @return list of univariate solvable polynomial of minimal degree in each 1466 * variable in ideal(G) 1467 */ 1468 public List<GenSolvablePolynomial<C>> constructUnivariate() { 1469 List<GenSolvablePolynomial<C>> univs = new ArrayList<GenSolvablePolynomial<C>>(); 1470 for (int i = getRing().nvar - 1; i >= 0; i--) { 1471 GenSolvablePolynomial<C> u = constructUnivariate(i); 1472 univs.add(u); 1473 } 1474 return univs; 1475 } 1476 1477 1478 /** 1479 * Construct univariate polynomial of minimal degree in variable i in zero 1480 * dimensional ideal(G). 1481 * @param i variable index. 1482 * @return univariate solvable polynomial of minimal degree in variable i in 1483 * ideal(G) 1484 */ 1485 public GenSolvablePolynomial<C> constructUnivariate(int i) { 1486 doGB(); 1487 return bb.constructUnivariate(i, getList()); 1488 } 1489 1490}