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