Source code

001/*
002 * $Id$
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.LogManager;
013import org.apache.logging.log4j.Logger;
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. Will be deprecated use
028 * QLRSolvablePolynomial.
029 * @param <C> coefficient type
030 * @author Heinz Kredel
031 */
032
033public class QuotSolvablePolynomial<C extends GcdRingElem<C>>
034                extends 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     * Hash code for this polynomial.
142     * @see java.lang.Object#hashCode()
143     */
144    @Override
145    public int hashCode() {
146        return super.hashCode();
147    }
148
149
150    /**
151     * QuotSolvablePolynomial multiplication.
152     * @param Bp QuotSolvablePolynomial.
153     * @return this*Bp, where * denotes solvable multiplication.
154     */
155    // not @Override
156    public QuotSolvablePolynomial<C> multiply(QuotSolvablePolynomial<C> Bp) {
157        if (Bp == null || Bp.isZERO()) {
158            return ring.getZERO();
159        }
160        if (this.isZERO()) {
161            return this;
162        }
163        if (Bp.isONE()) {
164            return this;
165        }
166        if (this.isONE()) {
167            return Bp;
168        }
169        assert (ring.nvar == Bp.ring.nvar);
170        logger.debug("ring = {}", ring);
171        //System.out.println("this = " + this + ", Bp = " + Bp);
172        ExpVector Z = ring.evzero;
173        QuotSolvablePolynomial<C> Dp = ring.getZERO().copy();
174        QuotSolvablePolynomial<C> zero = ring.getZERO().copy();
175        SolvableQuotient<C> one = ring.getONECoefficient();
176
177        //QuotSolvablePolynomial<C> C1 = null;
178        //QuotSolvablePolynomial<C> C2 = null;
179        Map<ExpVector, SolvableQuotient<C>> A = val;
180        Map<ExpVector, SolvableQuotient<C>> B = Bp.val;
181        Set<Map.Entry<ExpVector, SolvableQuotient<C>>> Bk = B.entrySet();
182        for (Map.Entry<ExpVector, SolvableQuotient<C>> y : A.entrySet()) {
183            SolvableQuotient<C> a = y.getValue();
184            ExpVector e = y.getKey();
185            if (debug)
186                logger.info("e = {}, a = {}", e, a);
187            // int[] ep = e.dependencyOnVariables();
188            // int el1 = ring.nvar + 1;
189            // if (ep.length > 0) {
190            //     el1 = ep[0];
191            // }
192            // int el1s = ring.nvar + 1 - el1;
193            for (Map.Entry<ExpVector, SolvableQuotient<C>> x : Bk) {
194                SolvableQuotient<C> b = x.getValue();
195                ExpVector f = x.getKey();
196                if (debug)
197                    logger.info("f = {}, b = {}", f, b);
198                int[] fp = f.dependencyOnVariables();
199                int fl1 = 0;
200                if (fp.length > 0) {
201                    fl1 = fp[fp.length - 1];
202                }
203                int fl1s = ring.nvar + 1 - fl1;
204                // polynomial with coefficient multiplication 
205                QuotSolvablePolynomial<C> Cps = ring.getZERO().copy();
206                //QuotSolvablePolynomial<C> Cs;
207                QuotSolvablePolynomial<C> qp;
208                if (ring.polCoeff.coeffTable.isEmpty() || b.isConstant() || e.isZERO()) { // symmetric
209                    Cps = new QuotSolvablePolynomial<C>(ring, b, e);
210                    if (debug)
211                        logger.info("symmetric coeff: b = {}, e = {}", b, e);
212                } else { // unsymmetric
213                    if (debug)
214                        logger.info("unsymmetric coeff: b = {}, e = {}", b, e);
215                    // compute e * b as ( e * 1/b.den ) * b.num
216                    if (b.den.isONE()) { // recursion base
217                        // recursive polynomial coefficient multiplication : e * b.num
218                        RecSolvablePolynomial<C> rsp1 = new RecSolvablePolynomial<C>(ring.polCoeff, e);
219                        RecSolvablePolynomial<C> rsp2 = new RecSolvablePolynomial<C>(ring.polCoeff, b.num);
220                        RecSolvablePolynomial<C> rsp3 = rsp1.multiply(rsp2);
221                        QuotSolvablePolynomial<C> rsp = ring.fromPolyCoefficients(rsp3);
222                        Cps = rsp;
223                    } else { // b.den != 1
224                        if (debug)
225                            logger.info("coeff-num: Cps = {}, num = {}, den = {}", Cps, b.num, b.den);
226                        Cps = new QuotSolvablePolynomial<C>(ring, b.ring.getONE(), e);
227
228                        // coefficient multiplication with 1/den: 
229                        QuotSolvablePolynomial<C> qv = Cps;
230                        SolvableQuotient<C> qden = new SolvableQuotient<C>(b.ring, b.den); // den/1
231                        //System.out.println("qv = " + qv + ", den = " + den);
232                        // recursion with den==1:
233                        QuotSolvablePolynomial<C> v = qv.multiply(qden);
234                        QuotSolvablePolynomial<C> vl = qv.multiplyLeft(qden);
235                        //System.out.println("v = " + v + ", vl = " + vl + ", qden = " + qden);
236                        QuotSolvablePolynomial<C> vr = (QuotSolvablePolynomial<C>) v.subtract(vl);
237                        SolvableQuotient<C> qdeni = new SolvableQuotient<C>(b.ring, b.ring.ring.getONE(),
238                                        b.den);
239                        //System.out.println("vr = " + vr + ", qdeni = " + qdeni);
240                        // recursion with smaller head term:
241                        QuotSolvablePolynomial<C> rq = vr.multiply(qdeni);
242                        qp = (QuotSolvablePolynomial<C>) qv.subtract(rq);
243                        qp = qp.multiplyLeft(qdeni);
244                        //System.out.println("qp_i = " + qp);
245                        Cps = qp;
246
247                        if (!b.num.isONE()) {
248                            SolvableQuotient<C> qnum = new SolvableQuotient<C>(b.ring, b.num); // num/1
249                            // recursion with den == 1:
250                            Cps = Cps.multiply(qnum);
251                        }
252                    }
253                } // end coeff
254                if (debug)
255                    logger.info("coeff-den: Cps = {}", Cps);
256                // polynomial multiplication 
257                QuotSolvablePolynomial<C> Dps = ring.getZERO().copy();
258                QuotSolvablePolynomial<C> Ds = null;
259                QuotSolvablePolynomial<C> D1, D2;
260                if (ring.table.isEmpty() || Cps.isConstant() || f.isZERO()) { // symmetric
261                    if (debug)
262                        logger.info("symmetric poly: b = {}, e = {}", b, e);
263                    ExpVector g = e.sum(f);
264                    if (Cps.isConstant()) {
265                        Ds = new QuotSolvablePolynomial<C>(ring, Cps.leadingBaseCoefficient(), g); // symmetric!
266                    } else {
267                        Ds = Cps.shift(f); // symmetric
268                    }
269                } else { // eventually unsymmetric
270                    if (debug)
271                        logger.info("unsymmetric poly: Cps = {}, f = {}", Cps, f);
272                    for (Map.Entry<ExpVector, SolvableQuotient<C>> z : Cps.val.entrySet()) {
273                        // split g = g1 * g2, f = f1 * f2
274                        SolvableQuotient<C> c = z.getValue();
275                        ExpVector g = z.getKey();
276                        if (debug)
277                            logger.info("g = {}, c = {}", g, c);
278                        int[] gp = g.dependencyOnVariables();
279                        int gl1 = ring.nvar + 1;
280                        if (gp.length > 0) {
281                            gl1 = gp[0];
282                        }
283                        int gl1s = ring.nvar + 1 - gl1;
284                        if (gl1s <= fl1s) { // symmetric
285                            ExpVector h = g.sum(f);
286                            if (debug)
287                                logger.info("disjoint poly: g = {}, f = {}, h = {}", g, f, h);
288                            Ds = (QuotSolvablePolynomial<C>) zero.sum(one, h); // symmetric!
289                        } else {
290                            ExpVector g1 = g.subst(gl1, 0);
291                            ExpVector g2 = Z.subst(gl1, g.getVal(gl1)); // bug el1, gl1
292                            ExpVector g4;
293                            ExpVector f1 = f.subst(fl1, 0);
294                            ExpVector f2 = Z.subst(fl1, f.getVal(fl1));
295                            if (debug) {
296                                logger.info("poly, g1 = {}, f1 = {}, Dps = {}", g1, f1, Dps);
297                                logger.info("poly, g2 = {}, f2 = {}", g2, f2);
298                            }
299                            TableRelation<SolvableQuotient<C>> rel = ring.table.lookup(g2, f2);
300                            if (debug)
301                                logger.info("poly, g  = {}, f  = {}, rel = {}", g, f, rel);
302                            Ds = new QuotSolvablePolynomial<C>(ring, rel.p); //ring.copy(rel.p);
303                            if (rel.f != null) {
304                                D2 = new QuotSolvablePolynomial<C>(ring, one, rel.f);
305                                Ds = Ds.multiply(D2);
306                                if (rel.e == null) {
307                                    g4 = g2;
308                                } else {
309                                    g4 = g2.subtract(rel.e);
310                                }
311                                ring.table.update(g4, f2, Ds);
312                            }
313                            if (rel.e != null) {
314                                D1 = new QuotSolvablePolynomial<C>(ring, one, rel.e);
315                                Ds = D1.multiply(Ds);
316                                ring.table.update(g2, f2, Ds);
317                            }
318                            if (!f1.isZERO()) {
319                                D2 = new QuotSolvablePolynomial<C>(ring, one, f1);
320                                Ds = Ds.multiply(D2);
321                                //ring.table.update(?,f1,Ds)
322                            }
323                            if (!g1.isZERO()) {
324                                D1 = new QuotSolvablePolynomial<C>(ring, one, g1);
325                                Ds = D1.multiply(Ds);
326                                //ring.table.update(e1,?,Ds)
327                            }
328                        }
329                        Ds = Ds.multiplyLeft(c); // c * Ds
330                        Dps = (QuotSolvablePolynomial<C>) Dps.sum(Ds);
331                    } // end Dps loop
332                    Ds = Dps;
333                }
334                Ds = Ds.multiplyLeft(a); // multiply(a,b); // non-symmetric 
335                logger.debug("Ds = {}", Ds);
336                Dp = (QuotSolvablePolynomial<C>) Dp.sum(Ds);
337            } // end B loop
338        } // end A loop
339          //System.out.println("this * Bp = " + Dp);
340        return Dp;
341    }
342
343
344    /**
345     * QuotSolvablePolynomial left and right multiplication. Product with two
346     * polynomials.
347     * @param S QuotSolvablePolynomial.
348     * @param T QuotSolvablePolynomial.
349     * @return S*this*T.
350     */
351    // not @Override
352    public QuotSolvablePolynomial<C> multiply(QuotSolvablePolynomial<C> S, QuotSolvablePolynomial<C> T) {
353        if (S.isZERO() || T.isZERO() || this.isZERO()) {
354            return ring.getZERO();
355        }
356        if (S.isONE()) {
357            return multiply(T);
358        }
359        if (T.isONE()) {
360            return S.multiply(this);
361        }
362        return S.multiply(this).multiply(T);
363    }
364
365
366    /**
367     * QuotSolvablePolynomial multiplication. Product with coefficient ring
368     * element.
369     * @param b solvable coefficient.
370     * @return this*b, where * is coefficient multiplication.
371     */
372    @Override
373    public QuotSolvablePolynomial<C> multiply(SolvableQuotient<C> b) {
374        QuotSolvablePolynomial<C> Cp = ring.getZERO().copy();
375        if (b == null || b.isZERO()) {
376            return Cp;
377        }
378        if (b.isONE()) {
379            return this;
380        }
381        Cp = new QuotSolvablePolynomial<C>(ring, b, ring.evzero);
382        return multiply(Cp);
383    }
384
385
386    /**
387     * QuotSolvablePolynomial left and right multiplication. Product with
388     * coefficient ring element.
389     * @param b coefficient polynomial.
390     * @param c coefficient polynomial.
391     * @return b*this*c, where * is coefficient multiplication.
392     */
393    @Override
394    public QuotSolvablePolynomial<C> multiply(SolvableQuotient<C> b, SolvableQuotient<C> c) {
395        QuotSolvablePolynomial<C> Cp = ring.getZERO().copy();
396        if (b == null || b.isZERO()) {
397            return Cp;
398        }
399        if (c == null || c.isZERO()) {
400            return Cp;
401        }
402        if (b.isONE() && c.isONE()) {
403            return this;
404        }
405        Cp = new QuotSolvablePolynomial<C>(ring, b, ring.evzero);
406        QuotSolvablePolynomial<C> Dp = new QuotSolvablePolynomial<C>(ring, c, ring.evzero);
407        return multiply(Cp, Dp);
408    }
409
410
411    /**
412     * QuotSolvablePolynomial multiplication. Product with exponent vector.
413     * @param e exponent.
414     * @return this * x<sup>e</sup>, where * denotes solvable multiplication.
415     */
416    @Override
417    public QuotSolvablePolynomial<C> multiply(ExpVector e) {
418        if (e == null || e.isZERO()) {
419            return this;
420        }
421        SolvableQuotient<C> b = ring.getONECoefficient();
422        return multiply(b, e);
423    }
424
425
426    /**
427     * QuotSolvablePolynomial left and right multiplication. Product with
428     * exponent vector.
429     * @param e exponent.
430     * @param f exponent.
431     * @return x<sup>e</sup> * this * x<sup>f</sup>, where * denotes solvable
432     *         multiplication.
433     */
434    @Override
435    public QuotSolvablePolynomial<C> multiply(ExpVector e, ExpVector f) {
436        if (e == null || e.isZERO()) {
437            return this;
438        }
439        if (f == null || f.isZERO()) {
440            return this;
441        }
442        SolvableQuotient<C> b = ring.getONECoefficient();
443        return multiply(b, e, b, f);
444    }
445
446
447    /**
448     * QuotSolvablePolynomial multiplication. Product with ring element and
449     * exponent vector.
450     * @param b coefficient polynomial.
451     * @param e exponent.
452     * @return this * b x<sup>e</sup>, where * denotes solvable multiplication.
453     */
454    @Override
455    public QuotSolvablePolynomial<C> multiply(SolvableQuotient<C> b, ExpVector e) {
456        if (b == null || b.isZERO()) {
457            return ring.getZERO();
458        }
459        if (b.isONE() && e.isZERO()) {
460            return this;
461        }
462        QuotSolvablePolynomial<C> Cp = new QuotSolvablePolynomial<C>(ring, b, e);
463        return multiply(Cp);
464    }
465
466
467    /**
468     * QuotSolvablePolynomial left and right multiplication. Product with ring
469     * element and exponent vector.
470     * @param b coefficient polynomial.
471     * @param e exponent.
472     * @param c coefficient polynomial.
473     * @param f exponent.
474     * @return b x<sup>e</sup> * this * c x<sup>f</sup>, where * denotes
475     *         solvable multiplication.
476     */
477    @Override
478    public QuotSolvablePolynomial<C> multiply(SolvableQuotient<C> b, ExpVector e, SolvableQuotient<C> c,
479                    ExpVector f) {
480        if (b == null || b.isZERO()) {
481            return ring.getZERO();
482        }
483        if (c == null || c.isZERO()) {
484            return ring.getZERO();
485        }
486        if (b.isONE() && e.isZERO() && c.isONE() && f.isZERO()) {
487            return this;
488        }
489        QuotSolvablePolynomial<C> Cp = new QuotSolvablePolynomial<C>(ring, b, e);
490        QuotSolvablePolynomial<C> Dp = new QuotSolvablePolynomial<C>(ring, c, f);
491        return multiply(Cp, Dp);
492    }
493
494
495    /**
496     * QuotSolvablePolynomial multiplication. Left product with ring element and
497     * exponent vector.
498     * @param b coefficient polynomial.
499     * @param e exponent.
500     * @return b x<sup>e</sup> * this, where * denotes solvable multiplication.
501     */
502    @Override
503    public QuotSolvablePolynomial<C> multiplyLeft(SolvableQuotient<C> b, ExpVector e) {
504        if (b == null || b.isZERO()) {
505            return ring.getZERO();
506        }
507        QuotSolvablePolynomial<C> Cp = new QuotSolvablePolynomial<C>(ring, b, e);
508        return Cp.multiply(this);
509    }
510
511
512    /**
513     * QuotSolvablePolynomial multiplication. Left product with exponent vector.
514     * @param e exponent.
515     * @return x<sup>e</sup> * this, where * denotes solvable multiplication.
516     */
517    @Override
518    public QuotSolvablePolynomial<C> multiplyLeft(ExpVector e) {
519        if (e == null || e.isZERO()) {
520            return this;
521        }
522        SolvableQuotient<C> b = ring.getONECoefficient();
523        QuotSolvablePolynomial<C> Cp = new QuotSolvablePolynomial<C>(ring, b, e);
524        return Cp.multiply(this);
525    }
526
527
528    /**
529     * QuotSolvablePolynomial multiplication. Left product with coefficient ring
530     * element.
531     * @param b coefficient polynomial.
532     * @return b*this, where * is coefficient multiplication.
533     */
534    @Override
535    public QuotSolvablePolynomial<C> multiplyLeft(SolvableQuotient<C> b) {
536        QuotSolvablePolynomial<C> Cp = ring.getZERO().copy();
537        if (b == null || b.isZERO()) {
538            return Cp;
539        }
540        Map<ExpVector, SolvableQuotient<C>> Cm = Cp.val; //getMap();
541        Map<ExpVector, SolvableQuotient<C>> Am = val;
542        SolvableQuotient<C> c;
543        for (Map.Entry<ExpVector, SolvableQuotient<C>> y : Am.entrySet()) {
544            ExpVector e = y.getKey();
545            SolvableQuotient<C> a = y.getValue();
546            c = b.multiply(a);
547            if (!c.isZERO()) {
548                Cm.put(e, c);
549            }
550        }
551        return Cp;
552    }
553
554
555    /**
556     * QuotSolvablePolynomial multiplication. Left product with 'monomial'.
557     * @param m 'monomial'.
558     * @return m * this, where * denotes solvable multiplication.
559     */
560    @Override
561    public QuotSolvablePolynomial<C> multiplyLeft(Map.Entry<ExpVector, SolvableQuotient<C>> m) {
562        if (m == null) {
563            return ring.getZERO();
564        }
565        return multiplyLeft(m.getValue(), m.getKey());
566    }
567
568
569    /**
570     * QuotSolvablePolynomial multiplication. Product with 'monomial'.
571     * @param m 'monomial'.
572     * @return this * m, where * denotes solvable multiplication.
573     */
574    @Override
575    public QuotSolvablePolynomial<C> multiply(Map.Entry<ExpVector, SolvableQuotient<C>> m) {
576        if (m == null) {
577            return ring.getZERO();
578        }
579        return multiply(m.getValue(), m.getKey());
580    }
581
582
583    /**
584     * QuotSolvablePolynomial multiplication. Left product with coefficient ring
585     * element.
586     * @param f exponent vector.
587     * @return B*f, where * is commutative multiplication.
588     */
589    protected QuotSolvablePolynomial<C> shift(ExpVector f) {
590        QuotSolvablePolynomial<C> C = ring.getZERO().copy();
591        if (this.isZERO()) {
592            return C;
593        }
594        if (f == null || f.isZERO()) {
595            return this;
596        }
597        Map<ExpVector, SolvableQuotient<C>> Cm = C.val;
598        Map<ExpVector, SolvableQuotient<C>> Bm = this.val;
599        for (Map.Entry<ExpVector, SolvableQuotient<C>> y : Bm.entrySet()) {
600            ExpVector e = y.getKey();
601            SolvableQuotient<C> a = y.getValue();
602            ExpVector d = e.sum(f);
603            if (!a.isZERO()) {
604                Cm.put(d, a);
605            }
606        }
607        return C;
608    }
609
610}