Source code

001/*
002 * $Id: MultiVarPowerSeriesRing.java 4125 2012-08-19 19:05:22Z 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        vars = names;
160        if (vars == null) {
161            if (PrettyPrint.isTrue()) {
162                vars = GenPolynomialRing.newVars("x", nvar);
163            }
164        } else {
165            if (vars.length != nvar) {
166                throw new IllegalArgumentException("incompatible variable size " + vars.length + ", " + nvar);
167            }
168            GenPolynomialRing.addVars(vars);
169        }
170        EVZERO = ExpVector.create(nvar);
171        ONE = new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
172
173
174            @Override
175            public C generate(ExpVector i) {
176                if (i.isZERO()) {
177                    return coFac.getONE();
178                }
179                return coFac.getZERO();
180            }
181        });
182        ZERO = new MultiVarPowerSeries<C>(this, new MultiVarCoefficients<C>(this) {
183
184
185            @Override
186            public C generate(ExpVector i) {
187                return coFac.getZERO();
188            }
189        });
190    }
191
192
193    /**
194     * Fixed point construction.
195     * @param map a mapping of power series.
196     * @return fix point wrt map.
197     */
198    // Cannot be a static method because a power series ring is required.
199    public MultiVarPowerSeries<C> fixPoint(MultiVarPowerSeriesMap<C> map) {
200        MultiVarPowerSeries<C> ps1 = new MultiVarPowerSeries<C>(this);
201        MultiVarPowerSeries<C> ps2 = map.map(ps1);
202        ps1.lazyCoeffs = ps2.lazyCoeffs;
203        return ps2;
204    }
205
206
207    /**
208     * To String.
209     * @return string representation of this.
210     */
211    @Override
212    public String toString() {
213        StringBuffer sb = new StringBuffer();
214        String scf = coFac.getClass().getSimpleName();
215        sb.append(scf + "((" + varsToString() + "))");
216        return sb.toString();
217    }
218
219
220    /**
221     * Get a String representation of the variable names.
222     * @return names separated by commas.
223     */
224    public String varsToString() {
225        if (vars == null) {
226            return "#" + nvar;
227        }
228        return ExpVector.varsToString(vars);
229        //return Arrays.toString(vars);
230    }
231
232
233    /**
234     * Get the variable names.
235     * @return names.
236     */
237    public String[] getVars() {
238        return vars; // Java-5: Arrays.copyOf(vars,vars.length);
239    }
240
241
242    /**
243     * Get a scripting compatible string representation.
244     * @return script compatible representation for this ElemFactory.
245     * @see edu.jas.structure.ElemFactory#toScript()
246     */
247    //JAVA6only: @Override
248    public String toScript() {
249        // Python case
250        StringBuffer s = new StringBuffer("MPS(");
251        String f = null;
252        try {
253            f = ((RingElem<C>) coFac).toScriptFactory(); // sic
254        } catch (Exception e) {
255            f = coFac.toScript();
256        }
257        s.append(f + ",\"" + varsToString() + "\"," + truncate + ")");
258        return s.toString();
259    }
260
261
262    /**
263     * Comparison with any other object.
264     * @see java.lang.Object#equals(java.lang.Object)
265     */
266    @Override
267    @SuppressWarnings("unchecked")
268    public boolean equals(Object B) {
269        MultiVarPowerSeriesRing<C> a = null;
270        try {
271            a = (MultiVarPowerSeriesRing<C>) B;
272        } catch (ClassCastException ignored) {
273        }
274        if (a == null) {
275            return false;
276        }
277        if (!coFac.equals(a.coFac)) {
278            return false;
279        }
280        if (Arrays.equals(vars, a.vars)) {
281            return true;
282        }
283        return false;
284    }
285
286
287    /**
288     * Hash code for this .
289     * @see java.lang.Object#hashCode()
290     */
291    @Override
292    public int hashCode() {
293        int h = coFac.hashCode();
294        h = h << 7;
295        h += (Arrays.hashCode(vars) << 17);
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&lt;C&gt; from a long value.
498     * @param a long.
499     * @return a MultiVarPowerSeries&lt;C&gt;.
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&lt;C&gt; from a
518     * java.math.BigInteger.
519     * @param a BigInteger.
520     * @return a MultiVarPowerSeries&lt;C&gt;.
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&lt;C&gt;.
539     * @return GenPolynomialRing&lt;C&gt;.
540     */
541    public GenPolynomialRing<C> polyRing() {
542        return new GenPolynomialRing<C>(coFac, nvar, vars);
543    }
544
545
546    /**
547     * Get a MultiVarPowerSeries&lt;C&gt; from a GenPolynomial&lt;C&gt;.
548     * @param a GenPolynomial&lt;C&gt;.
549     * @return a MultiVarPowerSeries&lt;C&gt;.
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().copy();
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().copy();
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&lt;C&gt; from a list of
600     * GenPolynomial&lt;C&gt;.
601     * @param A list of GenPolynomial&lt;C&gt;.
602     * @return a list of MultiVarPowerSeries&lt;C&gt;.
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&lt;C&gt; from a univariate power series.
618     * @param ps UnivPowerSeries&lt;C&gt;.
619     * @param r variable for the direction.
620     * @return a MultiVarPowerSeries&lt;C&gt;.
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}