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