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