Source code

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