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&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().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&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    }