Source code

001/*
002 * $Id: RGroebnerBaseSeq.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;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.gb.GroebnerBaseAbstract;
016import edu.jas.gb.Pair;
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.structure.RegularRingElem;
020
021
022/**
023 * Regular ring Groebner Base sequential algorithm. Implements R-Groebner bases
024 * and GB test.
025 * @param <C> coefficient type
026 * @author Heinz Kredel
027 */
028
029public class RGroebnerBaseSeq<C extends RegularRingElem<C>> extends GroebnerBaseAbstract<C> {
030
031
032    private static final Logger logger = LogManager.getLogger(RGroebnerBaseSeq.class);
033
034
035    private static final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Reduction engine.
040     */
041    protected RReduction<C> rred; // shadow super.red ??
042
043
044    /**
045     * Constructor.
046     */
047    public RGroebnerBaseSeq() {
048        this(new RReductionSeq<C>());
049    }
050
051
052    /**
053     * Constructor.
054     * @param rred R-Reduction engine
055     */
056    public RGroebnerBaseSeq(RReduction<C> rred) {
057        super(rred);
058        this.rred = rred;
059        assert super.red == this.rred;
060    }
061
062
063    /**
064     * R-Groebner base test.
065     * @param modv module variable number.
066     * @param F polynomial list.
067     * @return true, if F is a R-Groebner base, else false.
068     */
069    @Override
070    public boolean isGB(int modv, List<GenPolynomial<C>> F) {
071        if (F == null) {
072            return true;
073        }
074        if (!rred.isBooleanClosed(F)) {
075            if (debug) {
076                logger.debug("not boolean closed");
077            }
078            return false;
079        }
080        GenPolynomial<C> pi, pj, s;
081        for (int i = 0; i < F.size(); i++) {
082            pi = F.get(i);
083            for (int j = i + 1; j < F.size(); j++) {
084                pj = F.get(j);
085                if (!red.moduleCriterion(modv, pi, pj)) {
086                    continue;
087                }
088                // red.criterion4 not applicable
089                s = red.SPolynomial(pi, pj);
090                if (s.isZERO()) {
091                    continue;
092                }
093                s = red.normalform(F, s);
094                if (!s.isZERO()) {
095                    if (debug) {
096                        logger.debug("p" + i + " = " + pi);
097                        logger.debug("p" + j + " = " + pj);
098                        logger.debug("s-pol = " + red.SPolynomial(pi, pj));
099                        logger.debug("s-pol(" + i + "," + j + ") != 0: " + s);
100                    }
101                    return false;
102                }
103            }
104        }
105        return true;
106    }
107
108
109    /**
110     * R-Groebner base using pairlist class.
111     * @param modv module variable number.
112     * @param F polynomial list.
113     * @return GB(F) a R-Groebner base of F.
114     */
115    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
116        /* boolean closure */
117        List<GenPolynomial<C>> bcF = rred.reducedBooleanClosure(F);
118        logger.info("#bcF-#F = " + (bcF.size() - F.size()));
119        F = bcF;
120        /* normalize input */
121        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
122        OrderedRPairlist<C> pairlist = null;
123        for (GenPolynomial<C> p : F) {
124            if (!p.isZERO()) {
125                p = p.monic(); //p.abs(); // not monic, monic if boolean closed
126                if (p.isONE()) {
127                    G.clear();
128                    G.add(p);
129                    return G; // since boolean closed and no threads are activated
130                }
131                G.add(p); //G.add( 0, p ); //reverse list
132                if (pairlist == null) {
133                    pairlist = new OrderedRPairlist<C>(modv, p.ring);
134                }
135                // putOne not required
136                pairlist.put(p);
137            }
138        }
139        if (G.size() <= 1) {
140            return G; // since boolean closed and no threads are activated
141        }
142        /* loop on critical pairs */
143        Pair<C> pair;
144        GenPolynomial<C> pi;
145        GenPolynomial<C> pj;
146        GenPolynomial<C> S;
147        //GenPolynomial<C> D;
148        GenPolynomial<C> H;
149        List<GenPolynomial<C>> bcH;
150        //int len = G.size();
151        //System.out.println("len = " + len);
152        while (pairlist.hasNext()) {
153            pair = pairlist.removeNext();
154            //System.out.println("pair = " + pair);
155            if (pair == null)
156                continue;
157
158            pi = pair.pi;
159            pj = pair.pj;
160            if (logger.isDebugEnabled()) {
161                logger.debug("pi    = " + pi);
162                logger.debug("pj    = " + pj);
163            }
164            if (!red.moduleCriterion(modv, pi, pj)) {
165                continue;
166            }
167
168            // S-polynomial -----------------------
169            // Criterion3() Criterion4() not applicable
170            S = red.SPolynomial(pi, pj);
171            if (S.isZERO()) {
172                pair.setZero();
173                continue;
174            }
175            if (logger.isDebugEnabled()) {
176                logger.debug("ht(S) = " + S.leadingExpVector());
177            }
178
179            H = red.normalform(G, S);
180            if (H.isZERO()) {
181                pair.setZero();
182                continue;
183            }
184            //H = H.monic(); // only for boolean closed H
185            if (logger.isDebugEnabled()) {
186                logger.debug("ht(H) = " + H.leadingExpVector());
187            }
188
189            if (H.isONE()) { // mostly useless
190                G.clear();
191                G.add(H);
192                return G; // not boolean closed ok, since no threads are activated
193            }
194            if (logger.isDebugEnabled()) {
195                logger.debug("H = " + H);
196            }
197            if (!H.isZERO()) {
198                logger.info("Sred = " + H);
199                //len = G.size();
200                bcH = rred.reducedBooleanClosure(G, H);
201                logger.info("#bcH = " + bcH.size());
202                for (GenPolynomial<C> h : bcH) {
203                    h = h.monic(); // monic() ok, since boolean closed
204                    G.add(h);
205                    pairlist.put(h);
206                }
207                if (debug) {
208                    if (!pair.getUseCriterion3() || !pair.getUseCriterion4()) {
209                        logger.info("H != 0 but: " + pair);
210                    }
211                }
212            }
213        }
214        logger.debug("#sequential list = " + G.size());
215        G = minimalGB(G);
216        //G = red.irreducibleSet(G);
217        logger.info("" + pairlist);
218        return G;
219    }
220
221
222    /**
223     * Minimal ordered Groebner basis.
224     * @param Gp a Groebner base.
225     * @return a reduced Groebner base of Gp.
226     */
227    @Override
228    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
229        if (Gp == null || Gp.size() <= 1) {
230            return Gp;
231        }
232        // remove zero polynomials
233        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
234        for (GenPolynomial<C> a : Gp) {
235            if (a != null && !a.isZERO()) { // always true in GB()
236                // already positive a = a.abs();
237                G.add(a);
238            }
239        }
240        //if (G.size() <= 1) {
241            //wg monic do not return G;
242        //}
243        // remove top reducible polynomials
244        GenPolynomial<C> a, b;
245        List<GenPolynomial<C>> F;
246        List<GenPolynomial<C>> bcH;
247        F = new ArrayList<GenPolynomial<C>>(G.size());
248        while (G.size() > 0) {
249            a = G.remove(0);
250            b = a;
251            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
252                // drop polynomial 
253                if (logger.isInfoEnabled()) {
254                    List<GenPolynomial<C>> ff;
255                    ff = new ArrayList<GenPolynomial<C>>(G);
256                    ff.addAll(F);
257                    a = red.normalform(ff, a);
258                    if (!a.isZERO()) { // happens
259                        logger.info("minGB not zero " + a);
260                        bcH = rred.reducedBooleanClosure(G, a);
261                        if (bcH.size() > 1) { // never happend so far
262                            System.out.println("minGB not bc: bcH size = " + bcH.size());
263                            F.add(b); // do not replace, stay with b
264                        } else {
265                            //System.out.println("minGB add bc(a): a = " + a + ", bc(a) = " + bcH.get(0));
266                            F.addAll(bcH);
267                        }
268                    } else {
269                        //System.out.println("minGB dropped " + b);
270                    }
271                }
272            } else {
273                F.add(a);
274            }
275        }
276        G = F;
277        //if (G.size() <= 1) {
278            // wg monic return G;
279        //}
280        Collections.reverse(G); // important for lex GB
281        // reduce remaining polynomials
282        int len = G.size();
283        int el = 0;
284        while (el < len) {
285            a = G.remove(0);
286            b = a;
287            //System.out.println("doing " + a.length());
288            a = red.normalform(G, a);
289            bcH = rred.reducedBooleanClosure(G, a);
290            if (bcH.size() > 1) {
291                System.out.println("minGB not bc: bcH size = " + bcH.size());
292                G.add(b); // do not reduce
293            } else {
294                G.addAll(bcH);
295            }
296            el++;
297        }
298        // make monic if possible
299        F = new ArrayList<GenPolynomial<C>>(G.size());
300        for (GenPolynomial<C> p : G) {
301            a = p.monic().abs();
302            if (p.length() != a.length()) {
303                System.out.println("minGB not bc: #p != #a: a = " + a + ", p = " + p);
304                a = p; // dont make monic for now
305            }
306            F.add(a);
307        }
308        G = F;
309
310        /* stratify: collect polynomials with equal leading terms */
311        ExpVector e, f;
312        F = new ArrayList<GenPolynomial<C>>(G.size());
313        for (int i = 0; i < G.size(); i++) {
314            a = G.get(i);
315            if (a == null || a.isZERO()) {
316                continue;
317            }
318            e = a.leadingExpVector();
319            for (int j = i + 1; j < G.size(); j++) {
320                b = G.get(j);
321                if (b == null || b.isZERO()) {
322                    continue;
323                }
324                f = b.leadingExpVector();
325                if (e.equals(f)) {
326                    //System.out.println("minGB e == f: " + a + ", " + b);
327                    a = a.sum(b);
328                    G.set(j, null);
329                }
330            }
331            F.add(a);
332        }
333        G = F;
334
335        /* info on boolean algebra element blocks 
336        Map<C,List<GenPolynomial<C>>> bd = new TreeMap<C,List<GenPolynomial<C>>>();
337        for ( GenPolynomial<C> p : G ) { 
338            C cf = p.leadingBaseCoefficient();
339            cf = cf.idempotent();
340            List<GenPolynomial<C>> block = bd.get( cf );
341            if ( block == null ) {
342               block = new ArrayList<GenPolynomial<C>>();
343            }
344            block.add( p ); 
345            bd.put( cf, block );
346        }
347        System.out.println("\nminGB bd:");
348        for( C k: bd.keySet() ) {
349           System.out.println("\nkey = " + k + ":");
350           System.out.println("val = " + bd.get(k));
351        }
352        System.out.println();
353        */
354        return G;
355    }
356
357}