001/*
002 * $Id: DGroebnerBaseSeq.java 4099 2012-08-12 18:49:36Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.ListIterator;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.poly.GenPolynomial;
015import edu.jas.structure.RingElem;
016
017
018/**
019 * D-Groebner Base sequential algorithm. Implements D-Groebner bases and GB
020 * test. <b>Note:</b> Minimal reduced GBs are not unique. see BWK, section 10.1.
021 * @param <C> coefficient type
022 * @author Heinz Kredel
023 */
024
025public class DGroebnerBaseSeq<C extends RingElem<C>> extends GroebnerBaseAbstract<C> {
026
027
028    private static final Logger logger = Logger.getLogger(DGroebnerBaseSeq.class);
029
030
031    private final boolean debug = logger.isDebugEnabled();
032
033
034    /**
035     * Reduction engine.
036     */
037    protected DReduction<C> dred; // shadow super.red ??
038
039
040    /**
041     * Constructor.
042     */
043    public DGroebnerBaseSeq() {
044        this(new DReductionSeq<C>());
045    }
046
047
048    /**
049     * Constructor.
050     * @param dred D-Reduction engine
051     */
052    public DGroebnerBaseSeq(DReduction<C> dred) {
053        super(dred);
054        this.dred = dred;
055        assert this.dred == super.red;
056    }
057
058
059    /**
060     * D-Groebner base test.
061     * @param modv module variable number.
062     * @param F polynomial list.
063     * @return true, if F is a D-Groebner base, else false.
064     */
065    @Override
066    public boolean isGB(int modv, List<GenPolynomial<C>> F) {
067        GenPolynomial<C> pi, pj, s, d;
068        for (int i = 0; i < F.size(); i++) {
069            pi = F.get(i);
070            for (int j = i + 1; j < F.size(); j++) {
071                pj = F.get(j);
072                if (!red.moduleCriterion(modv, pi, pj)) {
073                    continue;
074                }
075                d = dred.GPolynomial(pi, pj);
076                if (!d.isZERO()) {
077                    // better check for top reduction only
078                    d = red.normalform(F, d);
079                }
080                if (!d.isZERO()) {
081                    System.out.println("d-pol(" + i + "," + j + ") != 0: " + d);
082                    return false;
083                }
084                // works ok
085                if (!red.criterion4(pi, pj)) {
086                    continue;
087                }
088                s = red.SPolynomial(pi, pj);
089                if (!s.isZERO()) {
090                    s = red.normalform(F, s);
091                }
092                if (!s.isZERO()) {
093                    System.out.println("s-pol(" + i + "," + j + ") != 0: " + s);
094                    return false;
095                }
096            }
097        }
098        return true;
099    }
100
101
102    /**
103     * D-Groebner base using pairlist class.
104     * @param modv module variable number.
105     * @param F polynomial list.
106     * @return GB(F) a D-Groebner base of F.
107     */
108    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
109        GenPolynomial<C> p;
110        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
111        OrderedDPairlist<C> pairlist = null;
112        int l = F.size();
113        ListIterator<GenPolynomial<C>> it = F.listIterator();
114        while (it.hasNext()) {
115            p = it.next();
116            if (!p.isZERO()) {
117                p = p.abs(); // not monic
118                if (p.isONE()) {
119                    G.clear();
120                    G.add(p);
121                    return G; // since no threads are activated
122                }
123                G.add(p); //G.add( 0, p ); //reverse list
124                if (pairlist == null) {
125                    pairlist = new OrderedDPairlist<C>(modv, p.ring);
126                }
127                // putOne not required
128                pairlist.put(p);
129            } else {
130                l--;
131            }
132        }
133        if (l <= 1) {
134            return G; // since no threads are activated
135        }
136
137        Pair<C> pair;
138        GenPolynomial<C> pi;
139        GenPolynomial<C> pj;
140        GenPolynomial<C> S;
141        GenPolynomial<C> D;
142        GenPolynomial<C> H;
143        //int len = G.size();
144        //System.out.println("len = " + len);
145        while (pairlist.hasNext()) {
146            pair = pairlist.removeNext();
147            //System.out.println("pair = " + pair);
148            if (pair == null)
149                continue;
150
151            pi = pair.pi;
152            pj = pair.pj;
153            if (debug) {
154                logger.debug("pi    = " + pi);
155                logger.debug("pj    = " + pj);
156            }
157
158            // D-polynomial case ----------------------
159            D = dred.GPolynomial(pi, pj);
160            //System.out.println("D_d = " + D);
161            if (!D.isZERO() && !red.isTopReducible(G, D)) {
162                H = red.normalform(G, D);
163                if (H.isONE()) {
164                    G.clear();
165                    G.add(H);
166                    return G; // since no threads are activated
167                }
168                if (!H.isZERO()) {
169                    logger.info("Dred = " + H);
170                    l++;
171                    G.add(H);
172                    pairlist.put(H);
173                }
174            }
175
176            // S-polynomial case -----------------------
177            if (pair.getUseCriterion3() && pair.getUseCriterion4()) {
178                S = red.SPolynomial(pi, pj);
179                //System.out.println("S_d = " + S);
180                if (S.isZERO()) {
181                    pair.setZero();
182                    continue;
183                }
184                if (logger.isDebugEnabled()) {
185                    logger.debug("ht(S) = " + S.leadingExpVector());
186                }
187
188                H = red.normalform(G, S);
189                if (H.isZERO()) {
190                    pair.setZero();
191                    continue;
192                }
193                if (logger.isDebugEnabled()) {
194                    logger.debug("ht(H) = " + H.leadingExpVector());
195                }
196
197                if (H.isONE()) {
198                    G.clear();
199                    G.add(H);
200                    return G; // since no threads are activated
201                }
202                if (logger.isDebugEnabled()) {
203                    logger.debug("H = " + H);
204                }
205                if (!H.isZERO()) {
206                    logger.info("Sred = " + H);
207                    //len = G.size();
208                    l++;
209                    G.add(H);
210                    pairlist.put(H);
211                }
212            }
213        }
214        logger.debug("#sequential list = " + G.size());
215        G = minimalGB(G);
216        logger.info("" + pairlist);
217        return G;
218    }
219
220}