Source code

001/*
002 * $Id: CReductionSeq.java 4115 2012-08-19 13:18:59Z kredel $
003 */
004
005package edu.jas.application;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.Collections;
011import java.util.LinkedList;
012import java.util.List;
013import java.util.Map;
014
015import org.apache.log4j.Logger;
016
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.structure.GcdRingElem;
021import edu.jas.structure.RingFactory;
022import edu.jas.ufd.GCDFactory;
023import edu.jas.ufd.GreatestCommonDivisor;
024
025
026/**
027 * Polynomial parametric ring reduction sequential use algorithm. Implements
028 * normalform, condition construction and polynomial determination.
029 * @param <C> coefficient type
030 * @author Heinz Kredel
031 */
032public class CReductionSeq<C extends GcdRingElem<C>> implements Serializable
033/* extends ReductionAbstract<C> */
034/* implements CReduction<C> */{
035
036
037    private static final Logger logger = Logger.getLogger(CReductionSeq.class);
038
039
040    //private final boolean debug = logger.isDebugEnabled();
041
042
043    private final boolean info = logger.isInfoEnabled();
044
045
046    /**
047     * Greatest common divisor engine.
048     */
049    protected final GreatestCommonDivisor<C> engine;
050
051
052    /**
053     * Polynomial coefficient ring factory.
054     */
055    protected final RingFactory<C> cofac;
056
057
058    /**
059     * Flag if top-reduction only should be used.
060     */
061    protected boolean top = true; // false;
062
063
064    /**
065     * Constructor.
066     * @param rf coefficient factory.
067     */
068    public CReductionSeq(RingFactory<C> rf) {
069        cofac = rf;
070        // System.out.println("cofac = " + cofac);
071        engine = GCDFactory.<C> getImplementation(cofac);
072    }
073
074
075    /**
076     * S-Polynomial.
077     * @param Ap polynomial.
078     * @param Bp polynomial.
079     * @return spol(Ap,Bp) the S-polynomial of Ap and Bp.
080     */
081    public ColorPolynomial<C> SPolynomial(ColorPolynomial<C> Ap, ColorPolynomial<C> Bp) {
082        if (Bp == null || Bp.isZERO()) {
083            return Bp;
084        }
085        if (Ap == null || Ap.isZERO()) {
086            return Ap;
087        }
088
089        Map.Entry<ExpVector, GenPolynomial<C>> ma = Ap.red.leadingMonomial();
090        Map.Entry<ExpVector, GenPolynomial<C>> mb = Bp.red.leadingMonomial();
091
092        ExpVector e = ma.getKey();
093        ExpVector f = mb.getKey();
094
095        ExpVector g = e.lcm(f); // EVLCM(e,f);
096        ExpVector e1 = g.subtract(e); // EVDIF(g,e);
097        ExpVector f1 = g.subtract(f); // EVDIF(g,f);
098
099        GenPolynomial<C> a = ma.getValue();
100        GenPolynomial<C> b = mb.getValue();
101
102        GenPolynomial<C> c = engine.gcd(a, b);
103        if (!c.isONE()) {
104            // System.out.println("gcd =s " + c);
105            a = a.divide(c);
106            b = b.divide(c);
107        }
108
109        ColorPolynomial<C> App = Ap.multiply(b, e1);
110        ColorPolynomial<C> Bpp = Bp.multiply(a, f1);
111        ColorPolynomial<C> Cp = App.subtract(Bpp);
112        return Cp;
113    }
114
115
116    /**
117     * Is top reducible.
118     * @param A polynomial.
119     * @param P polynomial list.
120     * @return true if A is top reducible with respect to P.
121     */
122    public boolean isTopReducible(List<ColorPolynomial<C>> P, ColorPolynomial<C> A) {
123        if (P == null || P.isEmpty()) {
124            return false;
125        }
126        if (A == null || A.isZERO()) {
127            return false;
128        }
129        boolean mt = false;
130        ExpVector e = A.leadingExpVector();
131        for (ColorPolynomial<C> p : P) {
132            if (p == null) {
133                return false;
134            }
135            ExpVector f = p.leadingExpVector();
136            if (f == null) {
137                return false;
138            }
139            if (e == null) {
140                return false;
141            }
142            mt = e.multipleOf(f); // EVMT( e, p.leadingExpVector() );
143            if (mt) {
144                return true;
145            }
146        }
147        return false;
148    }
149
150
151    /**
152     * Is reducible.
153     * @param Ap polynomial.
154     * @param Pp polynomial list.
155     * @return true if Ap is reducible with respect to Pp.
156     */
157    public boolean isReducible(List<ColorPolynomial<C>> Pp, ColorPolynomial<C> Ap) {
158        return !isNormalform(Pp, Ap);
159    }
160
161
162    /**
163     * Is in Normalform.
164     * @param Ap polynomial.
165     * @param Pp polynomial list.
166     * @return true if Ap is in normalform with respect to Pp.
167     */
168    @SuppressWarnings("unchecked")
169    public boolean isNormalform(List<ColorPolynomial<C>> Pp, ColorPolynomial<C> Ap) {
170        if (Pp == null || Pp.isEmpty()) {
171            return true;
172        }
173        if (Ap == null || Ap.isZERO()) {
174            return true;
175        }
176        int l;
177        ColorPolynomial<C>[] P;
178        synchronized (Pp) {
179            l = Pp.size();
180            P = new ColorPolynomial[l];
181            // P = Pp.toArray();
182            for (int i = 0; i < Pp.size(); i++) {
183                P[i] = Pp.get(i);
184            }
185        }
186        ExpVector[] htl = new ExpVector[l];
187        ColorPolynomial<C>[] p = new ColorPolynomial[l];
188        Map.Entry<ExpVector, GenPolynomial<C>> m;
189        int i;
190        int j = 0;
191        for (i = 0; i < l; i++) {
192            p[i] = P[i];
193            m = p[i].red.leadingMonomial();
194            if (m != null) {
195                p[j] = p[i];
196                htl[j] = m.getKey();
197                j++;
198            }
199        }
200        l = j;
201        boolean mt = false;
202        for (ExpVector e : Ap.red.getMap().keySet()) {
203            for (i = 0; i < l; i++) {
204                mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
205                if (mt) {
206                    System.out.println("not normalform " + Ap + ", P[i] = " + P[i]);
207                    return false;
208                }
209            }
210            if (top) {
211                return true;
212            }
213        }
214        for (ExpVector e : Ap.white.getMap().keySet()) {
215            for (i = 0; i < l; i++) {
216                mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
217                if (mt) {
218                    System.out.println("not normalform " + Ap + ", P[i] = " + P[i]);
219                    return false;
220                }
221            }
222            if (top) {
223                return true;
224            }
225        }
226        return true;
227    }
228
229
230    /**
231     * Is in Normalform.
232     * @param Pp polynomial list.
233     * @return true if each Ap in Pp is in normalform with respect to Pp\{Ap}.
234     */
235    public boolean isNormalform(List<ColorPolynomial<C>> Pp) {
236        if (Pp == null || Pp.isEmpty()) {
237            return true;
238        }
239        ColorPolynomial<C> Ap;
240        List<ColorPolynomial<C>> P = new LinkedList<ColorPolynomial<C>>(Pp);
241        int s = P.size();
242        for (int i = 0; i < s; i++) {
243            Ap = P.remove(i);
244            if (!isNormalform(P, Ap)) {
245                return false;
246            }
247            P.add(Ap);
248        }
249        return true;
250    }
251
252
253    /**
254     * Normalform.
255     * @param Ap polynomial.
256     * @param Pp polynomial list.
257     * @param cond condition for these polynomials.
258     * @return nf(Ap) with respect to Pp.
259     */
260    @SuppressWarnings("unchecked")
261    public ColorPolynomial<C> normalform(Condition<C> cond, List<ColorPolynomial<C>> Pp, ColorPolynomial<C> Ap) {
262        if (Pp == null || Pp.isEmpty()) {
263            return Ap;
264        }
265        if (Ap == null || Ap.isZERO()) {
266            return Ap;
267        }
268        Map.Entry<ExpVector, GenPolynomial<C>> m;
269        int l;
270        ColorPolynomial<C>[] P;
271        synchronized (Pp) {
272            l = Pp.size();
273            P = new ColorPolynomial[l];
274            // P = Pp.toArray();
275            for (int i = 0; i < Pp.size(); i++) {
276                P[i] = Pp.get(i);
277            }
278        }
279        ExpVector[] htl = new ExpVector[l];
280        Object[] lbc = new Object[l]; // want C[]
281        ColorPolynomial<C>[] p = new ColorPolynomial[l];
282        int i;
283        int j = 0;
284        for (i = 0; i < l; i++) {
285            if (P[i] == null) {
286                continue;
287            }
288            p[i] = P[i];
289            m = p[i].red.leadingMonomial();
290            if (m != null) {
291                p[j] = p[i];
292                htl[j] = m.getKey();
293                lbc[j] = m.getValue();
294                j++;
295            }
296        }
297        l = j;
298        ExpVector e;
299        GenPolynomial<C> a;
300        boolean mt = false;
301        GenPolynomial<GenPolynomial<C>> zero = p[0].red.ring.getZERO();
302        ColorPolynomial<C> R = new ColorPolynomial<C>(zero, zero, zero);
303
304        // ColorPolynomial<C> T = null;
305        ColorPolynomial<C> Q = null;
306        ColorPolynomial<C> S = Ap;
307        while (S.length() > 0) {
308            m = S.leadingMonomial();
309            e = m.getKey();
310            a = m.getValue();
311            Condition.Color col = cond.color(a);
312            if (col == Condition.Color.GREEN) { // move to green terms
313                GenPolynomial<GenPolynomial<C>> g = S.green.sum(a, e);
314                GenPolynomial<GenPolynomial<C>> r = S.red;
315                GenPolynomial<GenPolynomial<C>> w = S.white;
316                if (S.red.isZERO()) {
317                    w = w.subtract(a, e);
318                } else { // only in minimalGB
319                    logger.info("green_red = " + zero.sum(a, e));
320                    r = r.subtract(a, e);
321                }
322                S = new ColorPolynomial<C>(g, r, w);
323                continue;
324            }
325            //if (col == Condition.Color.WHITE) { // refine condition
326                // System.out.println("white = " + zero.sum(a,e));
327                // return S; // return for new case distinction
328            //}
329            // System.out.println("NF, e = " + e);
330            for (i = 0; i < l; i++) {
331                mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
332                if (mt)
333                    break;
334            }
335            if (!mt) {
336                // logger.debug("irred");
337                if (top) {
338                    return S;
339                }
340                R = R.sum(a, e);
341                S = S.subtract(a, e);
342                // System.out.println(" S = " + S);
343            } else {
344                e = e.subtract(htl[i]); // EVDIF( e, htl[i] );
345                // logger.info("red div = " + e);
346                GenPolynomial<C> c = (GenPolynomial<C>) lbc[i];
347                GenPolynomial<C> g = engine.gcd(a, c);
348                if (!g.isONE()) {
349                    // System.out.println("gcd = " + g);
350                    a = a.divide(g);
351                    c = c.divide(g);
352                }
353                S = S.multiply(c);
354                R = R.multiply(c);
355                Q = p[i].multiply(a, e);
356                S = S.subtract(Q);
357            }
358        }
359        return R;
360    }
361
362
363    /*
364     * -------- coloring and condition stuff ------------------------------
365     */
366
367    /**
368     * Case distinction conditions of parametric polynomial list. The returned
369     * condition determines the polynomial list.
370     * @param L list of parametric polynomials.
371     * @return list of conditions as case distinction.
372     */
373    public List<Condition<C>> caseDistinction(List<GenPolynomial<GenPolynomial<C>>> L) {
374        List<Condition<C>> cd = new ArrayList<Condition<C>>();
375        if (L == null || L.size() == 0) {
376            return cd;
377        }
378        for (GenPolynomial<GenPolynomial<C>> A : L) {
379            if (A != null && !A.isZERO()) {
380                cd = caseDistinction(cd, A);
381            }
382        }
383        // System.out.println("cd = " + cd);
384        return cd;
385    }
386
387
388    /**
389     * Case distinction conditions of parametric polynomial list.
390     * @param cd a list of conditions.
391     * @param A a parametric polynomial.
392     * @return list of conditions as case distinction extending the conditions
393     *         in cd.
394     */
395    public List<Condition<C>> caseDistinction(List<Condition<C>> cd, GenPolynomial<GenPolynomial<C>> A) {
396        if (A == null || A.isZERO()) {
397            return cd;
398        }
399        if (cd == null) {
400            cd = new ArrayList<Condition<C>>();
401        }
402        if (cd.size() == 0) { // construct empty condition
403            RingFactory<GenPolynomial<C>> crfac = A.ring.coFac;
404            GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) crfac;
405            Condition<C> sc = new Condition<C>(cfac);
406            cd.add(sc);
407        }
408        GenPolynomial<GenPolynomial<C>> Ap;
409        GenPolynomial<GenPolynomial<C>> Bp;
410
411        List<Condition<C>> C = new ArrayList<Condition<C>>( /* leer! */);
412        for (Condition<C> cond : cd) {
413            // System.out.println("caseDist: " + cond);
414            Condition<C> cz = cond;
415            Ap = A;
416            while (!Ap.isZERO()) {
417                GenPolynomial<C> c = Ap.leadingBaseCoefficient();
418                Bp = Ap.reductum();
419                //System.out.println("to color: " + c);
420                switch (cz.color(c)) {
421                case GREEN:
422                    // System.out.println("color green: " + c);
423                    Ap = Bp;
424                    continue;
425                case RED:
426                    // System.out.println("color red: " + c);
427                    C.add(cz);
428                    // wrong: return C;
429                    Ap = A.ring.getZERO();
430                    continue;
431                    // break;
432                case WHITE:
433                default:
434                    // System.out.println("color white: " + c);
435                    Condition<C> nc = cz.extendNonZero(c);
436                    if (nc != null) { // no contradiction
437                        if (!cz.equals(nc)) {
438                            C.add(nc);
439                        } else {
440                            cz = null;
441                            Ap = A.ring.getZERO();
442                            continue;
443                        }
444                    } else {
445                        System.out.println("this should not be printed " + c);
446                    }
447                    Condition<C> ez = cz.extendZero(c);
448                    if (ez != null) {
449                        cz = ez;
450                    } else { // contradiction
451                        cz = null;
452                        Ap = A.ring.getZERO();
453                        continue;
454                    }
455                    Ap = Bp;
456                }
457            }
458            // System.out.println("cond cz: " + cz);
459            if (cz == null || cz.isContradictory() || C.contains(cz)) {
460                // System.out.println("not added entry " + cz);
461            } else {
462                C.add(cz);
463            }
464        }
465        // System.out.println("C = " + C);
466        return C;
467    }
468
469
470    /**
471     * Case distinction conditions of parametric polynomial list.
472     * @param A a parametric polynomial.
473     * @param cond a condition.
474     * @return list of case distinction conditions.
475     */
476    public List<Condition<C>> caseDistinction(Condition<C> cond, GenPolynomial<GenPolynomial<C>> A) {
477        List<Condition<C>> cd = new ArrayList<Condition<C>>();
478        if (A == null || A.isZERO()) {
479            return cd;
480        }
481        cd.add(cond);
482        cd = caseDistinction(cd, A);
483        if (info) {
484            StringBuffer s = new StringBuffer("extending condition: " + cond + "\n");
485            s.append("case distinctions: [ \n");
486            for (Condition<C> c : cd) {
487                s.append(c.toString() + "\n");
488            }
489            s.append("]");
490            logger.info(s.toString());
491        }
492        return cd;
493    }
494
495
496    /**
497     * Determine polynomial list.
498     * @param H polynomial list.
499     * @return new determined list of colored systems.
500     */
501    public List<ColoredSystem<C>> determine(List<GenPolynomial<GenPolynomial<C>>> H) {
502        if (H == null || H.size() == 0) {
503            List<ColoredSystem<C>> CS = new ArrayList<ColoredSystem<C>>();
504            return CS;
505        }
506        //System.out.println("of determine     = " + H);
507        Collections.reverse(H);
508        List<Condition<C>> cd = caseDistinction(H);
509        //System.out.println("case Distinction = " + cd);
510        //System.out.println("of determine     = " + H);
511        return determine(cd, H);
512    }
513
514
515    /**
516     * Determine polynomial list.
517     * @param H polynomial list.
518     * @param cd case distiction, a condition list.
519     * @return new determined list of colored systems.
520     */
521    public List<ColoredSystem<C>> determine(List<Condition<C>> cd, List<GenPolynomial<GenPolynomial<C>>> H) {
522        List<ColoredSystem<C>> CS = new ArrayList<ColoredSystem<C>>();
523        if (H == null || H.size() == 0) {
524            return CS;
525        }
526        for (Condition<C> cond : cd) {
527            logger.info("determine wrt cond = " + cond);
528            if (cond.zero.isONE()) { // should not happen
529                System.out.println("ideal is one = " + cond.zero);
530                // continue; // can treat all coeffs as green
531            }
532            // if ( cond.isEmpty() ) { // do not use this code
533            // continue; // can skip condition (?)
534            // }
535            List<ColorPolynomial<C>> S = cond.determine(H);
536            ColoredSystem<C> cs = new ColoredSystem<C>(cond, S);
537            CS.add(cs);
538        }
539        return CS;
540    }
541
542}