001/*
002 * $Id: GroebnerBaseF5zSigSeqIter.java 5998 2020-03-17 15:40:05Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.logging.log4j.LogManager;
012import org.apache.logging.log4j.Logger;
013
014import edu.jas.poly.ExpVector;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.structure.RingElem;
017
018
019/**
020 * Groebner Base F5z signature based sequential iterative algorithm. Implements
021 * Groebner bases.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 * 
025 * @see edu.jas.application.GBAlgorithmBuilder
026 * @see edu.jas.gbufd.GBFactory
027 */
028
029public class GroebnerBaseF5zSigSeqIter<C extends RingElem<C>> extends GroebnerBaseSigSeqIter<C> {
030
031
032    private static final Logger logger = LogManager.getLogger(GroebnerBaseF5zSigSeqIter.class);
033
034
035    //private static final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Constructor.
040     */
041    public GroebnerBaseF5zSigSeqIter() {
042        this(new SigReductionSeq<C>());
043    }
044
045
046    /**
047     * Constructor.
048     * @param red Reduction engine
049     */
050    public GroebnerBaseF5zSigSeqIter(SigReductionSeq<C> red) {
051        super(red);
052    }
053
054
055    /**
056     * Top normalform.
057     * @param A polynomial.
058     * @param F polynomial list.
059     * @param G polynomial list.
060     * @return nf(A) with respect to F and G.
061     */
062    @Override
063    SigPoly<C> sigNormalform(List<GenPolynomial<C>> F, List<SigPoly<C>> G, SigPoly<C> A) {
064        return sred.sigSemiNormalform(F, G, A);
065    }
066
067
068    /**
069     * Prune total pair list P.
070     * @param P pair list.
071     * @param syz list of exponent vectors representing syzygies.
072     * @return updated pair list. <b>Note:<b> stores polynomials not only
073     *         indices.
074     */
075    @Override
076    List<SigPair<C>> pruneP(List<SigPair<C>> P, List<ExpVector> syz) {
077        List<SigPair<C>> res = new ArrayList<SigPair<C>>(P.size());
078        for (SigPair<C> p : P) {
079            ExpVector f = p.sigma.leadingExpVector();
080            if (f == null) {
081                continue;
082            }
083            boolean div = false;
084            for (ExpVector e : syz) {
085                if (f.multipleOf(e)) {
086                    div = true;
087                    break;
088                }
089            }
090            if (div) {
091                continue;
092            }
093            res.add(p);
094        }
095        return res;
096    }
097
098
099    /**
100     * Prune pair list of degree d.
101     * @param S pair list.
102     * @param syz list of exponent vectors representing syzygies.
103     * @param done list of treated polynomials.
104     * @param G polynomial with signature list.
105     * @return updated pair list.
106     */
107    @Override
108    List<SigPair<C>> pruneS(List<SigPair<C>> S, List<ExpVector> syz, List<SigPoly<C>> done,
109                    List<SigPoly<C>> G) {
110        List<SigPair<C>> res = new ArrayList<SigPair<C>>(S.size());
111        for (SigPair<C> p : S) {
112            if (p.sigma.isZERO()) {
113                continue;
114            }
115            ExpVector f = p.sigma.leadingExpVector();
116            boolean div = false;
117            for (ExpVector e : syz) {
118                if (f.multipleOf(e)) {
119                    div = true;
120                    break;
121                }
122            }
123            if (div) {
124                continue;
125            }
126            if (p.pi.sigma.isZERO()) {
127                logger.info("pruneS, p.pi.sigma = 0");
128                res.add(p);
129                continue;
130            }
131            ExpVector fi = p.pi.poly.leadingExpVector();
132            ExpVector fj = p.pj.poly.leadingExpVector();
133            ExpVector fu = fi.lcm(fj).subtract(fi);
134            f = p.pi.sigma.leadingExpVector();
135            fu = fu.sum(f);
136            div = false;
137            for (SigPoly<C> q : done) {
138                ExpVector e = q.sigma.leadingExpVector();
139                if (e == null) {
140                    continue;
141                }
142                if (fu.multipleOf(e)) {
143                    if (q.sigma.compareTo(p.pi.sigma) > 0) {
144                        div = true;
145                        break;
146                    }
147                }
148            }
149            if (div) {
150                continue;
151            }
152            res.add(p);
153            logger.debug("added p = " + p.sigma);
154        }
155        return res;
156    }
157
158
159    /**
160     * Initializes syzygy list.
161     * @param F polynomial list.
162     * @param G polynomial with signature list.
163     * @return list of exponent vectors representing syzygies.
164     */
165    @Override
166    List<ExpVector> initializeSyz(List<GenPolynomial<C>> F, List<SigPoly<C>> G) {
167        List<ExpVector> P = new ArrayList<ExpVector>();
168        for (GenPolynomial<C> p : F) {
169            if (p.isZERO()) {
170                continue;
171            }
172            P.add(p.leadingExpVector());
173        }
174        return P;
175    }
176
177
178    /**
179     * Update syzygy list.
180     * @param syz list of exponent vectors representing syzygies.
181     * @param r polynomial. <b>Note:</b> szy is modified to represent updated
182     *            list of exponent vectors.
183     */
184    @Override
185    void updateSyz(List<ExpVector> syz, SigPoly<C> r) {
186        if (r.poly.isZERO() && !r.sigma.isZERO()) {
187            //logger.info("update_syz, sigma = " + r.sigma);
188            syz.add(r.sigma.leadingExpVector());
189        }
190        return;
191    }
192
193}