Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.Iterator;
010import java.util.List;
011import java.util.Map;
012
013import org.apache.logging.log4j.LogManager;
014import org.apache.logging.log4j.Logger;
015
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.Monomial;
018import edu.jas.poly.GenSolvablePolynomial;
019import edu.jas.poly.GenSolvablePolynomialRing;
020import edu.jas.poly.ModuleList;
021import edu.jas.poly.PolynomialList;
022import edu.jas.structure.RingElem;
023
024
025/**
026 * Solvable polynomial Reduction abstract class. Implements common left, right
027 * S-Polynomial, left normalform and left irreducible set.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032public abstract class SolvableReductionAbstract<C extends RingElem<C>> implements SolvableReduction<C> {
033
034
035    private static final Logger logger = LogManager.getLogger(SolvableReductionAbstract.class);
036
037
038    private static final boolean debug = logger.isDebugEnabled();
039
040
041    /**
042     * Constructor.
043     */
044    public SolvableReductionAbstract() {
045    }
046
047
048    /**
049     * Left S-Polynomial.
050     * @param Ap solvable polynomial.
051     * @param Bp solvable polynomial.
052     * @return left-spol(Ap,Bp) the left S-polynomial of Ap and Bp.
053     */
054    public GenSolvablePolynomial<C> leftSPolynomial(GenSolvablePolynomial<C> Ap,
055                    GenSolvablePolynomial<C> Bp) {
056        if (logger.isInfoEnabled()) {
057            if (Bp == null || Bp.isZERO()) {
058                if (Ap != null) {
059                    return Ap.ring.getZERO();
060                }
061                return null;
062            }
063            if (Ap == null || Ap.isZERO()) {
064                return Bp.ring.getZERO();
065            }
066            if (!Ap.ring.equals(Bp.ring)) {
067                logger.error("rings not equal");
068            }
069        }
070        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
071        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
072
073        ExpVector e = ma.getKey();
074        ExpVector f = mb.getKey();
075
076        ExpVector g = e.lcm(f);
077        ExpVector e1 = g.subtract(e);
078        ExpVector f1 = g.subtract(f);
079
080        C a = ma.getValue();
081        C b = mb.getValue();
082
083        GenSolvablePolynomial<C> App = Ap.multiplyLeft(b, e1);
084        GenSolvablePolynomial<C> Bpp = Bp.multiplyLeft(a, f1);
085        GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp);
086        return Cp;
087    }
088
089
090    /**
091     * S-Polynomial with recording.
092     * @param S recording matrix, is modified.
093     * @param i index of Ap in basis list.
094     * @param Ap a polynomial.
095     * @param j index of Bp in basis list.
096     * @param Bp a polynomial.
097     * @return leftSpol(Ap, Bp), the left S-Polynomial for Ap and Bp.
098     */
099    public GenSolvablePolynomial<C> leftSPolynomial(List<GenSolvablePolynomial<C>> S, int i,
100                    GenSolvablePolynomial<C> Ap, int j, GenSolvablePolynomial<C> Bp) {
101        if (debug /*logger.isInfoEnabled()*/) {
102            if (Bp == null || Bp.isZERO()) {
103                throw new ArithmeticException("Spol B is zero");
104            }
105            if (Ap == null || Ap.isZERO()) {
106                throw new ArithmeticException("Spol A is zero");
107            }
108            if (!Ap.ring.equals(Bp.ring)) {
109                logger.error("rings not equal");
110            }
111        }
112        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
113        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
114
115        ExpVector e = ma.getKey();
116        ExpVector f = mb.getKey();
117
118        ExpVector g = e.lcm(f);
119        ExpVector e1 = g.subtract(e);
120        ExpVector f1 = g.subtract(f);
121
122        C a = ma.getValue();
123        C b = mb.getValue();
124
125        GenSolvablePolynomial<C> App = Ap.multiplyLeft(b, e1);
126        GenSolvablePolynomial<C> Bpp = Bp.multiplyLeft(a, f1);
127        GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp);
128
129        GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
130        GenSolvablePolynomial<C> As = (GenSolvablePolynomial<C>) zero.sum(b.negate(), e1);
131        GenSolvablePolynomial<C> Bs = (GenSolvablePolynomial<C>) zero.sum(a, f1);
132        S.set(i, As);
133        S.set(j, Bs);
134        return Cp;
135    }
136
137
138    /**
139     * Left Normalform Set.
140     * @param Ap solvable polynomial list.
141     * @param Pp solvable polynomial list.
142     * @return list of left-nf(a) with respect to Pp for all a in Ap.
143     */
144    public List<GenSolvablePolynomial<C>> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
145                    List<GenSolvablePolynomial<C>> Ap) {
146        if (Pp == null || Pp.isEmpty()) {
147            return Ap;
148        }
149        if (Ap == null || Ap.isEmpty()) {
150            return Ap;
151        }
152        ArrayList<GenSolvablePolynomial<C>> red = new ArrayList<GenSolvablePolynomial<C>>();
153        for (GenSolvablePolynomial<C> A : Ap) {
154            A = leftNormalform(Pp, A);
155            red.add(A);
156        }
157        return red;
158    }
159
160
161    /**
162     * Module left normalform set.
163     * @param Ap module list.
164     * @param Pp module list.
165     * @return list of left-nf(a) with respect to Pp for all a in Ap.
166     */
167    public ModuleList<C> leftNormalform(ModuleList<C> Pp, ModuleList<C> Ap) {
168        return leftNormalform(Pp, Ap, false);
169    }
170
171
172    /**
173     * Module left normalform set.
174     * @param Ap module list.
175     * @param Pp module list.
176     * @param top true for TOP term order, false for POT term order.
177     * @return list of left-nf(a) with respect to Pp for all a in Ap.
178     */
179    public ModuleList<C> leftNormalform(ModuleList<C> Pp, ModuleList<C> Ap, boolean top) {
180        if (Pp == null || Pp.isEmpty()) {
181            return Ap;
182        }
183        if (Ap == null || Ap.isEmpty()) {
184            return Ap;
185        }
186        GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) Pp.ring;
187        int modv = Pp.cols;
188        GenSolvablePolynomialRing<C> pfac = sring.extend(modv, top);
189        logger.debug("extended ring = {}", pfac.toScript());
190        //System.out.println("extended ring = " + pfac.toScript());
191        PolynomialList<C> P = Pp.getPolynomialList(pfac);
192        PolynomialList<C> A = Ap.getPolynomialList(pfac);
193        //System.out.println("P = " + P.toScript());
194
195        List<GenSolvablePolynomial<C>> red = leftNormalform(P.castToSolvableList(), A.castToSolvableList());
196        PolynomialList<C> Fr = new PolynomialList<C>(pfac, red);
197        ModuleList<C> Nr = Fr.getModuleList(modv);
198        return Nr;
199    }
200
201
202    /**
203     * Left irreducible set.
204     * @param Pp solvable polynomial list.
205     * @return a list P of solvable polynomials which are in normalform wrt. P.
206     */
207    public List<GenSolvablePolynomial<C>> leftIrreducibleSet(List<GenSolvablePolynomial<C>> Pp) {
208        ArrayList<GenSolvablePolynomial<C>> P = new ArrayList<GenSolvablePolynomial<C>>();
209        for (GenSolvablePolynomial<C> a : Pp) {
210            if (a.length() != 0) {
211                a = a.monic();
212                P.add(a);
213            }
214        }
215        int l = P.size();
216        if (l <= 1)
217            return P;
218
219        int irr = 0;
220        ExpVector e;
221        ExpVector f;
222        GenSolvablePolynomial<C> a;
223        Iterator<GenSolvablePolynomial<C>> it;
224        logger.debug("irr = ");
225        while (irr != l) {
226            it = P.listIterator();
227            a = it.next();
228            P.remove(0);
229            e = a.leadingExpVector();
230            a = leftNormalform(P, a);
231            logger.debug(String.valueOf(irr));
232            if (a.length() == 0) {
233                l--;
234                if (l <= 1) {
235                    return P;
236                }
237            } else {
238                f = a.leadingExpVector();
239                if (f.signum() == 0) {
240                    P = new ArrayList<GenSolvablePolynomial<C>>();
241                    P.add(a.monic());
242                    return P;
243                }
244                if (e.equals(f)) {
245                    irr++;
246                } else {
247                    irr = 0;
248                    a = a.monic();
249                }
250                P.add(a);
251            }
252        }
253        //System.out.println();
254        return P;
255    }
256
257
258    /**
259     * Is reduction of normal form.
260     * @param row recording matrix.
261     * @param Pp a solvable polynomial list for reduction.
262     * @param Ap a solvable polynomial.
263     * @param Np nf(Pp,Ap), a left normal form of Ap wrt. Pp.
264     * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false.
265     */
266    @SuppressWarnings("unchecked")
267    public boolean isLeftReductionNF(List<GenSolvablePolynomial<C>> row, List<GenSolvablePolynomial<C>> Pp,
268                    GenSolvablePolynomial<C> Ap, GenSolvablePolynomial<C> Np) {
269        if (row == null && Pp == null) {
270            if (Ap == null) {
271                return Np == null;
272            }
273            return Ap.equals(Np);
274        }
275        if (row == null || Pp == null) {
276            return false;
277        }
278        if (row.size() != Pp.size()) {
279            return false;
280        }
281        GenSolvablePolynomial<C> t = Np;
282        GenSolvablePolynomial<C> r;
283        GenSolvablePolynomial<C> p;
284        for (int m = 0; m < Pp.size(); m++) {
285            r = row.get(m);
286            p = Pp.get(m);
287            if (r != null && p != null) {
288                if (t == null) {
289                    t = r.multiply(p);
290                } else {
291                    t = (GenSolvablePolynomial<C>) t.sum(r.multiply(p));
292                }
293            }
294            //System.out.println("r = " + r );
295            //System.out.println("p = " + p );
296        }
297        if (debug) {
298            logger.info("t = {}", t);
299            logger.info("a = {}", Ap);
300        }
301        if (t == null) {
302            if (Ap == null) {
303                return true;
304            }
305            return Ap.isZERO();
306        }
307        t = (GenSolvablePolynomial<C>) t.subtract(Ap);
308        return t.isZERO();
309    }
310
311
312    /**
313     * Right S-Polynomial.
314     * @param Ap solvable polynomial.
315     * @param Bp solvable polynomial.
316     * @return right-spol(Ap,Bp) the right S-polynomial of Ap and Bp.
317     */
318    @SuppressWarnings("unchecked")
319    public GenSolvablePolynomial<C> rightSPolynomial(GenSolvablePolynomial<C> Ap,
320                    GenSolvablePolynomial<C> Bp) {
321        if (logger.isInfoEnabled()) {
322            if (Bp == null || Bp.isZERO()) {
323                if (Ap != null) {
324                    return Ap.ring.getZERO();
325                }
326                return null;
327            }
328            if (Ap == null || Ap.isZERO()) {
329                return Bp.ring.getZERO();
330            }
331            if (!Ap.ring.equals(Bp.ring)) {
332                logger.error("rings not equal");
333            }
334        }
335        ExpVector e = Ap.leadingExpVector();
336        ExpVector f = Bp.leadingExpVector();
337
338        ExpVector g = e.lcm(f);
339        ExpVector e1 = g.subtract(e);
340        ExpVector f1 = g.subtract(f);
341
342        C a = Ap.leadingBaseCoefficient();
343        C b = Bp.leadingBaseCoefficient();
344
345        GenSolvablePolynomial<C> App = Ap.multiply(b,e1);
346        GenSolvablePolynomial<C> Bpp = Bp.multiply(a,f1);
347
348        // App = App.multiply(b);
349        // Bpp = Bpp.multiply(a);
350
351        if (!App.leadingMonomial().equals(Bpp.leadingMonomial()) ) {
352            logger.info("lm(A) = " + new Monomial(App.leadingMonomial()) + ", lm(B) = " + new Monomial(Bpp.leadingMonomial()));
353            logger.info("right S-polynomial with unequal leading monomials: " + Ap.ring.toScript());
354            //throw new UnsupportedOperationException("right S-polynomial with error");
355        }
356        GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp);
357        return Cp;
358    }
359
360
361    /**
362     * S-Polynomial with recording.
363     * @param S recording matrix, is modified.
364     * @param i index of Ap in basis list.
365     * @param Ap a polynomial.
366     * @param j index of Bp in basis list.
367     * @param Bp a polynomial.
368     * @return rightSpol(Ap, Bp), the right S-Polynomial for Ap and Bp.
369     */
370    public GenSolvablePolynomial<C> rightSPolynomial(List<GenSolvablePolynomial<C>> S, int i,
371                    GenSolvablePolynomial<C> Ap, int j, GenSolvablePolynomial<C> Bp) {
372        if (debug /*logger.isInfoEnabled()*/) {
373            if (Bp == null || Bp.isZERO()) {
374                throw new ArithmeticException("Spol B is zero");
375            }
376            if (Ap == null || Ap.isZERO()) {
377                throw new ArithmeticException("Spol A is zero");
378            }
379            if (!Ap.ring.equals(Bp.ring)) {
380                logger.error("rings not equal");
381            }
382        }
383        Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
384        Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
385
386        ExpVector e = ma.getKey();
387        ExpVector f = mb.getKey();
388
389        ExpVector g = e.lcm(f);
390        ExpVector e1 = g.subtract(e);
391        ExpVector f1 = g.subtract(f);
392
393        C a = ma.getValue();
394        C b = mb.getValue();
395
396        GenSolvablePolynomial<C> App = Ap.multiply(b, e1);
397        GenSolvablePolynomial<C> Bpp = Bp.multiply(a, f1);
398
399        if (!App.leadingMonomial().equals(Bpp.leadingMonomial()) ) {
400            System.out.println("lm(A) = " + App.leadingMonomial() + ", lm(B) = " + Bpp.leadingMonomial());
401            throw new UnsupportedOperationException("right S-polynomial undefined ");
402        }
403        GenSolvablePolynomial<C> Cp = (GenSolvablePolynomial<C>) App.subtract(Bpp);
404
405        GenSolvablePolynomial<C> zero = Ap.ring.getZERO();
406        GenSolvablePolynomial<C> As = (GenSolvablePolynomial<C>) zero.sum(b.negate(), e1);
407        GenSolvablePolynomial<C> Bs = (GenSolvablePolynomial<C>) zero.sum(a, f1);
408        S.set(i, As);
409        S.set(j, Bs);
410        return Cp;
411    }
412
413
414    /**
415     * Is top reducible. Is left right symmetric.
416     * @param A solvable polynomial.
417     * @param P solvable polynomial list.
418     * @return true if A is top reducible with respect to P.
419     */
420    public boolean isTopReducible(List<GenSolvablePolynomial<C>> P, GenSolvablePolynomial<C> A) {
421        if (P == null || P.isEmpty()) {
422            return false;
423        }
424        if (A == null || A.isZERO()) {
425            return false;
426        }
427        boolean mt = false;
428        ExpVector e = A.leadingExpVector();
429        for (GenSolvablePolynomial<C> p : P) {
430            mt = e.multipleOf(p.leadingExpVector());
431            if (mt) {
432                return true;
433            }
434        }
435        return false;
436    }
437
438
439    /**
440     * Is reducible. Is left right symmetric.
441     * @param Ap solvable polynomial.
442     * @param Pp solvable polynomial list.
443     * @return true if Ap is reducible with respect to Pp.
444     */
445    public boolean isReducible(List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
446        return !isNormalform(Pp, Ap);
447    }
448
449
450    /**
451     * Is in Normalform. Is left right symmetric.
452     * @param Ap polynomial.
453     * @param Pp polynomial list.
454     * @return true if Ap is in normalform with respect to Pp.
455     */
456    @SuppressWarnings("unchecked")
457    public boolean isNormalform(List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) {
458        if (Pp == null || Pp.isEmpty()) {
459            return true;
460        }
461        if (Ap == null || Ap.isZERO()) {
462            return true;
463        }
464        GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0];
465        synchronized (Pp) {
466            P = Pp.toArray(P);
467        }
468        int l = P.length;
469        ExpVector[] htl = new ExpVector[l];
470        GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l];
471        ExpVector f;
472        int i;
473        int j = 0;
474        for (i = 0; i < l; i++) {
475            p[i] = P[i];
476            f = p[i].leadingExpVector();
477            if (f != null) {
478                p[j] = p[i];
479                htl[j] = f;
480                j++;
481            }
482        }
483        l = j;
484        boolean mt = false;
485        for (ExpVector e : Ap.getMap().keySet()) {
486            for (i = 0; i < l; i++) {
487                mt = e.multipleOf(htl[i]);
488                if (mt) {
489                    return false;
490                }
491            }
492        }
493        return true;
494    }
495
496
497    /**
498     * Is right reduction of normal form.
499     * @param row recording matrix.
500     * @param Pp a solvable polynomial list for reduction.
501     * @param Ap a solvable polynomial.
502     * @param Np nf(Pp,Ap), a left normal form of Ap wrt. Pp.
503     * @return true, if Np + sum( Pp[i]*row[i] ) == Ap, else false.
504     */
505    @SuppressWarnings("unchecked")
506    public boolean isRightReductionNF(List<GenSolvablePolynomial<C>> row, List<GenSolvablePolynomial<C>> Pp,
507                    GenSolvablePolynomial<C> Ap, GenSolvablePolynomial<C> Np) {
508        if (row == null && Pp == null) {
509            if (Ap == null) {
510                return Np == null;
511            }
512            return Ap.equals(Np);
513        }
514        if (row == null || Pp == null) {
515            return false;
516        }
517        if (row.size() != Pp.size()) {
518            return false;
519        }
520        GenSolvablePolynomial<C> t = Np;
521        GenSolvablePolynomial<C> r;
522        GenSolvablePolynomial<C> p;
523        for (int m = 0; m < Pp.size(); m++) {
524            r = row.get(m);
525            p = Pp.get(m);
526            if (r != null && p != null) {
527                if (t == null) {
528                    t = p.multiply(r); //right
529                } else {
530                    t = (GenSolvablePolynomial<C>) t.sum(p.multiply(r)); //right
531                }
532            }
533            //System.out.println("r = " + r );
534            //System.out.println("p = " + p );
535        }
536        if (debug) {
537            logger.info("t = {}", t);
538            logger.info("a = {}", Ap);
539        }
540        if (t == null) {
541            if (Ap == null) {
542                return true;
543            }
544            return Ap.isZERO();
545        }
546        t = (GenSolvablePolynomial<C>) t.subtract(Ap);
547        return t.isZERO();
548    }
549
550
551    /**
552     * Two-sided Normalform.
553     * @param Ap solvable polynomial.
554     * @param Pp solvable polynomial list.
555     * @return two-sided-nf(Ap) with respect to Pp.
556     */
557    public GenSolvablePolynomial<C> normalform(List<GenSolvablePolynomial<C>> Pp,
558                    GenSolvablePolynomial<C> Ap) {
559        throw new UnsupportedOperationException("two-sided normalform not implemented");
560    }
561
562}