001/* 002 * $Id$ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.Serializable; 009import java.util.ArrayList; 010import java.util.Arrays; 011import java.util.HashMap; 012import java.util.Iterator; 013import java.util.LinkedList; 014import java.util.List; 015import java.util.ListIterator; 016import java.util.Map; 017 018import org.apache.logging.log4j.LogManager; 019import org.apache.logging.log4j.Logger; 020 021import edu.jas.kern.PrettyPrint; 022import edu.jas.structure.RingElem; 023 024 025/** 026 * RelationTable for solvable polynomials. This class maintains the 027 * non-commutative multiplication relations of solvable polynomial rings. The 028 * table entries are initialized with relations of the form x<sub>j</sub> * 029 * x<sub>i</sub> = p<sub>ij</sub>. During multiplication the relations are 030 * updated by relations of the form x<sub>j</sub><sup>k</sup> * 031 * x<sub>i</sub><sup>l</sup> = p<sub>ijkl</sub>. If no relation for 032 * x<sub>j</sub> * x<sub>i</sub> is found in the table, this multiplication is 033 * assumed to be commutative x<sub>i</sub> x<sub>j</sub>. Can also be used for 034 * relations between coefficients and main variables. 035 * @author Heinz Kredel 036 */ 037public class RelationTable<C extends RingElem<C>> implements Serializable { 038 039 040 /** 041 * The data structure for the relations. 042 */ 043 public final Map<List<Integer>, List> table; 044 045 046 /** 047 * The factory for the solvable polynomial ring. 048 */ 049 public final GenSolvablePolynomialRing<C> ring; 050 051 052 /** 053 * Usage indicator: table or coeffTable. 054 */ 055 public final boolean coeffTable; 056 057 058 private static final Logger logger = LogManager.getLogger(RelationTable.class); 059 060 061 private static final boolean debug = logger.isDebugEnabled(); 062 063 064 /** 065 * Constructor for RelationTable requires ring factory. Note: This 066 * constructor is called within the constructor of the ring factory, so 067 * methods of this class can only be used after the other constructor has 068 * terminated. 069 * @param r solvable polynomial ring factory. 070 */ 071 public RelationTable(GenSolvablePolynomialRing<C> r) { 072 this(r, false); 073 } 074 075 076 /** 077 * Constructor for RelationTable requires ring factory. Note: This 078 * constructor is called within the constructor of the ring factory, so 079 * methods of this class can only be used after the other constructor has 080 * terminated. 081 * @param r solvable polynomial ring factory. 082 * @param coeffTable indicator for coeffTable. 083 */ 084 public RelationTable(GenSolvablePolynomialRing<C> r, boolean coeffTable) { 085 table = new HashMap<List<Integer>, List>(); 086 ring = r; 087 if (ring == null) { 088 throw new IllegalArgumentException("RelationTable no ring"); 089 } 090 this.coeffTable = coeffTable; 091 } 092 093 094 /** 095 * RelationTable equals. Tests same keySets and base relations. 096 * @see java.lang.Object#equals(java.lang.Object) 097 */ 098 @Override 099 @SuppressWarnings("unchecked") 100 public boolean equals(Object p) { 101 if (p == null) { 102 return false; 103 } 104 if (!(p instanceof RelationTable)) { 105 logger.info("no RelationTable"); 106 return false; 107 } 108 RelationTable<C> tab = (RelationTable<C>) p; 109 // not possible because of infinite recursion: 110 //if (!ring.equals(tab.ring)) { 111 // logger.info("not same Ring {} != {}", ring, tab.ring); 112 // return false; 113 //} 114 if (!table.keySet().equals(tab.table.keySet())) { 115 logger.info("keySet != : a = {} != b = {}", table.keySet(), tab.table.keySet()); 116 return false; 117 } 118 for (Map.Entry<List<Integer>, List> me : table.entrySet()) { 119 List<Integer> k = me.getKey(); 120 List a = me.getValue(); 121 List b = tab.table.get(k); 122 // check contents, but only base relations 123 Map<ExpVectorPair, GenPolynomial<C>> t1ex = fromListDeg2(a); 124 Map<ExpVectorPair, GenPolynomial<C>> t2ex = fromListDeg2(b); 125 if (!equalMaps(t1ex, t2ex)) { 126 //System.out.println("a != b, a = " + t1ex + ", b = " + t2ex); 127 return false; 128 } 129 } 130 return true; 131 } 132 133 134 /** 135 * Convert mixed list to map for base relations. 136 * @param a mixed list 137 * @returns a map constructed from the list with deg(key) == 2. 138 */ 139 @SuppressWarnings("unchecked") 140 Map<ExpVectorPair, GenPolynomial<C>> fromListDeg2(List a) { 141 Map<ExpVectorPair, GenPolynomial<C>> tex = new HashMap<ExpVectorPair, GenPolynomial<C>>(); 142 Iterator ait = a.iterator(); 143 while (ait.hasNext()) { 144 ExpVectorPair ae = (ExpVectorPair) ait.next(); 145 if (!ait.hasNext()) { 146 break; 147 } 148 GenPolynomial<C> p = (GenPolynomial<C>) ait.next(); 149 if (ae.totalDeg() == 2) { // only base relations 150 //System.out.println("ae => p: " + ae + " => " + p); 151 tex.put(ae, p); 152 } 153 } 154 return tex; 155 } 156 157 158 /** 159 * Hash code for base relations. 160 * @param a mixed list 161 * @returns hashCode(a) 162 */ 163 @SuppressWarnings("unchecked") 164 int fromListDeg2HashCode(List a) { 165 int h = 0; 166 Iterator ait = a.iterator(); 167 while (ait.hasNext()) { 168 ExpVectorPair ae = (ExpVectorPair) ait.next(); 169 h = 31 * h + ae.hashCode(); 170 if (!ait.hasNext()) { 171 break; 172 } 173 GenPolynomial<C> p = (GenPolynomial<C>) ait.next(); 174 if (ae.totalDeg() == 2) { // only base relations 175 //System.out.println("ae => p: " + ae + " => " + p); 176 h = 31 * h + p.val.hashCode(); // avoid hash of ring 177 } 178 } 179 return h; 180 } 181 182 183 /** 184 * Equals for special maps. 185 * @param m1 first map 186 * @param m2 second map 187 * @returns true if both maps are equal 188 */ 189 @SuppressWarnings("unchecked") 190 boolean equalMaps(Map<ExpVectorPair, GenPolynomial<C>> m1, Map<ExpVectorPair, GenPolynomial<C>> m2) { 191 if (!m1.keySet().equals(m2.keySet())) { 192 return false; 193 } 194 for (Map.Entry<ExpVectorPair, GenPolynomial<C>> me : m1.entrySet()) { 195 GenPolynomial<C> p1 = me.getValue(); 196 ExpVectorPair ep = me.getKey(); 197 GenPolynomial<C> p2 = m2.get(ep); 198 if (p1.compareTo(p2) != 0) { // not working: !p1.equals(p2) 199 logger.info("ep = {}, p1 = {}, p2 = {}", ep, p1, p2); 200 //logger.info("p1.compareTo(p2) = {}", p1.compareTo(p2)); 201 //logger.info("p1.equals(p2) = {}", p1.equals(p2)); 202 return false; 203 } 204 } 205 return true; 206 } 207 208 209 /** 210 * Hash code for this relation table. 211 * @see java.lang.Object#hashCode() 212 */ 213 @Override 214 public int hashCode() { 215 //int h = ring.hashCode(); // infinite recursion 216 int h = 0; //table.hashCode(); 217 h = table.keySet().hashCode(); 218 for (Map.Entry<List<Integer>, List> me : table.entrySet()) { 219 //List<Integer> k = me.getKey(); 220 List a = me.getValue(); 221 int t1 = fromListDeg2HashCode(a); 222 h = 31 * h + t1; 223 } 224 return h; 225 } 226 227 228 /** 229 * Test if the table is empty. 230 * @return true if the table is empty, else false. 231 */ 232 public boolean isEmpty() { 233 return table.isEmpty(); 234 } 235 236 237 /** 238 * Get the String representation. 239 * @see java.lang.Object#toString() 240 */ 241 @Override 242 public String toString() { 243 List v; 244 StringBuffer s = new StringBuffer("RelationTable["); 245 boolean first = true; 246 for (Map.Entry<List<Integer>, List> me : table.entrySet()) { 247 List<Integer> k = me.getKey(); 248 if (first) { 249 first = false; 250 } else { 251 s.append(", "); 252 } 253 s.append(k.toString()); 254 v = me.getValue(); 255 s.append("="); 256 s.append(v.toString()); 257 } 258 s.append("]"); 259 return s.toString(); 260 } 261 262 263 /** 264 * Get the String representation. 265 * @param vars names for the variables. 266 * @see java.lang.Object#toString() 267 */ 268 @SuppressWarnings({ "unchecked", "cast" }) 269 public String toString(String[] vars) { 270 if (vars == null) { 271 return toString(); 272 } 273 StringBuffer s = new StringBuffer(""); 274 String[] cvars = null; 275 if (coeffTable) { 276 if (ring.coFac instanceof GenPolynomialRing) { 277 cvars = ((GenPolynomialRing<C>) (Object) ring.coFac).getVars(); 278 } else if (ring.coFac instanceof GenWordPolynomialRing) { 279 cvars = ((GenWordPolynomialRing<C>) (Object) ring.coFac).getVars(); 280 } 281 s.append("Coefficient "); 282 } 283 s.append("RelationTable\n("); 284 List v; 285 if (PrettyPrint.isTrue()) { 286 boolean first = true; 287 for (Map.Entry<List<Integer>, List> me : table.entrySet()) { 288 //List<Integer> k = me.getKey(); 289 if (first) { 290 first = false; 291 s.append("\n"); 292 } else { 293 s.append(",\n"); 294 } 295 v = me.getValue(); 296 for (Iterator jt = v.iterator(); jt.hasNext();) { 297 ExpVectorPair ep = (ExpVectorPair) jt.next(); 298 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next(); 299 if (ep.totalDeg() != 2) { // only base relations 300 continue; 301 } 302 s.append("( " + ep.getFirst().toString(vars) + " ), "); 303 if (cvars == null) { 304 s.append("( " + ep.getSecond().toString(vars) + " ), "); 305 } else { 306 s.append("( " + ep.getSecond().toString(cvars) + " ), "); 307 } 308 s.append("( " + p.toString(vars) + " )"); 309 if (jt.hasNext()) { 310 s.append(",\n"); 311 } 312 } 313 } 314 } else { 315 boolean first = true; 316 for (Map.Entry<List<Integer>, List> me : table.entrySet()) { 317 //List<Integer> k = me.getKey(); 318 if (first) { 319 first = false; 320 } else { 321 s.append(",\n"); 322 } 323 v = me.getValue(); 324 for (Iterator jt = v.iterator(); jt.hasNext();) { 325 ExpVectorPair ep = (ExpVectorPair) jt.next(); 326 s.append("( " + ep.getFirst().toString(vars) + " ), "); 327 if (cvars == null) { 328 s.append("( " + ep.getSecond().toString(vars) + " ), "); 329 } else { 330 s.append("( " + ep.getSecond().toString(cvars) + " ), "); 331 } 332 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next(); 333 //s.append("( " + p.toString(vars) + " )"); 334 s.append(" " + p.toString(vars)); 335 if (jt.hasNext()) { 336 s.append(",\n"); 337 } 338 } 339 } 340 } 341 s.append("\n)\n"); 342 return s.toString(); 343 } 344 345 346 /** 347 * Get a scripting compatible string representation. 348 * @return script compatible representation for this relation table. 349 */ 350 @SuppressWarnings({ "unchecked", "cast" }) 351 public String toScript() { 352 // Python case 353 String[] vars = ring.vars; 354 String[] cvars = null; 355 if (coeffTable) { 356 if (ring.coFac instanceof GenPolynomialRing) { 357 cvars = ((GenPolynomialRing<C>) (Object) ring.coFac).getVars(); 358 } else if (ring.coFac instanceof GenWordPolynomialRing) { 359 cvars = ((GenWordPolynomialRing<C>) (Object) ring.coFac).getVars(); 360 } 361 } 362 List v; 363 StringBuffer s = new StringBuffer("["); 364 boolean first = true; 365 for (Map.Entry<List<Integer>, List> me : table.entrySet()) { 366 //List<Integer> k = me.getKey(); 367 if (first) { 368 first = false; 369 s.append(""); 370 } else { 371 s.append(", "); 372 } 373 v = me.getValue(); 374 for (Iterator jt = v.iterator(); jt.hasNext();) { 375 ExpVectorPair ep = (ExpVectorPair) jt.next(); 376 GenPolynomial<C> p = (GenPolynomial<C>) jt.next(); 377 if (ep.totalDeg() > 2) { // only base relations 378 continue; 379 } 380 s.append("" + ep.getFirst().toScript(vars) + ", "); 381 if (coeffTable) { 382 String eps = ep.getSecond().toScript(cvars); 383 if (eps.isEmpty()) { // if from a deeper down ring 384 eps = p.leadingBaseCoefficient().abs().toScript(); 385 } 386 s.append("" + eps + ", "); 387 } else { 388 s.append("" + ep.getSecond().toScript(vars) + ", "); 389 } 390 //s.append("( " + p.toScript() + " )"); 391 s.append(" " + p.toScript()); 392 if (jt.hasNext()) { 393 s.append(", "); 394 } 395 } 396 } 397 s.append("]"); 398 return s.toString(); 399 } 400 401 402 /** 403 * Update or initialize RelationTable with new relation. relation is e * f = 404 * p. 405 * @param e first term. 406 * @param f second term. 407 * @param p solvable product polynomial. 408 */ 409 @SuppressWarnings({ "unchecked", "cast" }) 410 public synchronized void update(ExpVector e, ExpVector f, GenSolvablePolynomial<C> p) { 411 if (p == null || e == null || f == null) { 412 throw new IllegalArgumentException("RelationTable update e|f|p == null"); 413 } 414 GenSolvablePolynomialRing<C> sring = p.ring; 415 if (debug) { 416 logger.info("new relation = {} .*. {} = {}", sring.toScript(e), sring.toScript(f), p.toScript()); 417 } 418 // test equal HTs for left and right side 419 if (!coeffTable) { // old case 420 int[] de = e.dependencyOnVariables(); 421 int[] df = f.dependencyOnVariables(); 422 if (debug) { 423 logger.info("update e ? f {} {} : {} ? {}", Arrays.toString(de), Arrays.toString(df), 424 sring.toScript(e), sring.toScript(f)); 425 } 426 if (de.length != 1 || df.length != 1) { // can this be relaxed? 427 throw new IllegalArgumentException("RelationTable no univariate relations"); 428 } 429 if (de[de.length - 1] == df[0]) { // error 430 throw new IllegalArgumentException("RelationTable update e == f"); 431 } 432 if (de[de.length - 1] > df[0]) { // invalid update 433 throw new IllegalArgumentException("RelationTable update e < f"); 434 // ExpVector tmp = e; 435 // e = f; 436 // f = tmp; 437 // Map.Entry<ExpVector, C> m = p.leadingMonomial(); 438 // ExpVector ef = e.sum(f); 439 // if (!ef.equals(m.getKey())) { 440 // throw new IllegalArgumentException("update e*f != lt(p): " + sring.toScript(ef) 441 // + ", lt = " + sring.toScript(m.getKey())); 442 // } 443 // GenPolynomial<C> r = p.reductum(); //subtract(m.getValue(), m.getKey()); 444 // r = r.negate(); 445 // //p = (GenSolvablePolynomial<C>) r.sum(m.getValue(), m.getKey()); 446 // p = (GenSolvablePolynomial<C>) r; 447 // p.doPutToMap(m.getKey(), m.getValue()); 448 } 449 ExpVector ef = e.sum(f); 450 ExpVector lp = p.leadingExpVector(); 451 if (!ef.equals(lp)) { // check for suitable term order 452 logger.error("relation term order = {}", ring.tord); 453 throw new IllegalArgumentException( 454 "update e*f != lt(p): " + sring.toScript(ef) + " != " + sring.toScript(lp)); 455 } 456 } else { // is coeffTable 457 ExpVector lp = p.leadingExpVector(); 458 if (!e.equals(lp)) { // check for suitable term order 459 logger.error("relation term order = {}", ring.tord); 460 throw new IllegalArgumentException("Coefficient RelationTable update e != lt(p): " 461 + sring.toScript(e) + " != " + sring.toScript(lp)); 462 } 463 if (p.leadingBaseCoefficient() instanceof GenPolynomial) { 464 lp = ((GenPolynomial<C>) (Object) p.leadingBaseCoefficient()).leadingExpVector(); 465 if (!f.equals(lp)) { // check for suitable term order 466 logger.error("relation term order = {}", ring.tord); 467 logger.error("Coefficient RelationTable update f != lt(lfcd(p)): {}, f = {}, p = {}", 468 sring.toScript(e), f, p.toScript()); 469 throw new IllegalArgumentException("Coefficient RelationTable update f != lt(lfcd(p)): " 470 + e + ", f = " + f + ", p = " + p); 471 } 472 } else if (p.leadingBaseCoefficient() instanceof GenWordPolynomial) { 473 lp = ((GenWordPolynomial<C>) (Object) p.leadingBaseCoefficient()).leadingWord() 474 .leadingExpVector(); 475 if (!f.equals(lp)) { // check for suitable term order and word structure 476 logger.error("relation term order = {}", ring.tord); 477 logger.error("Coefficient RelationTable update f != lt(lfcd(p)): {}, f = {}, p = {}", 478 sring.toScript(e), f, p.toScript()); 479 throw new IllegalArgumentException("Coefficient RelationTable update f != lt(lfcd(p)): " 480 + e + ", f = " + f + ", p = " + p); 481 } 482 } 483 } 484 // now insert key-value 485 List<Integer> key = makeKey(e, f); 486 ExpVectorPair evp = new ExpVectorPair(e, f); // beware of leadingWord != leadingExpVector 487 if (key.size() != 2) { 488 logger.warn("key = {}, evp = {}", key, evp); 489 } 490 List part = table.get(key); 491 if (part == null) { // initialization 492 part = new LinkedList(); 493 part.add(evp); 494 part.add(p); 495 table.put(key, part); 496 return; 497 } 498 @SuppressWarnings("unused") 499 Object skip; 500 int index = -1; 501 synchronized (part) { // with lookup() 502 for (ListIterator it = part.listIterator(); it.hasNext();) { 503 ExpVectorPair look = (ExpVectorPair) it.next(); 504 skip = it.next(); // skip poly 505 if (look.isMultiple(evp)) { 506 index = it.nextIndex(); 507 // last index of or first index of: break 508 } 509 } 510 if (index < 0) { 511 index = 0; 512 } 513 part.add(index, evp); 514 part.add(index + 1, p); 515 } 516 // table.put( key, part ); // required?? 517 } 518 519 520 /** 521 * Update or initialize RelationTable with new relation. relation is e * f = 522 * p. 523 * @param E first term polynomial. 524 * @param F second term polynomial. 525 * @param p solvable product polynomial. 526 */ 527 @SuppressWarnings({ "unchecked", "cast" }) 528 public void update(GenPolynomial<C> E, GenPolynomial<C> F, GenSolvablePolynomial<C> p) { 529 if (E.isZERO() || F.isZERO()) { 530 throw new IllegalArgumentException("polynomials may not be zero: " + E + ", " + F); 531 } 532 C ce = E.leadingBaseCoefficient(); 533 C cf = F.leadingBaseCoefficient(); 534 if (!ce.isONE()) { 535 throw new IllegalArgumentException( 536 "lbcf of polynomials must be one: " + ce + ", " + cf + ", p = " + p); 537 } 538 ExpVector e = E.leadingExpVector(); 539 ExpVector f = F.leadingExpVector(); 540 if (coeffTable && f.isZERO()) { 541 if (cf instanceof GenPolynomial) { 542 f = ((GenPolynomial<C>) (Object) cf).leadingExpVector(); 543 } else if (cf instanceof GenWordPolynomial) { 544 f = ((GenWordPolynomial<C>) (Object) cf).leadingWord().leadingExpVector(); 545 } 546 } 547 //logger.info("update: {} .*. {} = {}", e, f, p); 548 update(e, f, p); 549 } 550 551 552 /** 553 * Update or initialize RelationTable with new relation. relation is e * f = 554 * p. 555 * @param E first term polynomial. 556 * @param F second term polynomial. 557 * @param p product polynomial. 558 */ 559 public void update(GenPolynomial<C> E, GenPolynomial<C> F, GenPolynomial<C> p) { 560 if (p.isZERO()) { 561 throw new IllegalArgumentException("polynomial may not be zero: " + p); 562 } 563 if (p.isONE()) { 564 throw new IllegalArgumentException("product of polynomials may not be one: " + p); 565 } 566 GenSolvablePolynomial<C> sp = new GenSolvablePolynomial<C>(ring, p.val); 567 update(E, F, sp); 568 } 569 570 571 /** 572 * Update or initialize RelationTable with new relation. relation is e * f = 573 * p. 574 * @param e first term. 575 * @param f second term. 576 * @param p solvable product polynomial. 577 */ 578 public void update(ExpVector e, ExpVector f, GenPolynomial<C> p) { 579 if (p.isZERO()) { 580 throw new IllegalArgumentException("polynomial may not be zero: " + p); 581 } 582 if (p.isONE()) { 583 throw new IllegalArgumentException("product of polynomials may not be one: " + p); 584 } 585 GenSolvablePolynomial<C> sp = new GenSolvablePolynomial<C>(ring, p.val); 586 update(e, f, sp); 587 } 588 589 590 /** 591 * Lookup RelationTable for existing relation. Find p with e * f = p. If no 592 * relation for e * f is contained in the table then return the symmetric 593 * product p = 1 e f. 594 * @param e first term. 595 * @param f second term. 596 * @return t table relation container, contains e' and f' with e f = e' 597 * lt(p) f'. 598 */ 599 @SuppressWarnings({ "unchecked", "cast" }) 600 public TableRelation<C> lookup(ExpVector e, ExpVector f) { 601 List<Integer> key = makeKey(e, f); 602 List part = table.get(key); 603 if (part == null) { // symmetric product 604 GenSolvablePolynomial<C> p = null; 605 C c = null; 606 if (!coeffTable) { 607 ExpVector ef = e.sum(f); 608 //p = new GenSolvablePolynomial<C>(ring, ring.getONECoefficient(), ef); 609 p = ring.valueOf(ef); 610 } else { 611 if (ring.coFac instanceof GenPolynomialRing) { 612 GenPolynomialRing<C> cofac = (GenPolynomialRing<C>) (Object) ring.coFac; 613 //System.out.println("f = " + f + ", e = " + e); 614 GenPolynomial<C> pc = cofac.valueOf(f); 615 c = (C) (Object) pc; 616 } else if (ring.coFac instanceof GenWordPolynomialRing) { 617 GenWordPolynomialRing<C> cofac = (GenWordPolynomialRing<C>) (Object) ring.coFac; 618 //System.out.println("f = " + f + ", e = " + e); 619 GenWordPolynomial<C> pc = cofac.valueOf(f); 620 c = (C) (Object) pc; 621 } 622 p = new GenSolvablePolynomial<C>(ring, c, e); 623 //System.out.println("pc = " + pc + ", p = " + p); 624 } 625 return new TableRelation<C>(null, null, p); 626 } 627 // no distinction between coefficient f or polynomial f 628 ExpVectorPair evp = new ExpVectorPair(e, f); 629 ExpVector ep = null; 630 ExpVector fp = null; 631 ExpVectorPair look = null; 632 GenSolvablePolynomial<C> p = null; 633 synchronized (part) { // with update() 634 for (Iterator it = part.iterator(); it.hasNext();) { 635 look = (ExpVectorPair) it.next(); 636 p = (GenSolvablePolynomial<C>) it.next(); 637 if (evp.isMultiple(look)) { 638 ep = e.subtract(look.getFirst()); 639 fp = f.subtract(look.getSecond()); 640 if (ep.isZERO()) { 641 ep = null; 642 } 643 if (fp.isZERO()) { 644 fp = null; 645 } 646 if (debug) { 647 if (p != null && p.ring.vars != null) { 648 logger.info("found relation = {} .*. {} = {}", e.toString(p.ring.vars), 649 f.toString(p.ring.vars), p); 650 } else { 651 logger.info("found relation = {} .*. {} = {}", e, f, p); 652 } 653 } 654 return new TableRelation<C>(ep, fp, p); 655 } 656 } 657 } 658 // unreachable code! 659 throw new RuntimeException("no entry found in relation table for " + evp); 660 } 661 662 663 /** 664 * Construct a key for (e,f). 665 * @param e first term. 666 * @param f second term. 667 * @return k key for (e,f). 668 */ 669 protected List<Integer> makeKey(ExpVector e, ExpVector f) { 670 int[] de = e.dependencyOnVariables(); 671 int[] df = f.dependencyOnVariables(); 672 List<Integer> key = new ArrayList<Integer>(de.length + df.length); 673 for (int i = 0; i < de.length; i++) { 674 key.add(Integer.valueOf(de[i])); 675 } 676 for (int i = 0; i < df.length; i++) { 677 key.add(Integer.valueOf(df[i])); 678 } 679 return key; 680 } 681 682 683 /** 684 * Size of the table. 685 * @return n number of non-commutative relations. 686 */ 687 public int size() { 688 int s = 0; 689 if (table == null || table.isEmpty()) { 690 return s; 691 } 692 for (Iterator<List> it = table.values().iterator(); it.hasNext();) { 693 List list = it.next(); 694 s += list.size() / 2; 695 } 696 return s; 697 } 698 699 700 /** 701 * Extend variables. Used e.g. in module embedding. Extend all ExpVectors 702 * and polynomials of the given relation table by i elements and put the 703 * relations into this table, i.e. this should be empty. 704 * @param tab a relation table to be extended and inserted into this. 705 */ 706 @SuppressWarnings("unchecked") 707 public void extend(RelationTable<C> tab) { 708 if (tab.table.isEmpty()) { 709 return; 710 } 711 // assert this.size() == 0 712 int i = ring.nvar - tab.ring.nvar; 713 int j = 0; 714 long k = 0l; 715 List val; 716 for (List<Integer> key : tab.table.keySet()) { 717 val = tab.table.get(key); 718 for (Iterator jt = val.iterator(); jt.hasNext();) { 719 ExpVectorPair ep = (ExpVectorPair) jt.next(); 720 ExpVector e = ep.getFirst(); 721 ExpVector f = ep.getSecond(); 722 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next(); 723 ExpVector ex = e.extend(i, j, k); 724 ExpVector fx; 725 if (coeffTable) { 726 fx = f; 727 } else { 728 fx = f.extend(i, j, k); 729 } 730 GenSolvablePolynomial<C> px = (GenSolvablePolynomial<C>) p.extend(ring, j, k); 731 this.update(ex, fx, px); 732 } 733 } 734 return; 735 } 736 737 738 /** 739 * Contract variables. Used e.g. in module embedding. Contract all 740 * ExpVectors and polynomials of the given relation table by i elements and 741 * put the relations into this table, i.e. this should be empty. 742 * @param tab a relation table to be contracted and inserted into this. 743 */ 744 @SuppressWarnings("unchecked") 745 public void contract(RelationTable<C> tab) { 746 if (tab.table.isEmpty()) { 747 return; 748 } 749 // assert this.size() == 0 750 int i = tab.ring.nvar - ring.nvar; 751 List val; 752 for (List<Integer> key : tab.table.keySet()) { 753 val = tab.table.get(key); 754 //System.out.println("key = " + key + ", val = " + val); 755 for (Iterator jt = val.iterator(); jt.hasNext();) { 756 ExpVectorPair ep = (ExpVectorPair) jt.next(); 757 ExpVector e = ep.getFirst(); 758 ExpVector f = ep.getSecond(); 759 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next(); 760 ExpVector ec = e.contract(i, e.length() - i); 761 ExpVector fc; 762 if (coeffTable) { 763 fc = f; 764 } else { 765 fc = f.contract(i, f.length() - i); 766 } 767 //System.out.println("ec = " + ec + ", fc = " + fc); 768 if (ec.isZERO()) { 769 continue; 770 } 771 Map<ExpVector, GenPolynomial<C>> mc = p.contract(ring); 772 if (mc.size() != 1) { 773 continue; 774 } 775 GenPolynomial<C> pc = mc.values().iterator().next(); 776 this.update(ec, fc, pc); 777 } 778 } 779 return; 780 } 781 782 783 /** 784 * Recursive representation. Split all ExpVectors and polynomials of the 785 * given relation table to lower elements and upper elements and put the 786 * relations into this table or this as coefficient table, i.e. this should 787 * be empty. 788 * @param tab a relation table to be contracted and inserted into this. 789 */ 790 @SuppressWarnings({ "unchecked", "cast" }) 791 public void recursive(RelationTable tab) { //<C> 792 if (tab.table.isEmpty()) { 793 return; 794 } 795 //System.out.println("rel ring = " + ring.toScript()); 796 // assert this.size() == 0 797 GenPolynomialRing<C> cring = (GenPolynomialRing<C>) (Object) ring.coFac; 798 //System.out.println("cring = " + cring.toScript()); 799 GenSolvablePolynomial<C> pc; 800 int i = ring.nvar; // tab.ring.nvar - 801 for (Object okey : tab.table.keySet()) { 802 List<Integer> key = (List<Integer>) okey; 803 List val = (List) tab.table.get(key); 804 //System.out.println("key = " + key + ", val = " + val); 805 for (Iterator jt = val.iterator(); jt.hasNext();) { 806 ExpVectorPair ep = (ExpVectorPair) jt.next(); // ?? concurrent mod exception 807 ExpVector e = ep.getFirst(); 808 ExpVector f = ep.getSecond(); 809 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next(); 810 ExpVector ec = e.contract(0, i); 811 ExpVector fc; 812 if (coeffTable) { 813 fc = f; 814 } else { 815 fc = f.contract(0, i); 816 } 817 //System.out.println("ec = " + ec + ", fc = " + fc); 818 if (ec.isZERO()) { 819 continue; 820 } 821 Map<ExpVector, GenPolynomial<C>> mc = p.contract(cring); 822 //System.out.println("mc = " + mc + ", p = " + p); 823 //System.out.println("mc.ring = " + mc.values().iterator().next().ring.toScript()); 824 if (mc.size() == 1) { // < 1 only for p == 0 825 pc = (GenSolvablePolynomial<C>) mc.values().iterator().next(); 826 this.update(ec, fc, pc); 827 } else { // construct recursive polynomial 828 GenSolvablePolynomial<C> qr = ring.getZERO(); 829 for (Map.Entry<ExpVector, GenPolynomial<C>> mce : mc.entrySet()) { 830 ExpVector g = mce.getKey(); 831 GenPolynomial<C> q = mce.getValue(); 832 C cq = (C) (Object) q; 833 GenSolvablePolynomial<C> qp = new GenSolvablePolynomial<C>(ring, cq, g); 834 qr = (GenSolvablePolynomial<C>) qr.sum(qp); 835 } 836 if (coeffTable) { 837 fc = ((GenPolynomial<C>) (Object) qr.leadingBaseCoefficient()).leadingExpVector(); 838 } 839 if (fc.isZERO()) { 840 continue; 841 } 842 //System.out.println("ec = " + ec + ", fc = " + fc + ", qr = " + qr); 843 if (coeffTable) { 844 String qrs = ring.toScript(ec) + " * " + qr.leadingBaseCoefficient() + " = " 845 + qr.toScript(); 846 logger.info("coeffTable: adding {}", qrs); 847 } else { 848 String qrs = ring.toScript(ec) + " * " + ring.toScript(fc) + " = " + qr.toScript(); 849 logger.info("table: adding {}", qrs); 850 } 851 this.update(ec, fc, qr); 852 } 853 } 854 } 855 return; 856 } 857 858 859 /** 860 * Reverse variables and relations. Used e.g. in opposite rings. Reverse all 861 * ExpVectors and polynomials of the given relation table and put the 862 * modified relations into this table, i.e. this should be empty. 863 * @param tab a relation table to be reverted and inserted into this. 864 */ 865 @SuppressWarnings("unchecked") 866 public void reverse(RelationTable<C> tab) { 867 if (tab.table.isEmpty()) { 868 return; 869 } 870 if (!table.isEmpty()) { 871 logger.error("reverse table not empty"); 872 } 873 int k = -1; 874 if (ring.tord.getEvord2() != 0 && ring.partial) { 875 k = ring.tord.getSplit(); 876 } 877 logger.debug("k split = {}", k); 878 //System.out.println("k split = " + k ); 879 //System.out.println("reversed ring = " + ring.toScript() ); 880 for (List<Integer> key : tab.table.keySet()) { 881 List val = tab.table.get(key); 882 for (Iterator jt = val.iterator(); jt.hasNext();) { 883 ExpVectorPair ep = (ExpVectorPair) jt.next(); 884 ExpVector e = ep.getFirst(); 885 ExpVector f = ep.getSecond(); 886 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next(); 887 //logger.info("e pre reverse = {}", e ); 888 //logger.info("f pre reverse = {}", f ); 889 //logger.info("p pre reverse = {}", p ); 890 //if (e.degree() > 1 || f.degree() > 1) { // not required 891 // continue; // revert only base relations 892 //} 893 ExpVector ex; 894 ExpVector fx; 895 GenSolvablePolynomial<C> px; 896 boolean change = true; // if relevant vars reversed 897 if (k >= 0) { 898 ex = e.reverse(k); 899 if (coeffTable) { 900 fx = f; 901 } else { 902 fx = f.reverse(k); 903 } 904 // todo check non-com / relevant vars for change 905 //int[] ed = ex.dependencyOnVariables(); // = e 906 //if (ed.length == 0 || ed[0] >= k) { // k >= 0 907 // change = false; 908 //} 909 //int[] fd = fx.dependencyOnVariables(); // = f 910 //if (fd.length == 0 || fd[0] >= k) { // k >= 0 911 // change = false; 912 //} 913 } else { 914 ex = e.reverse(); 915 if (coeffTable) { 916 fx = f; 917 } else { 918 fx = f.reverse(); 919 } 920 } 921 px = (GenSolvablePolynomial<C>) p.reverse(ring); 922 //System.out.println("update, p, px: " + p.toScript() + " reverse:" + px.toScript() ); 923 if (!change) { 924 this.update(e, f, px); // same order 925 } else { 926 if (coeffTable) { 927 this.update(ex, fx, px); // same order 928 } else { 929 this.update(fx, ex, px); // opposite order 930 } 931 } 932 } 933 } 934 return; 935 } 936 937 938 /** 939 * Convert relation table to list of polynomial triples. 940 * @return rel = (e1,f1,p1, ...) where ei * fi = pi are solvable relations. 941 */ 942 @SuppressWarnings({ "unchecked", "cast" }) 943 public List<GenSolvablePolynomial<C>> relationList() { 944 List<GenSolvablePolynomial<C>> rels = new ArrayList<GenSolvablePolynomial<C>>(); 945 for (Map.Entry<List<Integer>, List> me : table.entrySet()) { 946 List v = me.getValue(); 947 for (Iterator jt = v.iterator(); jt.hasNext();) { 948 ExpVectorPair ep = (ExpVectorPair) jt.next(); 949 ExpVector e = ep.getFirst(); 950 GenSolvablePolynomial<C> pe = ring.valueOf(e); 951 ExpVector f = ep.getSecond(); 952 GenSolvablePolynomial<C> pf = null; 953 if (coeffTable) { 954 C cf = null; 955 if (ring.coFac instanceof GenPolynomialRing) { 956 GenPolynomial<C> cpf; 957 cpf = ((GenPolynomialRing<C>) (Object) ring.coFac).valueOf(f); 958 cf = (C) (Object) cpf; // down cast 959 } else if (ring.coFac instanceof GenWordPolynomialRing) { 960 GenWordPolynomial<C> cpf; 961 cpf = ((GenWordPolynomialRing<C>) (Object) ring.coFac).valueOf(f); 962 cf = (C) (Object) cpf; // down cast 963 } 964 pf = ring.valueOf(cf); 965 } else { 966 pf = ring.valueOf(f); 967 } 968 GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) jt.next(); 969 rels.add(pe); 970 rels.add(pf); 971 rels.add(p); 972 } 973 } 974 return rels; 975 } 976 977 978 /** 979 * Add list of polynomial triples as relations. 980 * @param rel = (e1,f1,p1, ...) where ei * fi = pi are solvable relations. 981 * <b>Note:</b> Only because of type erasure, equivalent to 982 * addRelations(). 983 */ 984 public void addSolvRelations(List<GenSolvablePolynomial<C>> rel) { 985 PolynomialList<C> Prel = new PolynomialList<C>(ring, rel); 986 addRelations(Prel.getList()); 987 } 988 989 990 /** 991 * Add list of polynomial triples as relations. 992 * @param rel = (e1,f1,p1, ...) where ei * fi = pi are solvable relations. 993 */ 994 @SuppressWarnings({ "unchecked", "cast" }) 995 public void addRelations(List<GenPolynomial<C>> rel) { 996 if (rel == null || rel.isEmpty()) { 997 return; 998 } 999 Iterator<GenPolynomial<C>> relit = rel.iterator(); 1000 while (relit.hasNext()) { 1001 GenPolynomial<C> E = relit.next(); 1002 ExpVector e = E.leadingExpVector(); 1003 ExpVector f = null; 1004 if (!relit.hasNext()) { 1005 throw new IllegalArgumentException("F and poly part missing"); 1006 } 1007 GenPolynomial<C> F = relit.next(); 1008 if (!relit.hasNext()) { 1009 throw new IllegalArgumentException("poly part missing"); 1010 } 1011 GenPolynomial<C> P = relit.next(); 1012 if (coeffTable) { 1013 if (!F.isConstant()) { 1014 throw new IllegalArgumentException("F not constant for coeffTable: " + F); 1015 } 1016 if (ring.coFac instanceof GenPolynomialRing) { 1017 f = ((GenPolynomial<C>) (Object) F.leadingBaseCoefficient()).leadingExpVector(); 1018 } else if (ring.coFac instanceof GenWordPolynomialRing) { 1019 f = ((GenWordPolynomial<C>) (Object) F.leadingBaseCoefficient()).leadingWord() 1020 .leadingExpVector(); 1021 } 1022 } else { 1023 f = F.leadingExpVector(); 1024 } 1025 update(e, f, P); 1026 } 1027 return; 1028 } 1029 1030}