001 /*
002 * $Id: MultiVarPowerSeriesRing.java 3349 2010-10-15 20:54:27Z kredel $
003 */
004
005 package edu.jas.ps;
006
007
008 import java.io.Reader;
009 import java.util.ArrayList;
010 import java.util.Arrays;
011 import java.util.BitSet;
012 import java.util.HashMap;
013 import java.util.List;
014 import java.util.Random;
015
016 import edu.jas.kern.PrettyPrint;
017 import edu.jas.poly.ExpVector;
018 import edu.jas.poly.GenPolynomial;
019 import edu.jas.poly.GenPolynomialRing;
020 import edu.jas.poly.Monomial;
021 import edu.jas.structure.RingElem;
022 import edu.jas.structure.RingFactory;
023 import edu.jas.structure.UnaryFunctor;
024 import 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
034 public 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 this.vars = names;
160 if (vars == null && PrettyPrint.isTrue()) {
161 vars = GenPolynomialRing.newVars("x", nvar);
162 } else {
163 if (vars.length != nvar) {
164 throw new IllegalArgumentException("incompatible variable size " + vars.length + ", " + nvar);
165 }
166 GenPolynomialRing.addVars(vars);
167 }
168 EVZERO = ExpVector.create(nvar);
169 ONE = new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
170
171
172 @Override
173 public C generate(ExpVector i) {
174 if (i.isZERO()) {
175 return coFac.getONE();
176 }
177 return coFac.getZERO();
178 }
179 });
180 ZERO = new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
181
182
183 @Override
184 public C generate(ExpVector i) {
185 return coFac.getZERO();
186 }
187 });
188 }
189
190
191 /**
192 * Fixed point construction.
193 * @param map a mapping of power series.
194 * @return fix point wrt map.
195 */
196 // Cannot be a static method because a power series ring is required.
197 public MultiVarPowerSeries<C> fixPoint(MultiVarPowerSeriesMap<C> map) {
198 MultiVarPowerSeries<C> ps1 = new MultiVarPowerSeries<C>(this);
199 MultiVarPowerSeries<C> ps2 = map.map(ps1);
200 ps1.lazyCoeffs = ps2.lazyCoeffs;
201 return ps2;
202 }
203
204
205 /**
206 * To String.
207 * @return string representation of this.
208 */
209 @Override
210 public String toString() {
211 StringBuffer sb = new StringBuffer();
212 String scf = coFac.getClass().getSimpleName();
213 sb.append(scf + "((" + varsToString() + "))");
214 return sb.toString();
215 }
216
217
218 /**
219 * Get a String representation of the variable names.
220 * @return names seperated by commas.
221 */
222 public String varsToString() {
223 String s = "";
224 if (vars == null) {
225 return s + "#" + nvar;
226 }
227 for (int i = 0; i < vars.length; i++) {
228 if (i != 0) {
229 s += ", ";
230 }
231 s += vars[i];
232 }
233 return s;
234 }
235
236
237 /**
238 * Get a variable names.
239 * @return names.
240 */
241 public String[] getVars() {
242 return vars;
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 //JAVA6only: @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 if (!(B instanceof MultiVarPowerSeriesRing)) {
274 return false;
275 }
276 MultiVarPowerSeriesRing<C> a = null;
277 try {
278 a = (MultiVarPowerSeriesRing<C>) B;
279 } catch (ClassCastException ignored) {
280 }
281 if (Arrays.equals(vars, a.vars)) {
282 return true;
283 }
284 return false;
285 }
286
287
288 /**
289 * Hash code for this .
290 * @see java.lang.Object#hashCode()
291 */
292 @Override
293 public int hashCode() {
294 int h = 0;
295 h = (Arrays.hashCode(vars) << 23);
296 h += truncate;
297 return h;
298 }
299
300
301 /**
302 * Get the zero element.
303 * @return 0 as MultiVarPowerSeries<C>.
304 */
305 public MultiVarPowerSeries<C> getZERO() {
306 return ZERO;
307 }
308
309
310 /**
311 * Get the one element.
312 * @return 1 as MultiVarPowerSeries<C>.
313 */
314 public MultiVarPowerSeries<C> getONE() {
315 return ONE;
316 }
317
318
319 /**
320 * Get a list of the generating elements.
321 * @return list of generators for the algebraic structure.
322 * @see edu.jas.structure.ElemFactory#generators()
323 */
324 public List<MultiVarPowerSeries<C>> generators() {
325 List<C> rgens = coFac.generators();
326 List<MultiVarPowerSeries<C>> gens = new ArrayList<MultiVarPowerSeries<C>>(rgens.size());
327 for (final C cg : rgens) {
328 MultiVarPowerSeries<C> g = new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
329
330
331 @Override
332 public C generate(ExpVector i) {
333 if (i.isZERO()) {
334 return cg;
335 }
336 return coFac.getZERO();
337 }
338 });
339 gens.add(g);
340 }
341 for (int i = 0; i < nvar; i++) {
342 gens.add(ONE.shift(1, nvar - 1 - i));
343 }
344 return gens;
345 }
346
347
348 /**
349 * Is this structure finite or infinite.
350 * @return true if this structure is finite, else false.
351 * @see edu.jas.structure.ElemFactory#isFinite()
352 */
353 public boolean isFinite() {
354 return false;
355 }
356
357
358 /**
359 * Truncate.
360 * @return truncate index of power series.
361 */
362 public int truncate() {
363 return truncate;
364 }
365
366
367 /**
368 * Set truncate.
369 * @param t new truncate index.
370 * @return old truncate index of power series.
371 */
372 public int setTruncate(int t) {
373 if (t < 0) {
374 throw new IllegalArgumentException("negative truncate not allowed");
375 }
376 int ot = truncate;
377 truncate = t;
378 ONE.setTruncate(t);
379 ZERO.setTruncate(t);
380 return ot;
381 }
382
383
384 /**
385 * Get the power series of the exponential function.
386 * @param r variable for the direction.
387 * @return exp(x_r) as MultiVarPowerSeries<C>.
388 */
389 public MultiVarPowerSeries<C> getEXP(final int r) {
390 return fixPoint(new MultiVarPowerSeriesMap<C>() {
391
392
393 public MultiVarPowerSeries<C> map(MultiVarPowerSeries<C> e) {
394 return e.integrate(coFac.getONE(), r);
395 }
396 });
397 }
398
399
400 /**
401 * Get the power series of the sinus function.
402 * @param r variable for the direction.
403 * @return sin(x_r) as MultiVarPowerSeries<C>.
404 */
405 public MultiVarPowerSeries<C> getSIN(final int r) {
406 return fixPoint(new MultiVarPowerSeriesMap<C>() {
407
408
409 public MultiVarPowerSeries<C> map(MultiVarPowerSeries<C> s) {
410 return s.negate().integrate(coFac.getONE(), r).integrate(coFac.getZERO(), r);
411 }
412 });
413 }
414
415
416 /**
417 * Get the power series of the cosinus function.
418 * @param r variable for the direction.
419 * @return cos(x_r) as MultiVarPowerSeries<C>.
420 */
421 public MultiVarPowerSeries<C> getCOS(final int r) {
422 return fixPoint(new MultiVarPowerSeriesMap<C>() {
423
424
425 public MultiVarPowerSeries<C> map(MultiVarPowerSeries<C> c) {
426 return c.negate().integrate(coFac.getZERO(), r).integrate(coFac.getONE(), r);
427 }
428 });
429 }
430
431
432 /**
433 * Get the power series of the tangens function.
434 * @param r variable for the direction.
435 * @return tan(x_r) as MultiVarPowerSeries<C>.
436 */
437 public MultiVarPowerSeries<C> getTAN(final int r) {
438 return fixPoint(new MultiVarPowerSeriesMap<C>() {
439
440
441 public MultiVarPowerSeries<C> map(MultiVarPowerSeries<C> t) {
442 return t.multiply(t).sum(getONE()).integrate(coFac.getZERO(), r);
443 }
444 });
445 }
446
447
448 /**
449 * Solve an partial differential equation. y_r' = f(y_r) with y_r(0) = c.
450 * @param f a MultiVarPowerSeries<C>.
451 * @param c integration constant.
452 * @param r variable for the direction.
453 * @return f.integrate(c).
454 */
455 public MultiVarPowerSeries<C> solvePDE(MultiVarPowerSeries<C> f, C c, int r) {
456 return f.integrate(c, r);
457 }
458
459
460 /**
461 * Query if this ring is commuative.
462 * @return true, if this ring is commutative, else false.
463 */
464 public boolean isCommutative() {
465 return coFac.isCommutative();
466 }
467
468
469 /**
470 * Query if this ring is associative.
471 * @return true if this ring is associative, else false.
472 */
473 public boolean isAssociative() {
474 return coFac.isAssociative();
475 }
476
477
478 /**
479 * Query if this ring is a field.
480 * @return false.
481 */
482 public boolean isField() {
483 return false;
484 }
485
486
487 /**
488 * Characteristic of this ring.
489 * @return characteristic of this ring.
490 */
491 public java.math.BigInteger characteristic() {
492 return coFac.characteristic();
493 }
494
495
496 /**
497 * Get a (constant) MultiVarPowerSeries<C> from a long value.
498 * @param a long.
499 * @return a MultiVarPowerSeries<C>.
500 */
501 public MultiVarPowerSeries<C> fromInteger(final long a) {
502 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
503
504
505 @Override
506 public C generate(ExpVector i) {
507 if (i.isZERO()) {
508 return coFac.fromInteger(a);
509 }
510 return coFac.getZERO();
511 }
512 });
513 }
514
515
516 /**
517 * Get a (constant) MultiVarPowerSeries<C> from a
518 * java.math.BigInteger.
519 * @param a BigInteger.
520 * @return a MultiVarPowerSeries<C>.
521 */
522 public MultiVarPowerSeries<C> fromInteger(final java.math.BigInteger a) {
523 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
524
525
526 @Override
527 public C generate(ExpVector i) {
528 if (i.isZERO()) {
529 return coFac.fromInteger(a);
530 }
531 return coFac.getZERO();
532 }
533 });
534 }
535
536
537 /**
538 * Get the corresponding GenPolynomialRing<C>.
539 * @return GenPolynomialRing<C>.
540 */
541 public GenPolynomialRing<C> polyRing() {
542 return new GenPolynomialRing<C>(coFac, nvar, vars);
543 }
544
545
546 /**
547 * Get a MultiVarPowerSeries<C> from a GenPolynomial<C>.
548 * @param a GenPolynomial<C>.
549 * @return a MultiVarPowerSeries<C>.
550 */
551 public MultiVarPowerSeries<C> fromPolynomial(GenPolynomial<C> a) {
552 if (a == null || a.isZERO()) {
553 return ZERO;
554 }
555 if (a.isONE()) {
556 return ONE;
557 }
558 GenPolynomialRing<C> pfac = polyRing();
559 HashMap<Long, GenPolynomial<C>> cache = new HashMap<Long, GenPolynomial<C>>();
560 int mt = 0;
561 for (Monomial<C> m : a) {
562 ExpVector e = m.exponent();
563 long t = e.totalDeg();
564 mt = Math.max(mt, (int) t);
565 GenPolynomial<C> p = cache.get(t);
566 if (p == null) {
567 p = pfac.getZERO().clone();
568 cache.put(t, p);
569 }
570 p.doPutToMap(e, m.coefficient());
571 }
572 mt++;
573 if (mt > truncate()) {
574 setTruncate(mt);
575 }
576 BitSet check = new BitSet();
577 for (int i = 0; i <= truncate(); i++) {
578 check.set(i);
579 if (cache.get((long) i) == null) {
580 GenPolynomial<C> p = pfac.getZERO().clone();
581 cache.put((long) i, p);
582 //System.out.println("p zero for deg i = " + i);
583 }
584 }
585
586 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(pfac, cache, check) {
587
588
589 @Override
590 public C generate(ExpVector e) {
591 // cached coefficients returned by get
592 return coFac.getZERO();
593 }
594 });
595 }
596
597
598 /**
599 * Get a list of MultiVarPowerSeries<C> from a list of
600 * GenPolynomial<C>.
601 * @param A list of GenPolynomial<C>.
602 * @return a list of MultiVarPowerSeries<C>.
603 */
604 public List<MultiVarPowerSeries<C>> fromPolynomial(List<GenPolynomial<C>> A) {
605 return ListUtil.<GenPolynomial<C>, MultiVarPowerSeries<C>> map(A,
606 new UnaryFunctor<GenPolynomial<C>, MultiVarPowerSeries<C>>() {
607
608
609 public MultiVarPowerSeries<C> eval(GenPolynomial<C> c) {
610 return fromPolynomial(c);
611 }
612 });
613 }
614
615
616 /**
617 * Get a MultiVarPowerSeries<C> from a univariate power series.
618 * @param ps UnivPowerSeries<C>.
619 * @param r variable for the direction.
620 * @return a MultiVarPowerSeries<C>.
621 */
622 public MultiVarPowerSeries<C> fromPowerSeries(final UnivPowerSeries<C> ps, final int r) {
623 if (ps == null) {
624 return ZERO;
625 }
626 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
627
628
629 @Override
630 public C generate(ExpVector i) {
631 if (i.isZERO()) {
632 return ps.coefficient(0);
633 }
634 int[] dep = i.dependencyOnVariables();
635 if (dep.length != 1) {
636 return coFac.getZERO();
637 }
638 if (dep[0] != r) {
639 return coFac.getZERO();
640 }
641 int j = (int) i.getVal(r);
642 if (j > 0) {
643 return ps.coefficient(j);
644 }
645 return coFac.getZERO();
646 }
647 });
648 }
649
650
651 /**
652 * Generate a random power series with k = 5, d = 0.7.
653 * @return a random power series.
654 */
655 public MultiVarPowerSeries<C> random() {
656 return random(5, 0.7f, random);
657 }
658
659
660 /**
661 * Generate a random power series with d = 0.7.
662 * @param k bit-size of random coefficients.
663 * @return a random power series.
664 */
665 public MultiVarPowerSeries<C> random(int k) {
666 return random(k, 0.7f, random);
667 }
668
669
670 /**
671 * Generate a random power series with d = 0.7.
672 * @param k bit-size of random coefficients.
673 * @param rnd is a source for random bits.
674 * @return a random power series.
675 */
676 public MultiVarPowerSeries<C> random(int k, Random rnd) {
677 return random(k, 0.7f, rnd);
678 }
679
680
681 /**
682 * Generate a random power series.
683 * @param k bit-size of random coefficients.
684 * @param d density of non-zero coefficients.
685 * @return a random power series.
686 */
687 public MultiVarPowerSeries<C> random(int k, float d) {
688 return random(k, d, random);
689 }
690
691
692 /**
693 * Generate a random power series.
694 * @param k bit-size of random coefficients.
695 * @param d density of non-zero coefficients.
696 * @param rnd is a source for random bits.
697 * @return a random power series.
698 */
699 public MultiVarPowerSeries<C> random(final int k, final float d, final Random rnd) {
700 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
701
702
703 @Override
704 public C generate(ExpVector i) {
705 // cached coefficients returned by get
706 C c;
707 float f = rnd.nextFloat();
708 if (f < d) {
709 c = coFac.random(k, rnd);
710 } else {
711 c = coFac.getZERO();
712 }
713 return c;
714 }
715 });
716 }
717
718
719 /**
720 * Copy power series.
721 * @param c a power series.
722 * @return a copy of c.
723 */
724 public MultiVarPowerSeries<C> copy(MultiVarPowerSeries<C> c) {
725 return new MultiVarPowerSeries<C>(this, c.lazyCoeffs);
726 }
727
728
729 /**
730 * Parse a power series. <b>Note:</b> not implemented.
731 * @param s String.
732 * @return power series from s.
733 */
734 public MultiVarPowerSeries<C> parse(String s) {
735 throw new UnsupportedOperationException("parse for power series not implemented");
736 }
737
738
739 /**
740 * Parse a power series. <b>Note:</b> not implemented.
741 * @param r Reader.
742 * @return next power series from r.
743 */
744 public MultiVarPowerSeries<C> parse(Reader r) {
745 throw new UnsupportedOperationException("parse for power series not implemented");
746 }
747
748
749 /**
750 * Taylor power series.
751 * @param f function.
752 * @param a expansion point.
753 * @return Taylor series of f.
754 */
755 public MultiVarPowerSeries<C> seriesOfTaylor(final TaylorFunction<C> f, final List<C> a) {
756 return new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
757
758
759 TaylorFunction<C> der = f;
760
761
762 // Map<ExpVextor,TaylorFunction<C>> pderCache = ...
763 final List<C> v = a;
764
765
766 @Override
767 public C generate(ExpVector i) {
768 C c;
769 int s = i.signum();
770 if (s == 0) {
771 c = der.evaluate(v);
772 return c;
773 }
774 TaylorFunction<C> pder = der.deriviative(i);
775 if ( pder.isZERO() ) {
776 return coFac.getZERO();
777 }
778 c = pder.evaluate(v);
779 if (c.isZERO()) {
780 return c;
781 }
782 long f = pder.getFacul();
783 c = c.divide(coFac.fromInteger(f));
784 return c;
785 }
786 });
787 }
788
789 }