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