001/* 002 * $Id$ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.IOException; 009import java.io.Reader; 010import java.io.StringReader; 011import java.math.BigInteger; 012import java.util.ArrayList; 013import java.util.List; 014import java.util.Random; 015 016import org.apache.logging.log4j.LogManager; 017import org.apache.logging.log4j.Logger; 018 019import edu.jas.kern.PrettyPrint; 020import edu.jas.kern.Scripting; 021import edu.jas.structure.RingElem; 022import edu.jas.structure.RingFactory; 023 024 025/** 026 * RecSolvableWordPolynomialRing generic recursive solvable polynomial factory 027 * implementing RingFactory and extending GenSolvablePolynomialRing factory. 028 * Factory for n-variate ordered solvable polynomials over non-commutative word 029 * polynomial coefficients. The non-commutative multiplication relations are 030 * maintained in a relation table and the non-commutative multiplication 031 * relations between the coefficients and the main variables are maintained in a 032 * coefficient relation table. Almost immutable object, except variable names 033 * and relation table contents. 034 * @param <C> base coefficient type. 035 * @author Heinz Kredel 036 */ 037 038public class RecSolvableWordPolynomialRing<C extends RingElem<C>> 039 extends GenSolvablePolynomialRing<GenWordPolynomial<C>> { 040 041 042 /** 043 * The solvable multiplication relations between variables and coefficients. 044 */ 045 public final RelationTable<GenWordPolynomial<C>> coeffTable; 046 047 048 /** 049 * The constant polynomial 0 for this ring. Hides super ZERO. 050 */ 051 public final RecSolvableWordPolynomial<C> ZERO; 052 053 054 /** 055 * The constant polynomial 1 for this ring. Hides super ONE. 056 */ 057 public final RecSolvableWordPolynomial<C> ONE; 058 059 060 private static final Logger logger = LogManager.getLogger(RecSolvableWordPolynomialRing.class); 061 062 063 //private static final boolean debug = logger.isDebugEnabled(); 064 065 066 /** 067 * The constructor creates a solvable polynomial factory object with the 068 * default term order and commutative relations. 069 * @param cf factory for coefficients of type C. 070 * @param n number of variables. 071 */ 072 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, int n) { 073 this(cf, n, new TermOrder(), null, null); 074 } 075 076 077 /** 078 * The constructor creates a solvable polynomial factory object with the 079 * default term order. 080 * @param cf factory for coefficients of type C. 081 * @param n number of variables. 082 * @param rt solvable multiplication relations. 083 */ 084 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, int n, 085 RelationTable<GenWordPolynomial<C>> rt) { 086 this(cf, n, new TermOrder(), null, rt); 087 } 088 089 090 /** 091 * The constructor creates a solvable polynomial factory object with the 092 * given term order and commutative relations. 093 * @param cf factory for coefficients of type C. 094 * @param n number of variables. 095 * @param t a term order. 096 */ 097 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, int n, TermOrder t) { 098 this(cf, n, t, null, null); 099 } 100 101 102 /** 103 * The constructor creates a solvable polynomial factory object with the 104 * given term order. 105 * @param cf factory for coefficients of type C. 106 * @param n number of variables. 107 * @param t a term order. 108 * @param rt solvable multiplication relations. 109 */ 110 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, int n, TermOrder t, 111 RelationTable<GenWordPolynomial<C>> rt) { 112 this(cf, n, t, null, rt); 113 } 114 115 116 /** 117 * The constructor creates a solvable polynomial factory object with the 118 * given term order and commutative relations. 119 * @param cf factory for coefficients of type C. 120 * @param n number of variables. 121 * @param t a term order. 122 * @param v names for the variables. 123 */ 124 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, int n, TermOrder t, 125 String[] v) { 126 this(cf, n, t, v, null); 127 } 128 129 130 /** 131 * The constructor creates a solvable polynomial factory object with the 132 * given term order and commutative relations. 133 * @param cf factory for coefficients of type C. 134 * @param t a term order. 135 * @param v names for the variables. 136 */ 137 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, TermOrder t, String[] v) { 138 this(cf, v.length, t, v, null); 139 } 140 141 142 /** 143 * The constructor creates a solvable polynomial factory object with the 144 * default term order. 145 * @param cf factory for coefficients of type C. 146 * @param v names for the variables. 147 */ 148 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, String[] v) { 149 this(cf, v.length, new TermOrder(), v, null); 150 } 151 152 153 /** 154 * The constructor creates a solvable polynomial factory object with the 155 * given term order. 156 * @param cf factory for coefficients of type C. 157 * @param n number of variables. 158 * @param t a term order. 159 * @param v names for the variables. 160 * @param rt solvable multiplication relations. 161 */ 162 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, int n, TermOrder t, String[] v, 163 RelationTable<GenWordPolynomial<C>> rt) { 164 super(cf, n, t, v, rt); 165 //if (rt == null) { // handled in super } 166 coeffTable = new RelationTable<GenWordPolynomial<C>>(this, true); 167 ZERO = new RecSolvableWordPolynomial<C>(this); 168 GenWordPolynomial<C> coeff = coFac.getONE(); 169 //evzero = ExpVector.create(nvar); // from super 170 ONE = new RecSolvableWordPolynomial<C>(this, coeff, evzero); 171 } 172 173 174 /** 175 * The constructor creates a solvable polynomial factory object with the the 176 * same term order, number of variables and variable names as the given 177 * polynomial factory, only the coefficient factories differ and the 178 * solvable multiplication relations are <b>empty</b>. 179 * @param cf factory for coefficients of type C. 180 * @param o other solvable polynomial ring. 181 */ 182 public RecSolvableWordPolynomialRing(RingFactory<GenWordPolynomial<C>> cf, 183 RecSolvableWordPolynomialRing o) { 184 this(cf, o.nvar, o.tord, o.getVars(), null); 185 } 186 187 188 /** 189 * Get the String representation. 190 * @see java.lang.Object#toString() 191 */ 192 @Override 193 public String toString() { 194 String res = super.toString(); 195 if (PrettyPrint.isTrue()) { 196 //res += "\n" + table.toString(vars); 197 res += "\n" + coeffTable.toString(vars); 198 } else { 199 res += ", #rel = " + table.size() + " + " + coeffTable.size(); 200 } 201 return res; 202 } 203 204 205 /** 206 * Get a scripting compatible string representation. 207 * @return script compatible representation for this Element. 208 * @see edu.jas.structure.Element#toScript() 209 */ 210 @Override 211 public String toScript() { 212 StringBuffer s = new StringBuffer(); 213 switch (Scripting.getLang()) { 214 case Ruby: 215 s.append("SolvPolyRing.new("); 216 break; 217 case Python: 218 default: 219 s.append("SolvPolyRing("); 220 } 221 if (coFac instanceof RingElem) { 222 s.append(((RingElem<GenWordPolynomial<C>>) coFac).toScriptFactory()); 223 } else { 224 s.append(coFac.toScript().trim()); 225 } 226 s.append(",\"" + varsToString() + "\","); 227 String to = tord.toScript(); 228 s.append(to); 229 if (table.size() > 0) { 230 String rel = table.toScript(); 231 s.append(",rel="); 232 s.append(rel); 233 } 234 if (coeffTable.size() > 0) { 235 String rel = coeffTable.toScript(); 236 s.append(",coeffrel="); 237 s.append(rel); 238 } 239 s.append(")"); 240 return s.toString(); 241 } 242 243 244 /** 245 * Comparison with any other object. 246 * @see java.lang.Object#equals(java.lang.Object) 247 */ 248 @Override 249 @SuppressWarnings("unchecked") 250 public boolean equals(Object other) { 251 if (other == null) { 252 return false; 253 } 254 if (!(other instanceof RecSolvableWordPolynomialRing)) { 255 return false; 256 } 257 // do a super.equals( ) 258 if (!super.equals(other)) { 259 return false; 260 } 261 RecSolvableWordPolynomialRing<C> oring = (RecSolvableWordPolynomialRing<C>) other; 262 // check same base relations 263 //if ( ! table.equals(oring.table) ) { // done in super 264 // return false; 265 //} 266 if (!coeffTable.equals(oring.coeffTable)) { 267 return false; 268 } 269 return true; 270 } 271 272 273 /** 274 * Hash code for this polynomial ring. 275 * @see java.lang.Object#hashCode() 276 */ 277 @Override 278 public int hashCode() { 279 int h; 280 h = super.hashCode(); 281 h = 37 * h + table.hashCode(); // may be different after some computations 282 h = 37 * h + coeffTable.hashCode(); // may be different 283 return h; 284 } 285 286 287 /** 288 * Get the zero element. 289 * @return 0 as RecSolvableWordPolynomial<C>. 290 */ 291 @Override 292 public RecSolvableWordPolynomial<C> getZERO() { 293 return ZERO; 294 } 295 296 297 /** 298 * Get the one element. 299 * @return 1 as RecSolvableWordPolynomial<C>. 300 */ 301 @Override 302 public RecSolvableWordPolynomial<C> getONE() { 303 return ONE; 304 } 305 306 307 /** 308 * Query if this ring is commutative. 309 * @return true if this ring is commutative, else false. 310 */ 311 @Override 312 public boolean isCommutative() { 313 if (coeffTable.isEmpty()) { 314 return super.isCommutative(); 315 } 316 return false; 317 } 318 319 320 /** 321 * Query if this ring is associative. Test if the relations between the mian 322 * variables and the coefficient generators define an associative solvable 323 * ring. 324 * @return true, if this ring is associative, else false. 325 */ 326 @SuppressWarnings("unused") 327 @Override 328 public boolean isAssociative() { 329 if (!coFac.isAssociative()) { 330 return false; 331 } 332 RecSolvableWordPolynomial<C> Xi, Xj, Xk, p, q; 333 List<GenPolynomial<GenWordPolynomial<C>>> gens = generators(); 334 //System.out.println("Rec word gens = " + gens); 335 int ngen = gens.size(); 336 for (int i = 0; i < ngen; i++) { 337 Xi = (RecSolvableWordPolynomial<C>) gens.get(i); 338 if (Xi.isONE()) { 339 continue; 340 } 341 for (int j = i + 1; j < ngen; j++) { 342 Xj = (RecSolvableWordPolynomial<C>) gens.get(j); 343 for (int k = j + 1; k < ngen; k++) { 344 Xk = (RecSolvableWordPolynomial<C>) gens.get(k); 345 try { 346 p = Xk.multiply(Xj).multiply(Xi); 347 q = Xk.multiply(Xj.multiply(Xi)); 348 if (!p.equals(q)) { 349 if (logger.isInfoEnabled()) { 350 logger.info("Xi = {}, Xj = {}, Xk = {}", Xi, Xj, Xk); 351 logger.info("p = ( Xk * Xj ) * Xi = {}", p); 352 logger.info("q = Xk * ( Xj * Xi ) = {}", q); 353 } 354 return false; 355 } 356 } catch (RuntimeException e) { 357 e.printStackTrace(); 358 System.out.println("Xk = " + Xk + ", Xj = " + Xj + ", Xi = " + Xi); 359 } 360 } 361 } 362 } 363 return true; 364 } 365 366 367 /** 368 * Get a (constant) RecSolvableWordPolynomial<C> element from a 369 * coefficient value. 370 * @param a coefficient. 371 * @return a RecSolvableWordPolynomial<C>. 372 */ 373 @Override 374 public RecSolvableWordPolynomial<C> valueOf(GenWordPolynomial<C> a) { 375 return new RecSolvableWordPolynomial<C>(this, a); 376 } 377 378 379 /** 380 * Get a RecSolvableWordPolynomial<C> element from an ExpVector. 381 * @param e exponent vector. 382 * @return a RecSolvableWordPolynomial<C>. 383 */ 384 @Override 385 public RecSolvableWordPolynomial<C> valueOf(ExpVector e) { 386 return valueOf(coFac.getONE(), e); 387 } 388 389 390 /** 391 * Get a RecSolvableWordPolynomial<C> element from a coefficient and an 392 * ExpVector. 393 * @param a coefficient. 394 * @param e exponent vector. 395 * @return a RecSolvableWordPolynomial<C>. 396 */ 397 @Override 398 public RecSolvableWordPolynomial<C> valueOf(GenWordPolynomial<C> a, ExpVector e) { 399 return new RecSolvableWordPolynomial<C>(this, a, e); 400 } 401 402 403 /** 404 * Get a (constant) RecSolvableWordPolynomial<C> element from a long 405 * value. 406 * @param a long. 407 * @return a RecSolvableWordPolynomial<C>. 408 */ 409 @Override 410 public RecSolvableWordPolynomial<C> fromInteger(long a) { 411 return new RecSolvableWordPolynomial<C>(this, coFac.fromInteger(a), evzero); 412 } 413 414 415 /** 416 * Get a (constant) RecSolvableWordPolynomial<C> element from a 417 * BigInteger value. 418 * @param a BigInteger. 419 * @return a RecSolvableWordPolynomial<C>. 420 */ 421 @Override 422 public RecSolvableWordPolynomial<C> fromInteger(BigInteger a) { 423 return new RecSolvableWordPolynomial<C>(this, coFac.fromInteger(a), evzero); 424 } 425 426 427 /** 428 * Random solvable polynomial. Generates a random solvable polynomial with k 429 * = 5, l = n, d = (nvar == 1) ? n : 3, q = (nvar == 1) ? 0.7 : 0.3. 430 * @param n number of terms. 431 * @return a random solvable polynomial. 432 */ 433 @Override 434 public RecSolvableWordPolynomial<C> random(int n) { 435 return random(n, random); 436 } 437 438 439 /** 440 * Random solvable polynomial. Generates a random solvable polynomial with k 441 * = 5, l = n, d = (nvar == 1) ? n : 3, q = (nvar == 1) ? 0.7 : 0.3. 442 * @param n number of terms. 443 * @param rnd is a source for random bits. 444 * @return a random solvable polynomial. 445 */ 446 @Override 447 public RecSolvableWordPolynomial<C> random(int n, Random rnd) { 448 if (nvar == 1) { 449 return random(5, n, n, 0.7f, rnd); 450 } 451 return random(5, n, 3, 0.3f, rnd); 452 } 453 454 455 /** 456 * Generate a random solvable polynomial. 457 * @param k bitsize of random coefficients. 458 * @param l number of terms. 459 * @param d maximal degree in each variable. 460 * @param q density of nozero exponents. 461 * @return a random solvable polynomial. 462 */ 463 @Override 464 public RecSolvableWordPolynomial<C> random(int k, int l, int d, float q) { 465 return random(k, l, d, q, random); 466 } 467 468 469 /** 470 * Random solvable polynomial. 471 * @param k size of random coefficients. 472 * @param l number of terms. 473 * @param d maximal degree in each variable. 474 * @param q density of nozero exponents. 475 * @param rnd is a source for random bits. 476 * @return a random solvable polynomial. 477 */ 478 @Override 479 public RecSolvableWordPolynomial<C> random(int k, int l, int d, float q, Random rnd) { 480 RecSolvableWordPolynomial<C> r = getZERO(); // copy( ZERO ); 481 ExpVector e; 482 GenWordPolynomial<C> a; 483 // add random coeffs and exponents 484 for (int i = 0; i < l; i++) { 485 e = ExpVector.random(nvar, d, q, rnd); 486 a = coFac.random(k, rnd); 487 r = (RecSolvableWordPolynomial<C>) r.sum(a, e); 488 // somewhat inefficient but clean 489 } 490 return r; 491 } 492 493 494 /** 495 * Copy polynomial c. 496 * @param c 497 * @return a copy of c. 498 */ 499 public RecSolvableWordPolynomial<C> copy(RecSolvableWordPolynomial<C> c) { 500 return new RecSolvableWordPolynomial<C>(this, c.val); 501 } 502 503 504 /** 505 * Parse a solvable polynomial with the use of GenPolynomialTokenizer 506 * @param s String. 507 * @return RecSolvableWordPolynomial from s. 508 */ 509 @Override 510 public RecSolvableWordPolynomial<C> parse(String s) { 511 return parse(new StringReader(s)); 512 } 513 514 515 /** 516 * Parse a solvable polynomial with the use of GenPolynomialTokenizer 517 * @param r Reader. 518 * @return next RecSolvableWordPolynomial from r. 519 */ 520 @Override 521 @SuppressWarnings("unchecked") 522 public RecSolvableWordPolynomial<C> parse(Reader r) { 523 GenPolynomialTokenizer pt = new GenPolynomialTokenizer(this, r); 524 RecSolvableWordPolynomial<C> p = null; 525 try { 526 GenSolvablePolynomial<GenWordPolynomial<C>> s = pt.nextSolvablePolynomial(); 527 p = new RecSolvableWordPolynomial<C>(this, s); 528 } catch (IOException e) { 529 logger.error("{} parse {}", e, this); 530 p = ZERO; 531 } 532 return p; 533 } 534 535 536 /** 537 * Generate univariate solvable polynomial in a given variable. 538 * @param i the index of the variable. 539 * @return X_i as solvable univariate polynomial. 540 */ 541 @Override 542 public RecSolvableWordPolynomial<C> univariate(int i) { 543 return (RecSolvableWordPolynomial<C>) super.univariate(i); 544 } 545 546 547 /** 548 * Generate univariate solvable polynomial in a given variable with given 549 * exponent. 550 * @param i the index of the variable. 551 * @param e the exponent of the variable. 552 * @return X_i^e as solvable univariate polynomial. 553 */ 554 @Override 555 public RecSolvableWordPolynomial<C> univariate(int i, long e) { 556 return (RecSolvableWordPolynomial<C>) super.univariate(i, e); 557 } 558 559 560 /** 561 * Generate univariate solvable polynomial in a given variable with given 562 * exponent. 563 * @param modv number of module variables. 564 * @param i the index of the variable. 565 * @param e the exponent of the variable. 566 * @return X_i^e as solvable univariate polynomial. 567 */ 568 @Override 569 public RecSolvableWordPolynomial<C> univariate(int modv, int i, long e) { 570 return (RecSolvableWordPolynomial<C>) super.univariate(modv, i, e); 571 } 572 573 574 /** 575 * Generate list of univariate polynomials in all variables. 576 * @return List(X_1,...,X_n) a list of univariate polynomials. 577 */ 578 @Override 579 public List<RecSolvableWordPolynomial<C>> univariateList() { 580 //return castToSolvableList( super.univariateList() ); 581 return univariateList(0, 1L); 582 } 583 584 585 /** 586 * Generate list of univariate polynomials in all variables. 587 * @param modv number of module variables. 588 * @return List(X_1,...,X_n) a list of univariate polynomials. 589 */ 590 @Override 591 public List<RecSolvableWordPolynomial<C>> univariateList(int modv) { 592 return univariateList(modv, 1L); 593 } 594 595 596 /** 597 * Generate list of univariate polynomials in all variables with given 598 * exponent. 599 * @param modv number of module variables. 600 * @param e the exponent of the variables. 601 * @return List(X_1^e,...,X_n^e) a list of univariate polynomials. 602 */ 603 @Override 604 public List<RecSolvableWordPolynomial<C>> univariateList(int modv, long e) { 605 List<RecSolvableWordPolynomial<C>> pols = new ArrayList<RecSolvableWordPolynomial<C>>(nvar); 606 int nm = nvar - modv; 607 for (int i = 0; i < nm; i++) { 608 RecSolvableWordPolynomial<C> p = univariate(modv, nm - 1 - i, e); 609 pols.add(p); 610 } 611 return pols; 612 } 613 614 615 /** 616 * Extend variables. Used e.g. in module embedding. Extend number of 617 * variables by i. 618 * @param i number of variables to extend. 619 * @return extended solvable polynomial ring factory. 620 */ 621 @Override 622 public RecSolvableWordPolynomialRing<C> extend(int i) { 623 GenSolvablePolynomialRing<GenWordPolynomial<C>> pfac = super.extend(i); 624 RecSolvableWordPolynomialRing<C> spfac = new RecSolvableWordPolynomialRing<C>(pfac.coFac, pfac.nvar, 625 pfac.tord, pfac.vars, pfac.table); 626 //spfac.table.extend(this.table); // pfac.table 627 spfac.coeffTable.extend(this.coeffTable); 628 return spfac; 629 } 630 631 632 /** 633 * Extend variables. Used e.g. in module embedding. Extend number of 634 * variables by length(vn). New variables commute with the exiting 635 * variables. 636 * @param vs names for extended variables. 637 * @return extended polynomial ring factory. 638 */ 639 @Override 640 public RecSolvableWordPolynomialRing<C> extend(String[] vs) { 641 GenSolvablePolynomialRing<GenWordPolynomial<C>> pfac = super.extend(vs); 642 RecSolvableWordPolynomialRing<C> spfac = new RecSolvableWordPolynomialRing<C>(pfac.coFac, pfac.nvar, 643 pfac.tord, pfac.vars, pfac.table); 644 //spfac.table.extend(this.table); // pfac.table?? 645 spfac.coeffTable.extend(this.coeffTable); 646 return spfac; 647 } 648 649 650 /** 651 * Contract variables. Used e.g. in module embedding. Contract number of 652 * variables by i. 653 * @param i number of variables to remove. 654 * @return contracted solvable polynomial ring factory. 655 */ 656 @Override 657 public RecSolvableWordPolynomialRing<C> contract(int i) { 658 GenPolynomialRing<GenWordPolynomial<C>> pfac = super.contract(i); 659 RecSolvableWordPolynomialRing<C> spfac = new RecSolvableWordPolynomialRing<C>(pfac.coFac, pfac.nvar, 660 pfac.tord, pfac.vars); 661 spfac.table.contract(this.table); 662 spfac.coeffTable.contract(this.coeffTable); 663 return spfac; 664 } 665 666 667 /** 668 * Reverse variables. Used e.g. in opposite rings. 669 * @return solvable polynomial ring factory with reversed variables. 670 */ 671 @Override 672 public RecSolvableWordPolynomialRing<C> reverse() { 673 return reverse(false); 674 } 675 676 677 /** 678 * Reverse variables. Used e.g. in opposite rings. 679 * @param partial true for partially reversed term orders. 680 * @return solvable polynomial ring factory with reversed variables. 681 */ 682 @Override 683 public RecSolvableWordPolynomialRing<C> reverse(boolean partial) { 684 GenPolynomialRing<GenWordPolynomial<C>> pfac = super.reverse(partial); 685 RecSolvableWordPolynomialRing<C> spfac = new RecSolvableWordPolynomialRing<C>(pfac.coFac, pfac.nvar, 686 pfac.tord, pfac.vars); 687 spfac.partial = partial; 688 spfac.table.reverse(this.table); 689 spfac.coeffTable.reverse(this.coeffTable); 690 return spfac; 691 } 692 693 694 /* not possible: 695 * Distributive representation as polynomial with all main variables. 696 * @return distributive polynomial ring factory. 697 @SuppressWarnings({"cast","unchecked"}) 698 public static <C extends RingElem<C>> // must be static because of types 699 GenSolvablePolynomialRing<C> distribute(RecSolvableWordPolynomialRing<C> rf) { 700 } 701 */ 702 703 704 /** 705 * Permutation of polynomial ring variables. 706 * @param P permutation. 707 * @return P(this). 708 */ 709 @Override 710 public GenSolvablePolynomialRing<GenWordPolynomial<C>> permutation(List<Integer> P) { 711 if (!coeffTable.isEmpty()) { 712 throw new UnsupportedOperationException("permutation with coeff relations: " + this); 713 } 714 GenSolvablePolynomialRing<GenWordPolynomial<C>> pfac = (GenSolvablePolynomialRing<GenWordPolynomial<C>>) super.permutation( 715 P); 716 return pfac; 717 } 718 719}