Source code

001/*
002 * $Id: QLRSolvablePolynomial.java 5164 2015-03-26 23:34:06Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008// todo: move to edu.jas.poly
009
010
011import java.util.Map;
012import java.util.Set;
013import java.util.SortedMap;
014
015import org.apache.log4j.Logger;
016
017import edu.jas.structure.GcdRingElem;
018import edu.jas.structure.QuotPair;
019import edu.jas.structure.RingFactory;
020
021
022/**
023 * QLRSolvablePolynomial generic recursive solvable polynomials implementing
024 * RingElem. n-variate ordered solvable polynomials over solvable quotient,
025 * local and local-residue coefficients. Objects of this class are intended to
026 * be immutable. The implementation is based on TreeMap respectively SortedMap
027 * from exponents to coefficients by extension of GenPolynomial.
028 * @param <C> polynomial coefficient type
029 * @param <D> quotient coefficient type
030 * @author Heinz Kredel
031 */
032
033public class QLRSolvablePolynomial<C extends GcdRingElem<C> & QuotPair<GenPolynomial<D>>, D extends GcdRingElem<D>>
034                extends GenSolvablePolynomial<C> {
035
036
037    private static final Logger logger = Logger.getLogger(QLRSolvablePolynomial.class);
038
039
040    private final boolean debug = logger.isDebugEnabled();
041
042
043    /**
044     * The factory for the recursive solvable polynomial ring. Hides super.ring.
045     */
046    public final QLRSolvablePolynomialRing<C, D> ring;
047
048
049    /**
050     * Constructor for zero QLRSolvablePolynomial.
051     * @param r solvable polynomial ring factory.
052     */
053    public QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r) {
054        super(r);
055        ring = r;
056    }
057
058
059    /**
060     * Constructor for QLRSolvablePolynomial.
061     * @param r solvable polynomial ring factory.
062     * @param c coefficient polynomial.
063     * @param e exponent.
064     */
065    public QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r, C c, ExpVector e) {
066        this(r);
067        if (c != null && !c.isZERO()) {
068            val.put(e, c);
069        }
070    }
071
072
073    /**
074     * Constructor for QLRSolvablePolynomial.
075     * @param r solvable polynomial ring factory.
076     * @param c coefficient polynomial.
077     */
078    public QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r, C c) {
079        this(r, c, r.evzero);
080    }
081
082
083    /**
084     * Constructor for QLRSolvablePolynomial.
085     * @param r solvable polynomial ring factory.
086     * @param S solvable polynomial.
087     */
088    public QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r, GenSolvablePolynomial<C> S) {
089        this(r, S.getMap());
090    }
091
092
093    /**
094     * Constructor for QLRSolvablePolynomial.
095     * @param r solvable polynomial ring factory.
096     * @param v the SortedMap of some other (solvable) polynomial.
097     */
098    protected QLRSolvablePolynomial(QLRSolvablePolynomialRing<C, D> r, SortedMap<ExpVector, C> v) {
099        this(r);
100        val.putAll(v); // assume no zero coefficients
101    }
102
103
104    /**
105     * Get the corresponding element factory.
106     * @return factory for this Element.
107     * @see edu.jas.structure.Element#factory()
108     */
109    @Override
110    public QLRSolvablePolynomialRing<C, D> factory() {
111        return ring;
112    }
113
114
115    /**
116     * Clone this QLRSolvablePolynomial.
117     * @see java.lang.Object#clone()
118     */
119    @Override
120    public QLRSolvablePolynomial<C, D> copy() {
121        return new QLRSolvablePolynomial<C, D>(ring, this.val);
122    }
123
124
125    /**
126     * Comparison with any other object.
127     * @see java.lang.Object#equals(java.lang.Object)
128     */
129    @Override
130    public boolean equals(Object B) {
131        if (!(B instanceof QLRSolvablePolynomial)) {
132            return false;
133        }
134        return super.equals(B);
135    }
136
137
138    /**
139     * QLRSolvablePolynomial multiplication.
140     * @param Bp QLRSolvablePolynomial.
141     * @return this*Bp, where * denotes solvable multiplication.
142     */
143    // not @Override
144    public QLRSolvablePolynomial<C, D> multiply(QLRSolvablePolynomial<C, D> Bp) {
145        if (Bp == null || Bp.isZERO()) {
146            return ring.getZERO();
147        }
148        if (this.isZERO()) {
149            return this;
150        }
151        if (Bp.isONE()) {
152            return this;
153        }
154        if (this.isONE()) {
155            return Bp;
156        }
157        assert (ring.nvar == Bp.ring.nvar);
158        if (debug) {
159            logger.debug("ring = " + ring);
160        }
161        //System.out.println("this = " + this + ", Bp = " + Bp);
162        ExpVector Z = ring.evzero;
163        QLRSolvablePolynomial<C, D> Dp = ring.getZERO().copy();
164        QLRSolvablePolynomial<C, D> zero = ring.getZERO().copy();
165        C one = ring.getONECoefficient();
166
167        Map<ExpVector, C> A = val;
168        Map<ExpVector, C> B = Bp.val;
169        Set<Map.Entry<ExpVector, C>> Bk = B.entrySet();
170        for (Map.Entry<ExpVector, C> y : A.entrySet()) {
171            C a = y.getValue();
172            ExpVector e = y.getKey();
173            if (debug)
174                logger.info("e = " + e + ", a = " + a);
175            //int[] ep = e.dependencyOnVariables();
176            //int el1 = ring.nvar + 1;
177            //if (ep.length > 0) {
178            //    el1 = ep[0];
179            //}
180            //int el1s = ring.nvar + 1 - el1;
181            for (Map.Entry<ExpVector, C> x : Bk) {
182                C b = x.getValue();
183                ExpVector f = x.getKey();
184                if (debug)
185                    logger.info("f = " + f + ", b = " + b);
186                int[] fp = f.dependencyOnVariables();
187                int fl1 = 0;
188                if (fp.length > 0) {
189                    fl1 = fp[fp.length - 1];
190                }
191                int fl1s = ring.nvar + 1 - fl1;
192                // polynomial with coefficient multiplication 
193                QLRSolvablePolynomial<C, D> Cps = ring.getZERO().copy();
194                //QLRSolvablePolynomial<C, D> Cs;
195                QLRSolvablePolynomial<C, D> qp;
196                if (ring.polCoeff.isCommutative() || b.isConstant() || e.isZERO()) { // symmetric
197                    Cps = new QLRSolvablePolynomial<C, D>(ring, b, e);
198                    if (debug)
199                        logger.info("symmetric coeff: b = " + b + ", e = " + e);
200                } else { // unsymmetric
201                    if (debug)
202                        logger.info("unsymmetric coeff: b = " + b + ", e = " + e);
203                    // compute e * b as ( e * 1/b.den ) * b.num
204                    if (b.denominator().isONE()) { // recursion base
205                        // recursive polynomial coefficient multiplication : e * b.num
206                        RecSolvablePolynomial<D> rsp1 = new RecSolvablePolynomial<D>(ring.polCoeff, e);
207                        RecSolvablePolynomial<D> rsp2 = new RecSolvablePolynomial<D>(ring.polCoeff,
208                                        b.numerator());
209                        RecSolvablePolynomial<D> rsp3 = rsp1.multiply(rsp2);
210                        QLRSolvablePolynomial<C, D> rsp = ring.fromPolyCoefficients(rsp3);
211                        Cps = rsp;
212                    } else { // b.denominator() != 1
213                        if (debug)
214                            logger.info("coeff-num: Cps = " + Cps + ", num = " + b.numerator() + ", den = "
215                                            + b.denominator());
216                        RingFactory<C> bfq = (RingFactory<C>) b.factory();
217                        Cps = new QLRSolvablePolynomial<C, D>(ring, bfq.getONE(), e);
218
219                        // coefficient multiplication with 1/den: 
220                        QLRSolvablePolynomial<C, D> qv = Cps;
221                        //C qden = new C(b.denominator().factory(), b.denominator()); // den/1
222                        C qden = ring.qpfac.create(b.denominator()); // den/1
223                        //System.out.println("qv = " + qv + ", den = " + den);
224                        // recursion with den==1:
225                        QLRSolvablePolynomial<C, D> v = qv.multiply(qden);
226                        QLRSolvablePolynomial<C, D> vl = qv.multiplyLeft(qden);
227                        //System.out.println("v = " + v + ", vl = " + vl + ", qden = " + qden);
228                        QLRSolvablePolynomial<C, D> vr = (QLRSolvablePolynomial<C, D>) v.subtract(vl);
229                        //C qdeni = new C(b.factory(), b.factory().getONE().numerator(), b.denominator());
230                        C qdeni = ring.qpfac.create(ring.qpfac.pairFactory().getONE(), b.denominator()); // 1/den
231                        //System.out.println("vr = " + vr + ", qdeni = " + qdeni);
232                        // recursion with smaller head term:
233                        if (qv.leadingExpVector().equals(vr.leadingExpVector())) {
234                            throw new IllegalArgumentException("qr !> vr: qv = " + qv + ", vr = " + vr);
235                        }
236                        QLRSolvablePolynomial<C, D> rq = vr.multiply(qdeni);
237                        qp = (QLRSolvablePolynomial<C, D>) qv.subtract(rq);
238                        qp = qp.multiplyLeft(qdeni);
239                        //System.out.println("qp_i = " + qp);
240                        Cps = qp;
241
242                        if (!b.numerator().isONE()) {
243                            //C qnum = new C(b.denominator().factory(), b.numerator()); // num/1
244                            C qnum = ring.qpfac.create(b.numerator()); // num/1
245                            // recursion with den == 1:
246                            Cps = Cps.multiply(qnum);
247                        }
248                    }
249                } // end coeff
250                if (debug)
251                    logger.info("coeff-den: Cps = " + Cps);
252                // polynomial multiplication 
253                QLRSolvablePolynomial<C, D> Dps = ring.getZERO().copy();
254                QLRSolvablePolynomial<C, D> Ds = null;
255                QLRSolvablePolynomial<C, D> D1, D2;
256                if (ring.isCommutative() || Cps.isConstant() || f.isZERO()) { // symmetric
257                    if (debug)
258                        logger.info("symmetric poly: b = " + b + ", e = " + e);
259                    if (Cps.isConstant()) {
260                        ExpVector g = e.sum(f);
261                        Ds = new QLRSolvablePolynomial<C, D>(ring, Cps.leadingBaseCoefficient(), g); // symmetric!
262                    } else {
263                        Ds = shift(Cps, f); // symmetric
264                    }
265                } else { // eventually unsymmetric
266                    if (debug)
267                        logger.info("unsymmetric poly: Cps = " + Cps + ", f = " + f);
268                    for (Map.Entry<ExpVector, C> z : Cps.val.entrySet()) {
269                        // split g = g1 * g2, f = f1 * f2
270                        C c = z.getValue();
271                        ExpVector g = z.getKey();
272                        if (debug)
273                            logger.info("g = " + g + ", c = " + c);
274                        int[] gp = g.dependencyOnVariables();
275                        int gl1 = ring.nvar + 1;
276                        if (gp.length > 0) {
277                            gl1 = gp[0];
278                        }
279                        int gl1s = ring.nvar + 1 - gl1;
280                        if (gl1s <= fl1s) { // symmetric
281                            ExpVector h = g.sum(f);
282                            if (debug)
283                                logger.info("disjoint poly: g = " + g + ", f = " + f + ", h = " + h);
284                            Ds = (QLRSolvablePolynomial<C, D>) zero.sum(one, h); // symmetric!
285                        } else {
286                            ExpVector g1 = g.subst(gl1, 0);
287                            ExpVector g2 = Z.subst(gl1, g.getVal(gl1)); // bug el1, gl1
288                            ExpVector g4;
289                            ExpVector f1 = f.subst(fl1, 0);
290                            ExpVector f2 = Z.subst(fl1, f.getVal(fl1));
291                            if (debug) {
292                                logger.info("poly, g1 = " + g1 + ", f1 = " + f1 + ", Dps = " + Dps);
293                                logger.info("poly, g2 = " + g2 + ", f2 = " + f2);
294                            }
295                            TableRelation<C> rel = ring.table.lookup(g2, f2);
296                            if (debug)
297                                logger.info("poly, g  = " + g + ", f  = " + f + ", rel = " + rel);
298                            Ds = new QLRSolvablePolynomial<C, D>(ring, rel.p); //ring.copy(rel.p);
299                            if (rel.f != null) {
300                                D2 = new QLRSolvablePolynomial<C, D>(ring, one, rel.f);
301                                Ds = Ds.multiply(D2);
302                                if (rel.e == null) {
303                                    g4 = g2;
304                                } else {
305                                    g4 = g2.subtract(rel.e);
306                                }
307                                ring.table.update(g4, f2, Ds);
308                            }
309                            if (rel.e != null) {
310                                D1 = new QLRSolvablePolynomial<C, D>(ring, one, rel.e);
311                                Ds = D1.multiply(Ds);
312                                ring.table.update(g2, f2, Ds);
313                            }
314                            if (!f1.isZERO()) {
315                                D2 = new QLRSolvablePolynomial<C, D>(ring, one, f1);
316                                Ds = Ds.multiply(D2);
317                                //ring.table.update(?,f1,Ds)
318                            }
319                            if (!g1.isZERO()) {
320                                D1 = new QLRSolvablePolynomial<C, D>(ring, one, g1);
321                                Ds = D1.multiply(Ds);
322                                //ring.table.update(e1,?,Ds)
323                            }
324                        }
325                        Ds = Ds.multiplyLeft(c); // c * Ds
326                        //Dps = (QLRSolvablePolynomial<C, D>) Dps.sum(Ds);
327                        Dps.doAddTo(Ds);
328                    } // end Dps loop
329                    Ds = Dps;
330                }
331                Ds = Ds.multiplyLeft(a); // multiply(a,b); // non-symmetric 
332                if (debug)
333                    logger.debug("Ds = " + Ds);
334                //Dp = (QLRSolvablePolynomial<C, D>) Dp.sum(Ds);
335                Dp.doAddTo(Ds);
336            } // end B loop
337        } // end A loop
338          //System.out.println("this * Bp = " + Dp);
339        return Dp;
340    }
341
342
343    /**
344     * QLRSolvablePolynomial left and right multiplication. Product with two
345     * polynomials.
346     * @param S QLRSolvablePolynomial.
347     * @param T QLRSolvablePolynomial.
348     * @return S*this*T.
349     */
350    // not @Override
351    public QLRSolvablePolynomial<C, D> multiply(QLRSolvablePolynomial<C, D> S, QLRSolvablePolynomial<C, D> T) {
352        if (S.isZERO() || T.isZERO() || this.isZERO()) {
353            return ring.getZERO();
354        }
355        if (S.isONE()) {
356            return multiply(T);
357        }
358        if (T.isONE()) {
359            return S.multiply(this);
360        }
361        return S.multiply(this).multiply(T);
362    }
363
364
365    /**
366     * QLRSolvablePolynomial multiplication. Product with coefficient ring
367     * element.
368     * @param b solvable coefficient.
369     * @return this*b, where * is coefficient multiplication.
370     */
371    @Override
372    public QLRSolvablePolynomial<C, D> multiply(C b) {
373        QLRSolvablePolynomial<C, D> Cp = ring.getZERO().copy();
374        if (b == null || b.isZERO()) {
375            return Cp;
376        }
377        if (b.isONE()) {
378            return this;
379        }
380        Cp = new QLRSolvablePolynomial<C, D>(ring, b, ring.evzero);
381        return multiply(Cp);
382    }
383
384
385    /**
386     * QLRSolvablePolynomial left and right multiplication. Product with
387     * coefficient ring element.
388     * @param b coefficient polynomial.
389     * @param c coefficient polynomial.
390     * @return b*this*c, where * is coefficient multiplication.
391     */
392    @Override
393    public QLRSolvablePolynomial<C, D> multiply(C b, C c) {
394        QLRSolvablePolynomial<C, D> Cp = ring.getZERO().copy();
395        if (b == null || b.isZERO()) {
396            return Cp;
397        }
398        if (c == null || c.isZERO()) {
399            return Cp;
400        }
401        if (b.isONE() && c.isONE()) {
402            return this;
403        }
404        Cp = new QLRSolvablePolynomial<C, D>(ring, b, ring.evzero);
405        QLRSolvablePolynomial<C, D> Dp = new QLRSolvablePolynomial<C, D>(ring, c, ring.evzero);
406        return multiply(Cp, Dp);
407    }
408
409
410    /**
411     * QLRSolvablePolynomial multiplication. Product with exponent vector.
412     * @param e exponent.
413     * @return this * x<sup>e</sup>, where * denotes solvable multiplication.
414     */
415    @Override
416    public QLRSolvablePolynomial<C, D> multiply(ExpVector e) {
417        if (e == null || e.isZERO()) {
418            return this;
419        }
420        C b = ring.getONECoefficient();
421        return multiply(b, e);
422    }
423
424
425    /**
426     * QLRSolvablePolynomial left and right multiplication. Product with
427     * exponent vector.
428     * @param e exponent.
429     * @param f exponent.
430     * @return x<sup>e</sup> * this * x<sup>f</sup>, where * denotes solvable
431     *         multiplication.
432     */
433    @Override
434    public QLRSolvablePolynomial<C, D> multiply(ExpVector e, ExpVector f) {
435        if (e == null || e.isZERO()) {
436            return this;
437        }
438        if (f == null || f.isZERO()) {
439            return this;
440        }
441        C b = ring.getONECoefficient();
442        return multiply(b, e, b, f);
443    }
444
445
446    /**
447     * QLRSolvablePolynomial multiplication. Product with ring element and
448     * exponent vector.
449     * @param b coefficient polynomial.
450     * @param e exponent.
451     * @return this * b x<sup>e</sup>, where * denotes solvable multiplication.
452     */
453    @Override
454    public QLRSolvablePolynomial<C, D> multiply(C b, ExpVector e) {
455        if (b == null || b.isZERO()) {
456            return ring.getZERO();
457        }
458        if (b.isONE() && e.isZERO()) {
459            return this;
460        }
461        QLRSolvablePolynomial<C, D> Cp = new QLRSolvablePolynomial<C, D>(ring, b, e);
462        return multiply(Cp);
463    }
464
465
466    /**
467     * QLRSolvablePolynomial left and right multiplication. Product with ring
468     * element and exponent vector.
469     * @param b coefficient polynomial.
470     * @param e exponent.
471     * @param c coefficient polynomial.
472     * @param f exponent.
473     * @return b x<sup>e</sup> * this * c x<sup>f</sup>, where * denotes
474     *         solvable multiplication.
475     */
476    @Override
477    public QLRSolvablePolynomial<C, D> multiply(C b, ExpVector e, C c, ExpVector f) {
478        if (b == null || b.isZERO()) {
479            return ring.getZERO();
480        }
481        if (c == null || c.isZERO()) {
482            return ring.getZERO();
483        }
484        if (b.isONE() && e.isZERO() && c.isONE() && f.isZERO()) {
485            return this;
486        }
487        QLRSolvablePolynomial<C, D> Cp = new QLRSolvablePolynomial<C, D>(ring, b, e);
488        QLRSolvablePolynomial<C, D> Dp = new QLRSolvablePolynomial<C, D>(ring, c, f);
489        return multiply(Cp, Dp);
490    }
491
492
493    /**
494     * QLRSolvablePolynomial multiplication. Left product with ring element and
495     * exponent vector.
496     * @param b coefficient polynomial.
497     * @param e exponent.
498     * @return b x<sup>e</sup> * this, where * denotes solvable multiplication.
499     */
500    @Override
501    public QLRSolvablePolynomial<C, D> multiplyLeft(C b, ExpVector e) {
502        if (b == null || b.isZERO()) {
503            return ring.getZERO();
504        }
505        QLRSolvablePolynomial<C, D> Cp = new QLRSolvablePolynomial<C, D>(ring, b, e);
506        return Cp.multiply(this);
507    }
508
509
510    /**
511     * QLRSolvablePolynomial multiplication. Left product with exponent vector.
512     * @param e exponent.
513     * @return x<sup>e</sup> * this, where * denotes solvable multiplication.
514     */
515    @Override
516    public QLRSolvablePolynomial<C, D> multiplyLeft(ExpVector e) {
517        if (e == null || e.isZERO()) {
518            return this;
519        }
520        C b = ring.getONECoefficient();
521        QLRSolvablePolynomial<C, D> Cp = new QLRSolvablePolynomial<C, D>(ring, b, e);
522        return Cp.multiply(this);
523    }
524
525
526    /**
527     * QLRSolvablePolynomial multiplication. Left product with coefficient ring
528     * element.
529     * @param b coefficient polynomial.
530     * @return b*this, where * is coefficient multiplication.
531     */
532    @Override
533    public QLRSolvablePolynomial<C, D> multiplyLeft(C b) {
534        QLRSolvablePolynomial<C, D> Cp = ring.getZERO().copy();
535        if (b == null || b.isZERO()) {
536            return Cp;
537        }
538        Map<ExpVector, C> Cm = Cp.val; //getMap();
539        Map<ExpVector, C> Am = val;
540        C c;
541        for (Map.Entry<ExpVector, C> y : Am.entrySet()) {
542            ExpVector e = y.getKey();
543            C a = y.getValue();
544            c = b.multiply(a);
545            if (!c.isZERO()) {
546                Cm.put(e, c);
547            }
548        }
549        return Cp;
550    }
551
552
553    /**
554     * QLRSolvablePolynomial multiplication. Left product with 'monomial'.
555     * @param m 'monomial'.
556     * @return m * this, where * denotes solvable multiplication.
557     */
558    @Override
559    public QLRSolvablePolynomial<C, D> multiplyLeft(Map.Entry<ExpVector, C> m) {
560        if (m == null) {
561            return ring.getZERO();
562        }
563        return multiplyLeft(m.getValue(), m.getKey());
564    }
565
566
567    /**
568     * QLRSolvablePolynomial multiplication. Product with 'monomial'.
569     * @param m 'monomial'.
570     * @return this * m, where * denotes solvable multiplication.
571     */
572    @Override
573    public QLRSolvablePolynomial<C, D> multiply(Map.Entry<ExpVector, C> m) {
574        if (m == null) {
575            return ring.getZERO();
576        }
577        return multiply(m.getValue(), m.getKey());
578    }
579
580
581    /**
582     * QLRSolvablePolynomial multiplication with exponent vector. 
583     * @param B solvable polynomial.
584     * @param f exponent vector.
585     * @return B*f, where * is commutative multiplication.
586     */
587    protected QLRSolvablePolynomial<C, D> shift(QLRSolvablePolynomial<C, D> B, ExpVector f) {
588        QLRSolvablePolynomial<C, D> C = ring.getZERO().copy();
589        if (B == null || B.isZERO()) {
590            return C;
591        }
592        if (f == null || f.isZERO()) {
593            return B;
594        }
595        Map<ExpVector, C> Cm = C.val;
596        Map<ExpVector, C> Bm = B.val;
597        for (Map.Entry<ExpVector, C> y : Bm.entrySet()) {
598            ExpVector e = y.getKey();
599            C a = y.getValue();
600            ExpVector d = e.sum(f);
601            if (!a.isZERO()) {
602                Cm.put(d, a);
603            }
604        }
605        return C;
606    }
607
608}