Source code

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