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