Source code

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