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