Source code

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