Source code

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