Source code

001/*
002 * $Id: RGroebnerBasePseudoSeq.java 4521 2013-07-27 10:16:36Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.List;
011import java.util.Map;
012import java.util.TreeMap;
013
014import org.apache.log4j.Logger;
015
016import edu.jas.gb.Pair;
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.structure.RegularRingElem;
020import edu.jas.structure.RingFactory;
021import edu.jas.ufd.GCDFactory;
022import edu.jas.ufd.GreatestCommonDivisorAbstract;
023
024
025/**
026 * Regular ring Groebner Base with pseudo reduction sequential algorithm.
027 * Implements R-Groebner bases and GB test.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032public class RGroebnerBasePseudoSeq<C extends RegularRingElem<C>> extends RGroebnerBaseSeq<C> {
033
034
035    private static final Logger logger = Logger.getLogger(RGroebnerBasePseudoSeq.class);
036
037
038    private final boolean debug = logger.isDebugEnabled();
039
040
041    /**
042     * Greatest common divisor engine for coefficient content and primitive
043     * parts.
044     */
045    protected final GreatestCommonDivisorAbstract<C> engine;
046
047
048    /**
049     * Pseudo reduction engine.
050     */
051    protected final RPseudoReduction<C> red;
052
053
054    /**
055     * Coefficient ring factory.
056     */
057    protected final RingFactory<C> cofac;
058
059
060    /**
061     * Constructor.
062     * @param rf coefficient ring factory.
063     */
064    public RGroebnerBasePseudoSeq(RingFactory<C> rf) {
065        this(new RPseudoReductionSeq<C>(), rf);
066    }
067
068
069    /**
070     * Constructor.
071     * @param red R-pseudo-Reduction engine
072     * @param rf coefficient ring factory.
073     */
074    public RGroebnerBasePseudoSeq(RPseudoReduction<C> red, RingFactory<C> rf) {
075        super(red);
076        this.red = red;
077        cofac = rf;
078        engine = GCDFactory.<C> getImplementation(rf);
079        // not used: engine =
080        // (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf );
081    }
082
083
084    /**
085     * R-Groebner base using pairlist class.
086     * @param modv module variable number.
087     * @param F polynomial list.
088     * @return GB(F) a R-Groebner base of F.
089     */
090    @Override
091    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
092        if (F == null) {
093            return F;
094        }
095        /* boolean closure */
096        List<GenPolynomial<C>> bcF = red.reducedBooleanClosure(F);
097        logger.info("#bcF-#F = " + (bcF.size() - F.size()));
098        F = bcF;
099        /* normalize input */
100        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
101        OrderedRPairlist<C> pairlist = null;
102        for (GenPolynomial<C> p : F) {
103            if (!p.isZERO()) {
104                p = engine.basePrimitivePart(p); // not monic, no field
105                p = p.abs();
106                if (p.isConstant() && p.leadingBaseCoefficient().isFull()) {
107                    G.clear();
108                    G.add(p);
109                    return G; // since boolean closed and no threads are activated
110                }
111                G.add(p); // G.add( 0, p ); //reverse list
112                if (pairlist == null) {
113                    pairlist = new OrderedRPairlist<C>(modv, p.ring);
114                }
115                // putOne not required
116                pairlist.put(p);
117            }
118        }
119        if (G.size() <= 1) {
120            return G; // since boolean closed and no threads are activated
121        }
122        /* loop on critical pairs */
123        Pair<C> pair;
124        GenPolynomial<C> pi;
125        GenPolynomial<C> pj;
126        GenPolynomial<C> S;
127        // GenPolynomial<C> D;
128        GenPolynomial<C> H;
129        List<GenPolynomial<C>> bcH;
130        while (pairlist.hasNext()) {
131            pair = pairlist.removeNext();
132            // System.out.println("pair = " + pair);
133            if (pair == null)
134                continue;
135
136            pi = pair.pi;
137            pj = pair.pj;
138            if (logger.isDebugEnabled()) {
139                logger.info("pi    = " + pi);
140                logger.info("pj    = " + pj);
141            }
142            if (!red.moduleCriterion(modv, pi, pj)) {
143                continue;
144            }
145
146            // S-polynomial -----------------------
147            // Criterion3(), Criterion4() not applicable
148            S = red.SPolynomial(pi, pj);
149            if (S.isZERO()) {
150                pair.setZero();
151                continue;
152            }
153            if (logger.isDebugEnabled()) {
154                logger.debug("ht(S) = " + S.leadingExpVector());
155            }
156
157            H = red.normalform(G, S);
158            if (H.isZERO()) {
159                pair.setZero();
160                continue;
161            }
162            if (logger.isDebugEnabled()) {
163                logger.debug("ht(H) = " + H.leadingExpVector());
164            }
165            H = engine.basePrimitivePart(H);
166            H = H.abs(); // not monic, no field
167            if (H.isConstant() && H.leadingBaseCoefficient().isFull()) {
168                // mostly useless
169                G.clear();
170                G.add(H);
171                return G; // not boolean closed ok, no threads are activated
172            }
173            if (logger.isDebugEnabled()) {
174                logger.debug("H = " + H);
175            }
176            if (!H.isZERO()) {
177                // logger.info("Sred = " + H);
178                // len = G.size();
179                bcH = red.reducedBooleanClosure(G, H);
180                // logger.info("#bcH = " + bcH.size());
181                // G.addAll( bcH );
182                for (GenPolynomial<C> h : bcH) {
183                    h = engine.basePrimitivePart(h);
184                    h = h.abs(); // monic() not ok, since no field
185                    logger.info("bc(Sred) = " + h);
186                    G.add(h);
187                    pairlist.put(h);
188                }
189                if (debug) {
190                    if (!pair.getUseCriterion3() || !pair.getUseCriterion4()) {
191                        logger.info("H != 0 but: " + pair);
192                    }
193                }
194            }
195        }
196        logger.debug("#sequential list = " + G.size());
197        G = minimalGB(G);
198        // G = red.irreducibleSet(G); // not correct since not boolean closed
199        logger.info("" + pairlist);
200        return G;
201    }
202
203
204    /**
205     * Minimal ordered Groebner basis.
206     * @param Gp a Groebner base.
207     * @return a reduced Groebner base of Gp.
208     */
209    @Override
210    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
211        if (Gp == null || Gp.size() <= 1) {
212            return Gp;
213        }
214        // remove zero polynomials
215        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
216        for (GenPolynomial<C> a : Gp) {
217            if (a != null && !a.isZERO()) { // always true in GB()
218                a = a.abs(); // already positive in GB
219                G.add(a);
220            }
221        }
222        // remove top reducible polynomials
223        logger.info("minGB start with " + G.size());
224        GenPolynomial<C> a, b;
225        List<GenPolynomial<C>> F;
226        F = new ArrayList<GenPolynomial<C>>(G.size());
227        while (G.size() > 0) {
228            a = G.remove(0);
229            b = a;
230            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
231                // try to drop polynomial
232                List<GenPolynomial<C>> ff;
233                ff = new ArrayList<GenPolynomial<C>>(G);
234                ff.addAll(F);
235                a = red.normalform(ff, a);
236                if (a.isZERO()) {
237                    //if (false && !isGB(ff)) { // is really required, but why?
238                    //    logger.info("minGB not dropped " + b);
239                    //    F.add(b);
240                    //} else {
241                    if (debug) {
242                        logger.debug("minGB dropped " + b);
243                    }
244                    //}
245                } else { // happens
246                    logger.info("minGB not zero " + a);
247                    F.add(a);
248                }
249            } else { // not top reducible, keep polynomial
250                F.add(a);
251            }
252        }
253        G = F;
254        Collections.reverse(G); // important for lex GB
255        // reduce remaining polynomials
256        int len = G.size();
257        int el = 0;
258        while (el < len) {
259            el++;
260            a = G.remove(0);
261            b = a;
262            a = red.normalform(G, a);
263            a = engine.basePrimitivePart(a); // not a.monic() since no field
264            a = a.abs();
265            if (red.isBooleanClosed(a)) {
266                //List<GenPolynomial<C>> ff;
267                //ff = new ArrayList<GenPolynomial<C>>(G);
268                //ff.add(a);
269                //if (true || isGB(ff)) {
270                if (debug) {
271                    logger.debug("minGB reduced " + b + " to " + a);
272                }
273                G.add(a);
274                //} else {
275                //    logger.info("minGB not reduced " + b + " to " + a);
276                //    G.add(b);
277                //}
278                continue;
279            }
280            logger.info("minGB not boolean closed " + a);
281            G.add(b); // do not reduce
282        }
283        /* stratify: collect polynomials with equal leading terms */
284        ExpVector e, f;
285        F = new ArrayList<GenPolynomial<C>>(G.size());
286        List<GenPolynomial<C>> ff;
287        ff = new ArrayList<GenPolynomial<C>>(G);
288        for (int i = 0; i < ff.size(); i++) {
289            a = ff.get(i);
290            if (a == null || a.isZERO()) {
291                continue;
292            }
293            e = a.leadingExpVector();
294            for (int j = i + 1; j < ff.size(); j++) {
295                b = ff.get(j);
296                if (b == null || b.isZERO()) {
297                    continue;
298                }
299                f = b.leadingExpVector();
300                if (e.equals(f)) {
301                    // System.out.println("minGB e == f: " + a + ", " + b);
302                    a = a.sum(b);
303                    ff.set(j, null);
304                }
305            }
306            F.add(a);
307        }
308        //if (true || isGB(F)) {
309        G = F;
310        //} else {
311        //    logger.info("minGB not stratified " + F);
312        //}
313        logger.info("minGB end with #G = " + G.size());
314        return G;
315    }
316
317
318    /*
319     * Minimal ordered Groebner basis. 
320     * @param Gp a Groebner base. 
321     * @return a reduced Groebner base of Gp. 
322     * TODO: use primitivePart
323     */
324    List<GenPolynomial<C>> minimalGBtesting(List<GenPolynomial<C>> Gp) {
325        if (Gp == null || Gp.size() <= 1) {
326            return Gp;
327        }
328        // remove zero polynomials
329        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
330        for (GenPolynomial<C> a : Gp) {
331            if (a != null && !a.isZERO()) { // always true in GB()
332                // already positive a = a.abs();
333                G.add(a);
334            }
335        }
336        //if (G.size() <= 1) {
337            // wg monic do not return G;
338        //}
339        // remove top reducible polynomials
340        GenPolynomial<C> a, b;
341        List<GenPolynomial<C>> F;
342        List<GenPolynomial<C>> bcH;
343        F = new ArrayList<GenPolynomial<C>>(G.size());
344        while (G.size() > 0) {
345            a = G.remove(0);
346            b = a;
347            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
348                // drop polynomial
349                if (logger.isInfoEnabled()) {
350                    List<GenPolynomial<C>> ff;
351                    ff = new ArrayList<GenPolynomial<C>>(G);
352                    ff.addAll(F);
353                    a = red.normalform(ff, a);
354                    if (!a.isZERO()) {
355                        System.out.println("minGB nf(a) != 0 " + a);
356                        bcH = red.reducedBooleanClosure(G, a);
357                        if (bcH.size() > 1) { // never happend so far
358                            System.out.println("minGB not bc: bcH size = " + bcH.size());
359                            F.add(b); // do not replace, stay with b
360                        } else {
361                            // System.out.println("minGB add bc(a): a = " + a + ",
362                            // bc(a) = " + bcH.get(0));
363                            F.add(b); // do not replace, stay with b
364                            // F.addAll( bcH );
365                        }
366                    } else {
367                        if (!isGB(ff)) {
368                            System.out.println("minGB not dropped " + b);
369                            F.add(b);
370                        } else {
371                            System.out.println("minGB dropped " + b);
372                        }
373                    }
374                }
375            } else { // not top reducible, keep polynomial
376                F.add(a);
377            }
378        }
379        G = F;
380        //if (G.size() <= 1) {
381            // wg monic return G;
382        //}
383        Collections.reverse(G); // important for lex GB
384        // reduce remaining polynomials
385        int len = G.size();
386        int el = 0;
387        // System.out.println("minGB reducing " + len);
388        while (el < len) {
389            el++;
390            a = G.remove(0);
391            b = a;
392            // System.out.println("minGB doing " + el + ", a = " + a);
393            a = red.normalform(G, a);
394            // not bc:
395            a = engine.basePrimitivePart(a); // not a.monic() since no field
396            if (red.isBooleanClosed(a)) {
397                List<GenPolynomial<C>> ff;
398                ff = new ArrayList<GenPolynomial<C>>(G);
399                ff.add(a);
400                if (isGB(ff)) {
401                    System.out.println("minGB reduced " + b + " to " + a);
402                    G.add(a);
403                } else {
404                    System.out.println("minGB not reduced " + b + " to " + a);
405                    G.add(b);
406                }
407                continue;
408            }
409            System.out.println("minGB not bc: a = " + a + "\n BC(a) = " + red.booleanClosure(a)
410                            + ", BR(a) = " + red.booleanRemainder(a));
411            bcH = red.reducedBooleanClosure(G, a);
412            if (bcH.size() > 1) {
413                System.out.println("minGB not bc: bcH size = " + bcH.size());
414                G.add(b); // do not reduce
415            } else {
416                // G.addAll( bcH );
417                G.add(b); // do not reduce
418                for (GenPolynomial<C> h : bcH) {
419                    h = engine.basePrimitivePart(h);
420                    h = h.abs(); // monic() not ok, since no field
421                    // G.add( h );
422                }
423            }
424        }
425        // make abs if possible
426        F = new ArrayList<GenPolynomial<C>>(G.size());
427        for (GenPolynomial<C> p : G) {
428            a = p.abs();
429            F.add(a);
430        }
431        G = F;
432        //if (false) {
433        //    return G;
434        //}
435        // stratify: collect polynomials with equal leading terms
436        ExpVector e, f;
437        F = new ArrayList<GenPolynomial<C>>(G.size());
438        for (int i = 0; i < G.size(); i++) {
439            a = G.get(i);
440            if (a == null || a.isZERO()) {
441                continue;
442            }
443            e = a.leadingExpVector();
444            for (int j = i + 1; j < G.size(); j++) {
445                b = G.get(j);
446                if (b == null || b.isZERO()) {
447                    continue;
448                }
449                f = b.leadingExpVector();
450                if (e.equals(f)) {
451                    // System.out.println("minGB e == f: " + a + ", " + b);
452                    a = a.sum(b);
453                    G.set(j, null);
454                }
455            }
456            F.add(a);
457        }
458        G = F;
459
460        // info on boolean algebra element blocks
461        Map<C, List<GenPolynomial<C>>> bd = new TreeMap<C, List<GenPolynomial<C>>>();
462        for (GenPolynomial<C> p : G) {
463            C cf = p.leadingBaseCoefficient();
464            cf = cf.idempotent();
465            List<GenPolynomial<C>> block = bd.get(cf);
466            if (block == null) {
467                block = new ArrayList<GenPolynomial<C>>();
468            }
469            block.add(p);
470            bd.put(cf, block);
471        }
472        System.out.println("\nminGB bd:");
473        for (Map.Entry<C, List<GenPolynomial<C>>> me : bd.entrySet()) {
474            System.out.println("\nkey = " + me.getKey() + ":");
475            System.out.println("val = " + me.getValue());
476        }
477        System.out.println();
478        //
479        return G;
480    }
481
482}