001/*
002 * $Id: GroebnerBaseSeqIter.java 5869 2018-07-20 15:53:10Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010// import java.util.Collections;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.poly.OrderedPolynomialList;
018import edu.jas.poly.PolyUtil;
019import edu.jas.structure.RingElem;
020
021
022/**
023 * Groebner Base sequential iterative algorithm. Implements Groebner bases and
024 * GB test.
025 * @param <C> coefficient type
026 * @author Heinz Kredel
027 * 
028 * @see edu.jas.application.GBAlgorithmBuilder
029 * @see edu.jas.gbufd.GBFactory
030 */
031
032public class GroebnerBaseSeqIter<C extends RingElem<C>> extends GroebnerBaseAbstract<C> {
033
034
035    private static final Logger logger = LogManager.getLogger(GroebnerBaseSeqIter.class);
036
037
038    private static final boolean debug = logger.isDebugEnabled();
039
040
041    /**
042     * Constructor.
043     */
044    public GroebnerBaseSeqIter() {
045        super();
046    }
047
048
049    /**
050     * Constructor.
051     * @param red Reduction engine
052     */
053    public GroebnerBaseSeqIter(Reduction<C> red) {
054        super(red);
055    }
056
057
058    /**
059     * Constructor.
060     * @param pl pair selection strategy
061     */
062    public GroebnerBaseSeqIter(PairList<C> pl) {
063        super(pl);
064    }
065
066
067    /**
068     * Constructor.
069     * @param red Reduction engine
070     * @param pl pair selection strategy
071     */
072    public GroebnerBaseSeqIter(Reduction<C> red, PairList<C> pl) {
073        super(red, pl);
074    }
075
076
077    /**
078     * Groebner base using pairlist class, iterative algorithm.
079     * @param modv module variable number.
080     * @param F polynomial list.
081     * @return GB(F) a Groebner base of F.
082     */
083    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
084        List<GenPolynomial<C>> G = normalizeZerosOnes(F);
085        G = PolyUtil.<C> monic(G);
086        if (G.size() <= 1) {
087            return G;
088        }
089        // sort, no reverse
090        G = OrderedPolynomialList.<C> sort(G);
091        //no: Collections.reverse(G);
092        logger.info("G-sort = " + G);
093        List<GenPolynomial<C>> Gp = new ArrayList<GenPolynomial<C>>();
094        for (GenPolynomial<C> p : G) {
095            if (debug) {
096                logger.info("p = " + p);
097            }
098            GenPolynomial<C> pp = red.normalform(Gp, p);
099            if (pp.isZERO()) {
100                continue;
101            }
102            Gp = GB(modv, Gp, pp);
103            //System.out.println("GB(Gp+p) = " + Gp);
104            if (Gp.size() > 0) {
105                if (Gp.get(0).isONE()) {
106                    return Gp;
107                }
108            }
109        }
110        return Gp;
111    }
112
113
114    /**
115     * Groebner base using pairlist class.
116     * @param modv module variable number.
117     * @param G polynomial list of a Groebner base.
118     * @param f polynomial.
119     * @return GB(G,f) a Groebner base of G+(f).
120     */
121    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> G, GenPolynomial<C> f) {
122        List<GenPolynomial<C>> F = new ArrayList<GenPolynomial<C>>(G);
123        GenPolynomial<C> g = f.monic();
124        if (F.isEmpty()) {
125            F.add(g);
126            return F;
127        }
128        if (g.isZERO()) {
129            return F;
130        }
131        if (g.isONE()) {
132            F.clear();
133            F.add(g);
134            return F;
135        }
136        GenPolynomialRing<C> ring = F.get(0).ring;
137        if (!ring.coFac.isField()) {
138            throw new IllegalArgumentException("coefficients not from a field");
139        }
140        G = F;
141        PairList<C> pairlist = strategy.create(modv, ring);
142        pairlist.setList(G);
143        G.add(g);
144        pairlist.put(g);
145        logger.info("start " + pairlist);
146
147        Pair<C> pair;
148        GenPolynomial<C> pi, pj, S, H;
149        while (pairlist.hasNext()) {
150            pair = pairlist.removeNext();
151            //logger.debug("pair = " + pair);
152            if (pair == null) {
153                continue;
154            }
155            pi = pair.pi;
156            pj = pair.pj;
157            if ( /*false &&*/debug) {
158                logger.debug("pi    = " + pi);
159                logger.debug("pj    = " + pj);
160            }
161
162            S = red.SPolynomial(pi, pj);
163            if (S.isZERO()) {
164                pair.setZero();
165                continue;
166            }
167            if (debug) {
168                logger.debug("ht(S) = " + S.leadingExpVector());
169            }
170
171            H = red.normalform(G, S);
172            if (debug) {
173                //logger.info("pair = " + pair); 
174                //logger.info("ht(S) = " + S.monic()); //.leadingExpVector() );
175                logger.info("ht(H) = " + H.monic()); //.leadingExpVector() );
176            }
177            if (H.isZERO()) {
178                pair.setZero();
179                continue;
180            }
181            H = H.monic();
182            if (debug) {
183                logger.info("ht(H) = " + H.leadingExpVector());
184            }
185
186            H = H.monic();
187            if (H.isONE()) {
188                G.clear();
189                G.add(H);
190                pairlist.putOne();
191                logger.info("end " + pairlist);
192                return G; // since no threads are activated
193            }
194            if (debug) {
195                logger.info("H = " + H);
196            }
197            if (H.length() > 0) {
198                //l++;
199                G.add(H);
200                pairlist.put(H);
201            }
202        }
203        logger.debug("#sequential list = " + G.size());
204        G = minimalGB(G);
205        logger.info("end " + pairlist);
206        return G;
207    }
208
209}