001/*
002 * $Id: CReductionSeq.java 5122 2015-02-17 08:35:15Z 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); // multiplyLeft in poly
110        ColorPolynomial<C> Bpp = Bp.multiply(a, f1); // multiplyLeft in poly
111        ColorPolynomial<C> Cp = App.subtract(Bpp);
112        assert (! g.equals(Cp.getEssentialPolynomial().leadingExpVector())) : "g == lt(Cp)";
113        return Cp;
114    }
115
116
117    /**
118     * Is top reducible.
119     * @param A polynomial.
120     * @param P polynomial list.
121     * @return true if A is top reducible with respect to P.
122     */
123    public boolean isTopReducible(List<ColorPolynomial<C>> P, ColorPolynomial<C> A) {
124        if (P == null || P.isEmpty()) {
125            return false;
126        }
127        if (A == null || A.isZERO()) {
128            return false;
129        }
130        boolean mt = false;
131        ExpVector e = A.leadingExpVector();
132        for (ColorPolynomial<C> p : P) {
133            if (p == null) {
134                return false;
135            }
136            ExpVector f = p.leadingExpVector();
137            if (f == null) {
138                return false;
139            }
140            if (e == null) {
141                return false;
142            }
143            mt = e.multipleOf(f); // EVMT( e, p.leadingExpVector() );
144            if (mt) {
145                return true;
146            }
147        }
148        return false;
149    }
150
151
152    /**
153     * Is reducible.
154     * @param Ap polynomial.
155     * @param Pp polynomial list.
156     * @return true if Ap is reducible with respect to Pp.
157     */
158    public boolean isReducible(List<ColorPolynomial<C>> Pp, ColorPolynomial<C> Ap) {
159        return !isNormalform(Pp, Ap);
160    }
161
162
163    /**
164     * Is in Normalform.
165     * @param Ap polynomial.
166     * @param Pp polynomial list.
167     * @return true if Ap is in normalform with respect to Pp.
168     */
169    @SuppressWarnings("unchecked")
170    public boolean isNormalform(List<ColorPolynomial<C>> Pp, ColorPolynomial<C> Ap) {
171        if (Pp == null || Pp.isEmpty()) {
172            return true;
173        }
174        if (Ap == null || Ap.isZERO()) {
175            return true;
176        }
177        int l;
178        ColorPolynomial<C>[] P;
179        synchronized (Pp) {
180            l = Pp.size();
181            P = new ColorPolynomial[l];
182            // P = Pp.toArray();
183            for (int i = 0; i < Pp.size(); i++) {
184                P[i] = Pp.get(i);
185            }
186        }
187        ExpVector[] htl = new ExpVector[l];
188        ColorPolynomial<C>[] p = new ColorPolynomial[l];
189        Map.Entry<ExpVector, GenPolynomial<C>> m;
190        int i;
191        int j = 0;
192        for (i = 0; i < l; i++) {
193            p[i] = P[i];
194            m = p[i].red.leadingMonomial();
195            if (m != null) {
196                p[j] = p[i];
197                htl[j] = m.getKey();
198                j++;
199            }
200        }
201        l = j;
202        boolean mt = false;
203        for (ExpVector e : Ap.red.getMap().keySet()) {
204            for (i = 0; i < l; i++) {
205                mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
206                if (mt) {
207                    System.out.println("not normalform " + Ap + ", P[i] = " + P[i]);
208                    return false;
209                }
210            }
211            if (top) {
212                return true;
213            }
214        }
215        for (ExpVector e : Ap.white.getMap().keySet()) {
216            for (i = 0; i < l; i++) {
217                mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
218                if (mt) {
219                    System.out.println("not normalform " + Ap + ", P[i] = " + P[i]);
220                    return false;
221                }
222            }
223            if (top) {
224                return true;
225            }
226        }
227        return true;
228    }
229
230
231    /**
232     * Is in Normalform.
233     * @param Pp polynomial list.
234     * @return true if each Ap in Pp is in normalform with respect to Pp\{Ap}.
235     */
236    public boolean isNormalform(List<ColorPolynomial<C>> Pp) {
237        if (Pp == null || Pp.isEmpty()) {
238            return true;
239        }
240        ColorPolynomial<C> Ap;
241        List<ColorPolynomial<C>> P = new LinkedList<ColorPolynomial<C>>(Pp);
242        int s = P.size();
243        for (int i = 0; i < s; i++) {
244            Ap = P.remove(i);
245            if (!isNormalform(P, Ap)) {
246                return false;
247            }
248            P.add(Ap);
249        }
250        return true;
251    }
252
253
254    /**
255     * Normalform.
256     * @param Ap polynomial.
257     * @param Pp polynomial list.
258     * @param cond condition for these polynomials.
259     * @return nf(Ap) with respect to Pp.
260     */
261    @SuppressWarnings("unchecked")
262    public ColorPolynomial<C> normalform(Condition<C> cond, List<ColorPolynomial<C>> Pp, ColorPolynomial<C> Ap) {
263        if (Pp == null || Pp.isEmpty()) {
264            return Ap;
265        }
266        if (Ap == null || Ap.isZERO()) {
267            return Ap;
268        }
269        Map.Entry<ExpVector, GenPolynomial<C>> m;
270        int l;
271        ColorPolynomial<C>[] P;
272        synchronized (Pp) {
273            l = Pp.size();
274            P = new ColorPolynomial[l];
275            // P = Pp.toArray();
276            for (int i = 0; i < Pp.size(); i++) {
277                P[i] = Pp.get(i);
278            }
279        }
280        ExpVector[] htl = new ExpVector[l];
281        Object[] lbc = new Object[l]; // want C[]
282        ColorPolynomial<C>[] p = new ColorPolynomial[l];
283        int i;
284        int j = 0;
285        for (i = 0; i < l; i++) {
286            if (P[i] == null) {
287                continue;
288            }
289            p[i] = P[i];
290            m = p[i].red.leadingMonomial();
291            if (m != null) {
292                p[j] = p[i];
293                htl[j] = m.getKey();
294                lbc[j] = m.getValue();
295                j++;
296            }
297        }
298        l = j;
299        ExpVector e, f;
300        GenPolynomial<C> a;
301        boolean mt = false;
302        GenPolynomial<GenPolynomial<C>> zero = p[0].red.ring.getZERO();
303        ColorPolynomial<C> R = new ColorPolynomial<C>(zero, zero, zero);
304
305        // ColorPolynomial<C> T = null;
306        ColorPolynomial<C> Q = null;
307        ColorPolynomial<C> S = Ap;
308        while (S.length() > 0) {
309            m = S.leadingMonomial();
310            e = m.getKey();
311            a = m.getValue();
312            Condition.Color col = cond.color(a);
313            if (col == Condition.Color.GREEN) { // move to green terms
314                GenPolynomial<GenPolynomial<C>> g = S.green.sum(a, e);
315                GenPolynomial<GenPolynomial<C>> r = S.red;
316                GenPolynomial<GenPolynomial<C>> w = S.white;
317                if (S.red.isZERO()) {
318                    w = w.subtract(a, e);
319                } else { // only in minimalGB
320                    logger.info("green_red = " + zero.sum(a, e));
321                    r = r.subtract(a, e);
322                }
323                S = new ColorPolynomial<C>(g, r, w);
324                continue;
325            }
326            //if (col == Condition.Color.WHITE) { // refine condition
327                // System.out.println("white = " + zero.sum(a,e));
328                // return S; // return for new case distinction
329            //}
330            // System.out.println("NF, e = " + e);
331            for (i = 0; i < l; i++) {
332                mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
333                if (mt)
334                    break;
335            }
336            if (!mt) {
337                // logger.debug("irred");
338                if (top) {
339                    return S;
340                }
341                R = R.sum(a, e);
342                S = S.subtract(a, e);
343                // System.out.println(" S = " + S);
344            } else {
345                f = e;
346                e = e.subtract(htl[i]); // EVDIF( e, htl[i] );
347                // logger.info("red div = " + e);
348                GenPolynomial<C> c = (GenPolynomial<C>) lbc[i];
349                GenPolynomial<C> g = engine.gcd(a, c);
350                if (!g.isONE()) {
351                    // System.out.println("gcd = " + g);
352                    a = a.divide(g);
353                    c = c.divide(g);
354                }
355                S = S.multiply(c);
356                R = R.multiply(c);
357                Q = p[i].multiply(a, e); // multiplyLeft in poly
358                S = S.subtract(Q);
359                assert (! f.equals(S.getEssentialPolynomial().leadingExpVector()) ) : "f == lt(S)";
360            }
361        }
362        return R;
363    }
364
365
366    /*
367     * -------- coloring and condition stuff ------------------------------
368     */
369
370    /**
371     * Case distinction conditions of parametric polynomial list. The returned
372     * condition determines the polynomial list.
373     * @param L list of parametric polynomials.
374     * @return list of conditions as case distinction.
375     */
376    public List<Condition<C>> caseDistinction(List<GenPolynomial<GenPolynomial<C>>> L) {
377        List<Condition<C>> cd = new ArrayList<Condition<C>>();
378        if (L == null || L.size() == 0) {
379            return cd;
380        }
381        for (GenPolynomial<GenPolynomial<C>> A : L) {
382            if (A != null && !A.isZERO()) {
383                cd = caseDistinction(cd, A);
384            }
385        }
386        // System.out.println("cd = " + cd);
387        return cd;
388    }
389
390
391    /**
392     * Case distinction conditions of parametric polynomial list.
393     * @param cd a list of conditions.
394     * @param A a parametric polynomial.
395     * @return list of conditions as case distinction extending the conditions
396     *         in cd.
397     */
398    public List<Condition<C>> caseDistinction(List<Condition<C>> cd, GenPolynomial<GenPolynomial<C>> A) {
399        if (A == null || A.isZERO()) {
400            return cd;
401        }
402        if (cd == null) {
403            cd = new ArrayList<Condition<C>>();
404        }
405        if (cd.size() == 0) { // construct empty condition
406            RingFactory<GenPolynomial<C>> crfac = A.ring.coFac;
407            GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) crfac;
408            Condition<C> sc = new Condition<C>(cfac);
409            cd.add(sc);
410        }
411        GenPolynomial<GenPolynomial<C>> Ap;
412        GenPolynomial<GenPolynomial<C>> Bp;
413
414        List<Condition<C>> C = new ArrayList<Condition<C>>( /* leer! */);
415        for (Condition<C> cond : cd) {
416            // System.out.println("caseDist: " + cond);
417            Condition<C> cz = cond;
418            Ap = A;
419            while (!Ap.isZERO()) {
420                GenPolynomial<C> c = Ap.leadingBaseCoefficient();
421                Bp = Ap.reductum();
422                //System.out.println("to color: " + c);
423                switch (cz.color(c)) {
424                case GREEN:
425                    // System.out.println("color green: " + c);
426                    Ap = Bp;
427                    continue;
428                case RED:
429                    // System.out.println("color red: " + c);
430                    C.add(cz);
431                    // wrong: return C;
432                    Ap = A.ring.getZERO();
433                    continue;
434                    // break;
435                case WHITE:
436                default:
437                    // System.out.println("color white: " + c);
438                    Condition<C> nc = cz.extendNonZero(c);
439                    if (nc != null) { // no contradiction
440                        if (!cz.equals(nc)) {
441                            C.add(nc);
442                        } else {
443                            cz = null;
444                            Ap = A.ring.getZERO();
445                            continue;
446                        }
447                    } else { // contradiction rechecked in determine(c)
448                        //System.out.println("this should not be printed, c  = " + c);
449                        //System.out.println("this should not be printed, cz = " + cz);
450                    }
451                    Condition<C> ez = cz.extendZero(c);
452                    if (ez != null) {
453                        cz = ez;
454                    } else { // contradiction
455                        cz = null;
456                        Ap = A.ring.getZERO();
457                        continue;
458                    }
459                    Ap = Bp;
460                }
461            }
462            // System.out.println("cond cz: " + cz);
463            if (cz == null || cz.isContradictory() || C.contains(cz)) {
464                // System.out.println("not added entry " + cz);
465            } else {
466                C.add(cz);
467            }
468        }
469        // System.out.println("C = " + C);
470        return C;
471    }
472
473
474    /**
475     * Case distinction conditions of parametric polynomial list.
476     * @param A a parametric polynomial.
477     * @param cond a condition.
478     * @return list of case distinction conditions.
479     */
480    public List<Condition<C>> caseDistinction(Condition<C> cond, GenPolynomial<GenPolynomial<C>> A) {
481        List<Condition<C>> cd = new ArrayList<Condition<C>>();
482        if (A == null || A.isZERO()) {
483            return cd;
484        }
485        cd.add(cond);
486        cd = caseDistinction(cd, A);
487        if (info) {
488            StringBuffer s = new StringBuffer("extending condition: " + cond + "\n");
489            s.append("case distinctions: [ \n");
490            for (Condition<C> c : cd) {
491                s.append(c.toString() + "\n");
492            }
493            s.append("]");
494            logger.info(s.toString());
495        }
496        return cd;
497    }
498
499
500    /**
501     * Determine polynomial list.
502     * @param H polynomial list.
503     * @return new determined list of colored systems.
504     */
505    public List<ColoredSystem<C>> determine(List<GenPolynomial<GenPolynomial<C>>> H) {
506        if (H == null || H.size() == 0) {
507            List<ColoredSystem<C>> CS = new ArrayList<ColoredSystem<C>>();
508            return CS;
509        }
510        //System.out.println("of determine     = " + H);
511        Collections.reverse(H);
512        List<Condition<C>> cd = caseDistinction(H);
513        //System.out.println("case Distinction = " + cd);
514        //System.out.println("of determine     = " + H);
515        return determine(cd, H);
516    }
517
518
519    /**
520     * Determine polynomial list.
521     * @param H polynomial list.
522     * @param cd case distiction, a condition list.
523     * @return new determined list of colored systems.
524     */
525    public List<ColoredSystem<C>> determine(List<Condition<C>> cd, List<GenPolynomial<GenPolynomial<C>>> H) {
526        List<ColoredSystem<C>> CS = new ArrayList<ColoredSystem<C>>();
527        if (H == null || H.size() == 0) {
528            return CS;
529        }
530        for (Condition<C> cond : cd) {
531            logger.info("determine wrt cond = " + cond);
532            if (cond.zero.isONE()) { // should not happen
533                System.out.println("ideal is one = " + cond.zero);
534                // continue; // can treat all coeffs as green
535            }
536            // if ( cond.isEmpty() ) { // do not use this code
537            // continue; // can skip condition (?)
538            // }
539            List<ColorPolynomial<C>> S = cond.determine(H);
540            ColoredSystem<C> cs = new ColoredSystem<C>(cond, S);
541            CS.add(cs);
542        }
543        return CS;
544    }
545
546}