Source code

001/*
002 * $Id: RGroebnerBasePseudoSeq.java 5870 2018-07-20 15:56:23Z 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.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            if (logger.isDebugEnabled()) {
155                logger.debug("ht(S) = " + S.leadingExpVector());
156            }
157
158            H = red.normalform(G, S);
159            if (H.isZERO()) {
160                pair.setZero();
161                continue;
162            }
163            if (logger.isDebugEnabled()) {
164                logger.debug("ht(H) = " + H.leadingExpVector());
165            }
166            H = engine.basePrimitivePart(H);
167            H = H.abs(); // not monic, no field
168            if (H.isConstant() && H.leadingBaseCoefficient().isFull()) {
169                // mostly useless
170                G.clear();
171                G.add(H);
172                return G; // not boolean closed ok, no threads are activated
173            }
174            if (logger.isDebugEnabled()) {
175                logger.debug("H = " + H);
176            }
177            if (!H.isZERO()) {
178                // logger.info("Sred = " + H);
179                // len = G.size();
180                bcH = red.reducedBooleanClosure(G, H);
181                // logger.info("#bcH = " + bcH.size());
182                // G.addAll( bcH );
183                for (GenPolynomial<C> h : bcH) {
184                    h = engine.basePrimitivePart(h);
185                    h = h.abs(); // monic() not ok, since no field
186                    logger.info("bc(Sred) = " + h);
187                    G.add(h);
188                    pairlist.put(h);
189                }
190                if (debug) {
191                    if (!pair.getUseCriterion3() || !pair.getUseCriterion4()) {
192                        logger.info("H != 0 but: " + pair);
193                    }
194                }
195            }
196        }
197        logger.debug("#sequential list = " + G.size());
198        G = minimalGB(G);
199        // G = red.irreducibleSet(G); // not correct since not boolean closed
200        logger.info("" + pairlist);
201        return G;
202    }
203
204
205    /**
206     * Minimal ordered Groebner basis.
207     * @param Gp a Groebner base.
208     * @return a reduced Groebner base of Gp.
209     */
210    @Override
211    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
212        if (Gp == null || Gp.size() <= 1) {
213            return Gp;
214        }
215        // remove zero polynomials
216        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
217        for (GenPolynomial<C> a : Gp) {
218            if (a != null && !a.isZERO()) { // always true in GB()
219                a = a.abs(); // already positive in GB
220                G.add(a);
221            }
222        }
223        // remove top reducible polynomials
224        logger.info("minGB start with " + G.size());
225        GenPolynomial<C> a, b;
226        List<GenPolynomial<C>> F;
227        F = new ArrayList<GenPolynomial<C>>(G.size());
228        while (G.size() > 0) {
229            a = G.remove(0);
230            b = a;
231            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
232                // try to drop polynomial
233                List<GenPolynomial<C>> ff;
234                ff = new ArrayList<GenPolynomial<C>>(G);
235                ff.addAll(F);
236                a = red.normalform(ff, a);
237                if (a.isZERO()) {
238                    //if (false && !isGB(ff)) { // is really required, but why?
239                    //    logger.info("minGB not dropped " + b);
240                    //    F.add(b);
241                    //} else {
242                    if (debug) {
243                        logger.debug("minGB dropped " + b);
244                    }
245                    //}
246                } else { // happens
247                    logger.info("minGB not zero " + a);
248                    F.add(a);
249                }
250            } else { // not top reducible, keep polynomial
251                F.add(a);
252            }
253        }
254        G = F;
255        Collections.reverse(G); // important for lex GB
256        // reduce remaining polynomials
257        int len = G.size();
258        int el = 0;
259        while (el < len) {
260            el++;
261            a = G.remove(0);
262            b = a;
263            a = red.normalform(G, a);
264            a = engine.basePrimitivePart(a); // not a.monic() since no field
265            a = a.abs();
266            if (red.isBooleanClosed(a)) {
267                //List<GenPolynomial<C>> ff;
268                //ff = new ArrayList<GenPolynomial<C>>(G);
269                //ff.add(a);
270                //if (true || isGB(ff)) {
271                if (debug) {
272                    logger.debug("minGB reduced " + b + " to " + a);
273                }
274                G.add(a);
275                //} else {
276                //    logger.info("minGB not reduced " + b + " to " + a);
277                //    G.add(b);
278                //}
279                continue;
280            }
281            logger.info("minGB not boolean closed " + a);
282            G.add(b); // do not reduce
283        }
284        /* stratify: collect polynomials with equal leading terms */
285        ExpVector e, f;
286        F = new ArrayList<GenPolynomial<C>>(G.size());
287        List<GenPolynomial<C>> ff;
288        ff = new ArrayList<GenPolynomial<C>>(G);
289        for (int i = 0; i < ff.size(); i++) {
290            a = ff.get(i);
291            if (a == null || a.isZERO()) {
292                continue;
293            }
294            e = a.leadingExpVector();
295            for (int j = i + 1; j < ff.size(); j++) {
296                b = ff.get(j);
297                if (b == null || b.isZERO()) {
298                    continue;
299                }
300                f = b.leadingExpVector();
301                if (e.equals(f)) {
302                    // System.out.println("minGB e == f: " + a + ", " + b);
303                    a = a.sum(b);
304                    ff.set(j, null);
305                }
306            }
307            F.add(a);
308        }
309        //if (true || isGB(F)) {
310        G = F;
311        //} else {
312        //    logger.info("minGB not stratified " + F);
313        //}
314        logger.info("minGB end with #G = " + G.size());
315        return G;
316    }
317
318
319    /*
320     * Minimal ordered Groebner basis. 
321     * @param Gp a Groebner base. 
322     * @return a reduced Groebner base of Gp. 
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            // use primitivePart
395            a = engine.basePrimitivePart(a); // not a.monic() since no field
396            // not bc:
397            if (red.isBooleanClosed(a)) {
398                List<GenPolynomial<C>> ff;
399                ff = new ArrayList<GenPolynomial<C>>(G);
400                ff.add(a);
401                if (isGB(ff)) {
402                    System.out.println("minGB reduced " + b + " to " + a);
403                    G.add(a);
404                } else {
405                    System.out.println("minGB not reduced " + b + " to " + a);
406                    G.add(b);
407                }
408                continue;
409            }
410            System.out.println("minGB not bc: a = " + a + "\n BC(a) = " + red.booleanClosure(a)
411                            + ", BR(a) = " + red.booleanRemainder(a));
412            bcH = red.reducedBooleanClosure(G, a);
413            if (bcH.size() > 1) {
414                System.out.println("minGB not bc: bcH size = " + bcH.size());
415                G.add(b); // do not reduce
416            } else {
417                // G.addAll( bcH );
418                G.add(b); // do not reduce
419                for (GenPolynomial<C> h : bcH) {
420                    // use primitivePart
421                    h = engine.basePrimitivePart(h);
422                    h = h.abs(); // monic() not ok, since no field
423                    // G.add( h );
424                }
425            }
426        }
427        // make abs if possible
428        F = new ArrayList<GenPolynomial<C>>(G.size());
429        for (GenPolynomial<C> p : G) {
430            a = p.abs();
431            F.add(a);
432        }
433        G = F;
434        //if (false) {
435        //    return G;
436        //}
437        // stratify: collect polynomials with equal leading terms
438        ExpVector e, f;
439        F = new ArrayList<GenPolynomial<C>>(G.size());
440        for (int i = 0; i < G.size(); i++) {
441            a = G.get(i);
442            if (a == null || a.isZERO()) {
443                continue;
444            }
445            e = a.leadingExpVector();
446            for (int j = i + 1; j < G.size(); j++) {
447                b = G.get(j);
448                if (b == null || b.isZERO()) {
449                    continue;
450                }
451                f = b.leadingExpVector();
452                if (e.equals(f)) {
453                    // System.out.println("minGB e == f: " + a + ", " + b);
454                    a = a.sum(b);
455                    G.set(j, null);
456                }
457            }
458            F.add(a);
459        }
460        G = F;
461
462        // info on boolean algebra element blocks
463        Map<C, List<GenPolynomial<C>>> bd = new TreeMap<C, List<GenPolynomial<C>>>();
464        for (GenPolynomial<C> p : G) {
465            C cf = p.leadingBaseCoefficient();
466            cf = cf.idempotent();
467            List<GenPolynomial<C>> block = bd.get(cf);
468            if (block == null) {
469                block = new ArrayList<GenPolynomial<C>>();
470            }
471            block.add(p);
472            bd.put(cf, block);
473        }
474        System.out.println("\nminGB bd:");
475        for (Map.Entry<C, List<GenPolynomial<C>>> me : bd.entrySet()) {
476            System.out.println("\nkey = " + me.getKey() + ":");
477            System.out.println("val = " + me.getValue());
478        }
479        System.out.println();
480        //
481        return G;
482    }
483
484}