Source code

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