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