001/* 002 * $Id: MultiVarPowerSeriesRing.java 5335 2015-12-06 12:18:41Z kredel $ 003 */ 004 005package edu.jas.ps; 006 007 008import java.io.Reader; 009import java.util.ArrayList; 010import java.util.Arrays; 011import java.util.BitSet; 012import java.util.HashMap; 013import java.util.List; 014import java.util.Random; 015 016import edu.jas.kern.PrettyPrint; 017import edu.jas.poly.ExpVector; 018import edu.jas.poly.GenPolynomial; 019import edu.jas.poly.GenPolynomialRing; 020import edu.jas.poly.Monomial; 021import edu.jas.structure.RingElem; 022import edu.jas.structure.RingFactory; 023import edu.jas.structure.UnaryFunctor; 024import edu.jas.util.ListUtil; 025 026 027/** 028 * Multivariate power series ring implementation. Uses lazy evaluated generating 029 * function for coefficients. 030 * @param <C> ring element type 031 * @author Heinz Kredel 032 */ 033 034public class MultiVarPowerSeriesRing<C extends RingElem<C>> implements RingFactory<MultiVarPowerSeries<C>> { 035 036 037 /** 038 * A default random sequence generator. 039 */ 040 protected final static Random random = new Random(); 041 042 043 /** 044 * Default truncate. 045 */ 046 public final static int DEFAULT_TRUNCATE = 7; 047 048 049 /** 050 * Truncate. 051 */ 052 int truncate; 053 054 055 /** 056 * Zero ExpVector. 057 */ 058 public final ExpVector EVZERO; 059 060 061 /** 062 * Coefficient ring factory. 063 */ 064 public final RingFactory<C> coFac; 065 066 067 /** 068 * The number of variables. 069 */ 070 public final int nvar; 071 072 073 /** 074 * The names of the variables. This value can be modified. 075 */ 076 protected String[] vars; 077 078 079 /** 080 * The constant power series 1 for this ring. 081 */ 082 public final MultiVarPowerSeries<C> ONE; 083 084 085 /** 086 * The constant power series 0 for this ring. 087 */ 088 public final MultiVarPowerSeries<C> ZERO; 089 090 091 /** 092 * No argument constructor. 093 */ 094 @SuppressWarnings("unused") 095 private MultiVarPowerSeriesRing() { 096 throw new IllegalArgumentException("do not use no-argument constructor"); 097 } 098 099 100 /** 101 * Constructor. 102 * @param fac polynomial ring factory. 103 */ 104 public MultiVarPowerSeriesRing(GenPolynomialRing<C> fac) { 105 this(fac.coFac, fac.nvar, fac.getVars()); 106 } 107 108 109 /** 110 * Constructor. 111 * @param coFac coefficient ring factory. 112 */ 113 public MultiVarPowerSeriesRing(RingFactory<C> coFac, int nv) { 114 this(coFac, nv, DEFAULT_TRUNCATE); 115 } 116 117 118 /** 119 * Constructor. 120 * @param coFac coefficient ring factory. 121 * @param truncate index of truncation. 122 */ 123 public MultiVarPowerSeriesRing(RingFactory<C> coFac, int nv, int truncate) { 124 this(coFac, nv, truncate, null); 125 } 126 127 128 /** 129 * Constructor. 130 * @param coFac coefficient ring factory. 131 * @param names of the variables. 132 */ 133 public MultiVarPowerSeriesRing(RingFactory<C> coFac, String[] names) { 134 this(coFac, names.length, DEFAULT_TRUNCATE, names); 135 } 136 137 138 /** 139 * Constructor. 140 * @param cofac coefficient ring factory. 141 * @param nv number of variables. 142 * @param names of the variables. 143 */ 144 public MultiVarPowerSeriesRing(RingFactory<C> cofac, int nv, String[] names) { 145 this(cofac, nv, DEFAULT_TRUNCATE, names); 146 } 147 148 149 /** 150 * Constructor. 151 * @param cofac coefficient ring factory. 152 * @param truncate index of truncation. 153 * @param names of the variables. 154 */ 155 public MultiVarPowerSeriesRing(RingFactory<C> cofac, int nv, int truncate, String[] names) { 156 this.coFac = cofac; 157 this.nvar = nv; 158 this.truncate = truncate; 159 if (names == null) { 160 vars = null; 161 } else { 162 vars = Arrays.copyOf(names,names.length); // > Java-5 163 } 164 if (vars == null) { 165 if (PrettyPrint.isTrue()) { 166 vars = GenPolynomialRing.newVars("x", nvar); 167 } 168 } else { 169 if (vars.length != nvar) { 170 throw new IllegalArgumentException("incompatible variable size " + vars.length + ", " + nvar); 171 } 172 GenPolynomialRing.addVars(vars); 173 } 174 EVZERO = ExpVector.create(nvar); 175 ONE = new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) { 176 177 178 @Override 179 public C generate(ExpVector i) { 180 if (i.isZERO()) { 181 return coFac.getONE(); 182 } 183 return coFac.getZERO(); 184 } 185 }); 186 ZERO = new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) { 187 188 189 @Override 190 public C generate(ExpVector i) { 191 return coFac.getZERO(); 192 } 193 }); 194 } 195 196 197 /** 198 * Fixed point construction. 199 * @param map a mapping of power series. 200 * @return fix point wrt map. 201 */ 202 // Cannot be a static method because a power series ring is required. 203 public MultiVarPowerSeries<C> fixPoint(MultiVarPowerSeriesMap<C> map) { 204 MultiVarPowerSeries<C> ps1 = new MultiVarPowerSeries<C>(this); 205 MultiVarPowerSeries<C> ps2 = map.map(ps1); 206 ps1.lazyCoeffs = ps2.lazyCoeffs; 207 return ps2; 208 } 209 210 211 /** 212 * To String. 213 * @return string representation of this. 214 */ 215 @Override 216 public String toString() { 217 StringBuffer sb = new StringBuffer(); 218 String scf = coFac.getClass().getSimpleName(); 219 sb.append(scf + "((" + varsToString() + "))"); 220 return sb.toString(); 221 } 222 223 224 /** 225 * Get a String representation of the variable names. 226 * @return names separated by commas. 227 */ 228 public String varsToString() { 229 if (vars == null) { 230 return "#" + nvar; 231 } 232 return ExpVector.varsToString(vars); 233 //return Arrays.toString(vars); 234 } 235 236 237 /** 238 * Get the variable names. 239 * @return names. 240 */ 241 public String[] getVars() { 242 return Arrays.copyOf(vars,vars.length); // > Java-5 243 } 244 245 246 /** 247 * Get a scripting compatible string representation. 248 * @return script compatible representation for this ElemFactory. 249 * @see edu.jas.structure.ElemFactory#toScript() 250 */ 251 @Override 252 public String toScript() { 253 // Python case 254 StringBuffer s = new StringBuffer("MPS("); 255 String f = null; 256 try { 257 f = ((RingElem<C>) coFac).toScriptFactory(); // sic 258 } catch (Exception e) { 259 f = coFac.toScript(); 260 } 261 s.append(f + ",\"" + varsToString() + "\"," + truncate + ")"); 262 return s.toString(); 263 } 264 265 266 /** 267 * Comparison with any other object. 268 * @see java.lang.Object#equals(java.lang.Object) 269 */ 270 @Override 271 @SuppressWarnings("unchecked") 272 public boolean equals(Object B) { 273 MultiVarPowerSeriesRing<C> a = null; 274 try { 275 a = (MultiVarPowerSeriesRing<C>) B; 276 } catch (ClassCastException ignored) { 277 } 278 if (a == null) { 279 return false; 280 } 281 if (!coFac.equals(a.coFac)) { 282 return false; 283 } 284 if (Arrays.deepEquals(vars, a.vars)) { 285 return true; 286 } 287 return false; 288 } 289 290 291 /** 292 * Hash code for this . 293 * @see java.lang.Object#hashCode() 294 */ 295 @Override 296 public int hashCode() { 297 int h = coFac.hashCode(); 298 h = h << 7; 299 h += (Arrays.hashCode(vars) << 17); 300 h += truncate; 301 return h; 302 } 303 304 305 /** 306 * Get the zero element. 307 * @return 0 as MultiVarPowerSeries<C>. 308 */ 309 public MultiVarPowerSeries<C> getZERO() { 310 return ZERO; 311 } 312 313 314 /** 315 * Get the one element. 316 * @return 1 as MultiVarPowerSeries<C>. 317 */ 318 public MultiVarPowerSeries<C> getONE() { 319 return ONE; 320 } 321 322 323 /** 324 * Get a list of the generating elements. 325 * @return list of generators for the algebraic structure. 326 * @see edu.jas.structure.ElemFactory#generators() 327 */ 328 public List<MultiVarPowerSeries<C>> generators() { 329 List<C> rgens = coFac.generators(); 330 List<MultiVarPowerSeries<C>> gens = new ArrayList<MultiVarPowerSeries<C>>(rgens.size()); 331 for (final C cg : rgens) { 332 MultiVarPowerSeries<C> g = new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) { 333 334 335 @Override 336 public C generate(ExpVector i) { 337 if (i.isZERO()) { 338 return cg; 339 } 340 return coFac.getZERO(); 341 } 342 }); 343 gens.add(g); 344 } 345 for (int i = 0; i < nvar; i++) { 346 gens.add(ONE.shift(1, nvar - 1 - i)); 347 } 348 return gens; 349 } 350 351 352 /** 353 * Is this structure finite or infinite. 354 * @return true if this structure is finite, else false. 355 * @see edu.jas.structure.ElemFactory#isFinite() 356 */ 357 public boolean isFinite() { 358 return false; 359 } 360 361 362 /** 363 * Truncate. 364 * @return truncate index of power series. 365 */ 366 public int truncate() { 367 return truncate; 368 } 369 370 371 /** 372 * Set truncate. 373 * @param t new truncate index. 374 * @return old truncate index of power series. 375 */ 376 public int setTruncate(int t) { 377 if (t < 0) { 378 throw new IllegalArgumentException("negative truncate not allowed"); 379 } 380 int ot = truncate; 381 truncate = t; 382 ONE.setTruncate(t); 383 ZERO.setTruncate(t); 384 return ot; 385 } 386 387 388 /** 389 * Get the power series of the exponential function. 390 * @param r variable for the direction. 391 * @return exp(x_r) as MultiVarPowerSeries<C>. 392 */ 393 public MultiVarPowerSeries<C> getEXP(final int r) { 394 return fixPoint(new MultiVarPowerSeriesMap<C>() { 395 396 397 public MultiVarPowerSeries<C> map(MultiVarPowerSeries<C> e) { 398 return e.integrate(coFac.getONE(), r); 399 } 400 }); 401 } 402 403 404 /** 405 * Get the power series of the sinus function. 406 * @param r variable for the direction. 407 * @return sin(x_r) as MultiVarPowerSeries<C>. 408 */ 409 public MultiVarPowerSeries<C> getSIN(final int r) { 410 return fixPoint(new MultiVarPowerSeriesMap<C>() { 411 412 413 public MultiVarPowerSeries<C> map(MultiVarPowerSeries<C> s) { 414 return s.negate().integrate(coFac.getONE(), r).integrate(coFac.getZERO(), r); 415 } 416 }); 417 } 418 419 420 /** 421 * Get the power series of the cosinus function. 422 * @param r variable for the direction. 423 * @return cos(x_r) as MultiVarPowerSeries<C>. 424 */ 425 public MultiVarPowerSeries<C> getCOS(final int r) { 426 return fixPoint(new MultiVarPowerSeriesMap<C>() { 427 428 429 public MultiVarPowerSeries<C> map(MultiVarPowerSeries<C> c) { 430 return c.negate().integrate(coFac.getZERO(), r).integrate(coFac.getONE(), r); 431 } 432 }); 433 } 434 435 436 /** 437 * Get the power series of the tangens function. 438 * @param r variable for the direction. 439 * @return tan(x_r) as MultiVarPowerSeries<C>. 440 */ 441 public MultiVarPowerSeries<C> getTAN(final int r) { 442 return fixPoint(new MultiVarPowerSeriesMap<C>() { 443 444 445 public MultiVarPowerSeries<C> map(MultiVarPowerSeries<C> t) { 446 return t.multiply(t).sum(getONE()).integrate(coFac.getZERO(), r); 447 } 448 }); 449 } 450 451 452 /** 453 * Solve an partial differential equation. y_r' = f(y_r) with y_r(0) = c. 454 * @param f a MultiVarPowerSeries<C>. 455 * @param c integration constant. 456 * @param r variable for the direction. 457 * @return f.integrate(c). 458 */ 459 public MultiVarPowerSeries<C> solvePDE(MultiVarPowerSeries<C> f, C c, int r) { 460 return f.integrate(c, r); 461 } 462 463 464 /** 465 * Query if this ring is commuative. 466 * @return true, if this ring is commutative, else false. 467 */ 468 public boolean isCommutative() { 469 return coFac.isCommutative(); 470 } 471 472 473 /** 474 * Query if this ring is associative. 475 * @return true if this ring is associative, else false. 476 */ 477 public boolean isAssociative() { 478 return coFac.isAssociative(); 479 } 480 481 482 /** 483 * Query if this ring is a field. 484 * @return false. 485 */ 486 public boolean isField() { 487 return false; 488 } 489 490 491 /** 492 * Characteristic of this ring. 493 * @return characteristic of this ring. 494 */ 495 public java.math.BigInteger characteristic() { 496 return coFac.characteristic(); 497 } 498 499 500 /** 501 * Get a (constant) MultiVarPowerSeries<C> from a long value. 502 * @param a long. 503 * @return a MultiVarPowerSeries<C>. 504 */ 505 public MultiVarPowerSeries<C> fromInteger(final long a) { 506 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) { 507 508 509 @Override 510 public C generate(ExpVector i) { 511 if (i.isZERO()) { 512 return coFac.fromInteger(a); 513 } 514 return coFac.getZERO(); 515 } 516 }); 517 } 518 519 520 /** 521 * Get a (constant) MultiVarPowerSeries<C> from a 522 * java.math.BigInteger. 523 * @param a BigInteger. 524 * @return a MultiVarPowerSeries<C>. 525 */ 526 public MultiVarPowerSeries<C> fromInteger(final java.math.BigInteger a) { 527 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) { 528 529 530 @Override 531 public C generate(ExpVector i) { 532 if (i.isZERO()) { 533 return coFac.fromInteger(a); 534 } 535 return coFac.getZERO(); 536 } 537 }); 538 } 539 540 541 /** 542 * Get the corresponding GenPolynomialRing<C>. 543 * @return GenPolynomialRing<C>. 544 */ 545 public GenPolynomialRing<C> polyRing() { 546 return new GenPolynomialRing<C>(coFac, nvar, vars); 547 } 548 549 550 /** 551 * Get a MultiVarPowerSeries<C> from a GenPolynomial<C>. 552 * @param a GenPolynomial<C>. 553 * @return a MultiVarPowerSeries<C>. 554 */ 555 public MultiVarPowerSeries<C> fromPolynomial(GenPolynomial<C> a) { 556 if (a == null || a.isZERO()) { 557 return ZERO; 558 } 559 if (a.isONE()) { 560 return ONE; 561 } 562 GenPolynomialRing<C> pfac = polyRing(); 563 HashMap<Long, GenPolynomial<C>> cache = new HashMap<Long, GenPolynomial<C>>(); 564 int mt = 0; 565 for (Monomial<C> m : a) { 566 ExpVector e = m.exponent(); 567 long t = e.totalDeg(); 568 mt = Math.max(mt, (int) t); 569 GenPolynomial<C> p = cache.get(t); 570 if (p == null) { 571 p = pfac.getZERO().copy(); 572 cache.put(t, p); 573 } 574 p.doPutToMap(e, m.coefficient()); 575 } 576 mt++; 577 if (mt > truncate()) { 578 setTruncate(mt); 579 } 580 BitSet check = new BitSet(); 581 for (int i = 0; i <= truncate(); i++) { 582 check.set(i); 583 if (cache.get((long) i) == null) { 584 GenPolynomial<C> p = pfac.getZERO().copy(); 585 cache.put((long) i, p); 586 //System.out.println("p zero for deg i = " + i); 587 } 588 } 589 590 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(pfac, cache, check) { 591 592 593 @Override 594 public C generate(ExpVector e) { 595 // cached coefficients returned by get 596 return coFac.getZERO(); 597 } 598 }); 599 } 600 601 602 /** 603 * Get a list of MultiVarPowerSeries<C> from a list of 604 * GenPolynomial<C>. 605 * @param A list of GenPolynomial<C>. 606 * @return a list of MultiVarPowerSeries<C>. 607 */ 608 public List<MultiVarPowerSeries<C>> fromPolynomial(List<GenPolynomial<C>> A) { 609 return ListUtil.<GenPolynomial<C>, MultiVarPowerSeries<C>> map(A, 610 new UnaryFunctor<GenPolynomial<C>, MultiVarPowerSeries<C>>() { 611 612 613 public MultiVarPowerSeries<C> eval(GenPolynomial<C> c) { 614 return fromPolynomial(c); 615 } 616 }); 617 } 618 619 620 /** 621 * Get a MultiVarPowerSeries<C> from a univariate power series. 622 * @param ps UnivPowerSeries<C>. 623 * @param r variable for the direction. 624 * @return a MultiVarPowerSeries<C>. 625 */ 626 public MultiVarPowerSeries<C> fromPowerSeries(final UnivPowerSeries<C> ps, final int r) { 627 if (ps == null) { 628 return ZERO; 629 } 630 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) { 631 632 633 @Override 634 public C generate(ExpVector i) { 635 if (i.isZERO()) { 636 return ps.coefficient(0); 637 } 638 int[] dep = i.dependencyOnVariables(); 639 if (dep.length != 1) { 640 return coFac.getZERO(); 641 } 642 if (dep[0] != r) { 643 return coFac.getZERO(); 644 } 645 int j = (int) i.getVal(r); 646 if (j > 0) { 647 return ps.coefficient(j); 648 } 649 return coFac.getZERO(); 650 } 651 }); 652 } 653 654 655 /** 656 * Generate a random power series with k = 5, d = 0.7. 657 * @return a random power series. 658 */ 659 public MultiVarPowerSeries<C> random() { 660 return random(5, 0.7f, random); 661 } 662 663 664 /** 665 * Generate a random power series with d = 0.7. 666 * @param k bit-size of random coefficients. 667 * @return a random power series. 668 */ 669 public MultiVarPowerSeries<C> random(int k) { 670 return random(k, 0.7f, random); 671 } 672 673 674 /** 675 * Generate a random power series with d = 0.7. 676 * @param k bit-size of random coefficients. 677 * @param rnd is a source for random bits. 678 * @return a random power series. 679 */ 680 public MultiVarPowerSeries<C> random(int k, Random rnd) { 681 return random(k, 0.7f, rnd); 682 } 683 684 685 /** 686 * Generate a random power series. 687 * @param k bit-size of random coefficients. 688 * @param d density of non-zero coefficients. 689 * @return a random power series. 690 */ 691 public MultiVarPowerSeries<C> random(int k, float d) { 692 return random(k, d, random); 693 } 694 695 696 /** 697 * Generate a random power series. 698 * @param k bit-size of random coefficients. 699 * @param d density of non-zero coefficients. 700 * @param rnd is a source for random bits. 701 * @return a random power series. 702 */ 703 public MultiVarPowerSeries<C> random(final int k, final float d, final Random rnd) { 704 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) { 705 706 707 @Override 708 public C generate(ExpVector i) { 709 // cached coefficients returned by get 710 C c; 711 float f = rnd.nextFloat(); 712 if (f < d) { 713 c = coFac.random(k, rnd); 714 } else { 715 c = coFac.getZERO(); 716 } 717 return c; 718 } 719 }); 720 } 721 722 723 /** 724 * Copy power series. 725 * @param c a power series. 726 * @return a copy of c. 727 */ 728 public MultiVarPowerSeries<C> copy(MultiVarPowerSeries<C> c) { 729 return new MultiVarPowerSeries<C>(this, c.lazyCoeffs); 730 } 731 732 733 /** 734 * Parse a power series. <b>Note:</b> not implemented. 735 * @param s String. 736 * @return power series from s. 737 */ 738 public MultiVarPowerSeries<C> parse(String s) { 739 throw new UnsupportedOperationException("parse for power series not implemented"); 740 } 741 742 743 /** 744 * Parse a power series. <b>Note:</b> not implemented. 745 * @param r Reader. 746 * @return next power series from r. 747 */ 748 public MultiVarPowerSeries<C> parse(Reader r) { 749 throw new UnsupportedOperationException("parse for power series not implemented"); 750 } 751 752 753 /** 754 * Taylor power series. 755 * @param f function. 756 * @param a expansion point. 757 * @return Taylor series of f. 758 */ 759 public MultiVarPowerSeries<C> seriesOfTaylor(final TaylorFunction<C> f, final List<C> a) { 760 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) { 761 762 763 TaylorFunction<C> der = f; 764 765 766 // Map<ExpVextor,TaylorFunction<C>> pderCache = ... 767 final List<C> v = a; 768 769 770 @Override 771 public C generate(ExpVector i) { 772 C c; 773 int s = i.signum(); 774 if (s == 0) { 775 c = der.evaluate(v); 776 return c; 777 } 778 TaylorFunction<C> pder = der.deriviative(i); 779 if (pder.isZERO()) { 780 return coFac.getZERO(); 781 } 782 c = pder.evaluate(v); 783 if (c.isZERO()) { 784 return c; 785 } 786 long f = pder.getFacul(); 787 c = c.divide(coFac.fromInteger(f)); 788 return c; 789 } 790 }); 791 } 792 793}