Source code

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