Source code

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