001/*
002 * $Id: GroebnerBaseGGVSigSeqIter.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 GGV 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 GroebnerBaseGGVSigSeqIter<C extends RingElem<C>> extends GroebnerBaseSigSeqIter<C> {
030
031
032    private static final Logger logger = LogManager.getLogger(GroebnerBaseGGVSigSeqIter.class);
033
034
035    //private static final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Constructor.
040     */
041    public GroebnerBaseGGVSigSeqIter() {
042        this(new SigReductionSeq<C>());
043    }
044
045
046    /**
047     * Constructor.
048     * @param red Reduction engine
049     */
050    public GroebnerBaseGGVSigSeqIter(SigReductionSeq<C> red) {
051        super(red);
052    }
053
054
055    /**
056     * S-Polynomial.
057     * @param A polynomial.
058     * @param B polynomial.
059     * @return spol(A,B) the S-polynomial of A and B.
060     */
061    @Override
062    GenPolynomial<C> SPolynomial(SigPoly<C> A, SigPoly<C> B) {
063        return sred.SPolynomialHalf(A, B);
064    }
065
066
067    /**
068     * Prune total pair list P.
069     * @param P pair list.
070     * @param syz list of exponent vectors representing syzygies.
071     * @return updated pair list.
072     */
073    @Override
074    List<SigPair<C>> pruneP(List<SigPair<C>> P, List<ExpVector> syz) {
075        List<SigPair<C>> res = new ArrayList<SigPair<C>>(P.size());
076        for (SigPair<C> p : P) {
077            ExpVector f = p.sigma.leadingExpVector();
078            if (f == null) {
079                continue;
080            }
081            boolean div = false;
082            for (ExpVector e : syz) {
083                if (f.multipleOf(e)) {
084                    div = true;
085                    break;
086                }
087            }
088            if (div) {
089                continue;
090            }
091            res.add(p);
092        }
093        return res;
094    }
095
096
097    /**
098     * Prune pair list of degree d.
099     * @param S pair list.
100     * @param syz list of exponent vectors representing syzygies.
101     * @param done list of treated polynomials.
102     * @param G polynomial with signature list.
103     * @return updated pair list.
104     */
105    @Override
106    List<SigPair<C>> pruneS(List<SigPair<C>> S, List<ExpVector> syz, List<SigPoly<C>> done,
107                    List<SigPoly<C>> G) {
108        List<SigPair<C>> res = new ArrayList<SigPair<C>>(S.size());
109        for (SigPair<C> p : S) {
110            ExpVector f = p.sigma.leadingExpVector();
111            if (f == null) {
112                continue;
113            }
114            boolean div = false;
115            for (ExpVector e : syz) {
116                if (f.multipleOf(e)) {
117                    div = true;
118                    break;
119                }
120            }
121            if (div) {
122                continue;
123            }
124            div = false;
125            for (SigPair<C> q : S) {
126                if (f.equals(q.sigma.leadingExpVector())) {
127                    if (p.pi.poly.compareTo(q.pi.poly) < 0) {
128                        div = true;
129                        break;
130                    }
131                }
132            }
133            if (div) {
134                continue;
135            }
136            div = false;
137            for (SigPair<C> q : res) {
138                if (f.equals(q.sigma.leadingExpVector())) {
139                    div = true;
140                    break;
141                }
142            }
143            if (div) {
144                continue;
145            }
146            res.add(p);
147            logger.debug("added p = " + p.sigma);
148        }
149        return res;
150    }
151
152
153    /**
154     * Initializes syzygy list.
155     * @param F polynomial list.
156     * @param G polynomial with signature list.
157     * @return list of exponent vectors representing syzygies.
158     */
159    @Override
160    List<ExpVector> initializeSyz(List<GenPolynomial<C>> F, List<SigPoly<C>> G) {
161        List<ExpVector> P = new ArrayList<ExpVector>();
162        for (GenPolynomial<C> p : F) {
163            if (p.isZERO()) {
164                continue;
165            }
166            P.add(p.leadingExpVector());
167        }
168        return P;
169    }
170
171
172    /**
173     * Update syzygy list.
174     * @param syz list of exponent vectors representing syzygies.
175     * @param r polynomial. <b>Note:</b> szy is modified to represent updated
176     *            list of exponent vectors.
177     */
178    @Override
179    void updateSyz(List<ExpVector> syz, SigPoly<C> r) {
180        if (r.poly.isZERO() && !r.sigma.isZERO()) {
181            syz.add(r.sigma.leadingExpVector());
182        }
183        return;
184    }
185
186}