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