Source code

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