Source code

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