001/*
002 * $Id: GroebnerBaseArriSigSeqIter.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 Arri 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 GroebnerBaseArriSigSeqIter<C extends RingElem<C>> extends GroebnerBaseSigSeqIter<C> {
030
031
032    private static final Logger logger = LogManager.getLogger(GroebnerBaseArriSigSeqIter.class);
033
034
035    //private static final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Constructor.
040     */
041    public GroebnerBaseArriSigSeqIter() {
042        this(new SigReductionSeq<C>());
043    }
044
045
046    /**
047     * Constructor.
048     * @param red Reduction engine
049     */
050    public GroebnerBaseArriSigSeqIter(SigReductionSeq<C> red) {
051        super(red);
052    }
053
054
055    /**
056     * S-Polynomial.
057     * @param P pair.
058     * @return spol(A,B) the S-polynomial of the pair (A,B).
059     */
060    @Override
061    GenPolynomial<C> SPolynomial(SigPair<C> P) {
062        return P.pi.poly;
063    }
064
065
066    /**
067     * Pair with signature.
068     * @param A polynomial with signature.
069     * @param B polynomial with signature.
070     * @param G polynomial ith signature list.
071     * @return signature pair according to algorithm.
072     */
073    @Override
074    SigPair<C> newPair(SigPoly<C> A, SigPoly<C> B, List<SigPoly<C>> G) {
075        ExpVector e = A.poly.leadingExpVector().lcm(B.poly.leadingExpVector())
076                        .subtract(A.poly.leadingExpVector());
077        GenPolynomial<C> sp = SPolynomial(A, B);
078        GenPolynomial<C> sig = sp.ring.valueOf(e);
079        return new SigPair<C>(sig, new SigPoly<C>(sig, sp), B, G);
080    }
081
082
083    /**
084     * Pair with signature.
085     * @param s signature for pair.
086     * @param A polynomial with signature.
087     * @param B polynomial with signature.
088     * @param G polynomial ith signature list.
089     * @return signature pair according to algorithm.
090     */
091    @Override
092    SigPair<C> newPair(GenPolynomial<C> s, SigPoly<C> A, SigPoly<C> B, List<SigPoly<C>> G) {
093        GenPolynomial<C> sp = SPolynomial(A, B);
094        return new SigPair<C>(s, new SigPoly<C>(s, sp), B, G);
095    }
096
097
098    /**
099     * Top normalform.
100     * @param A polynomial.
101     * @param F polynomial list.
102     * @param G polynomial list.
103     * @return nf(A) with respect to F and G.
104     */
105    @Override
106    SigPoly<C> sigNormalform(List<GenPolynomial<C>> F, List<SigPoly<C>> G, SigPoly<C> A) {
107        return sred.sigSemiNormalform(F, G, A);
108    }
109
110
111    /**
112     * Prune total pair list P.
113     * @param P pair list.
114     * @param syz list of exponent vectors representing syzygies.
115     * @return updated pair list.
116     */
117    @Override
118    List<SigPair<C>> pruneP(List<SigPair<C>> P, List<ExpVector> syz) {
119        List<SigPair<C>> res = new ArrayList<SigPair<C>>(P.size());
120        for (SigPair<C> p : P) {
121            ExpVector f = p.sigma.leadingExpVector();
122            if (f == null) {
123                continue;
124            }
125            boolean div = false;
126            for (ExpVector e : syz) {
127                if (f.multipleOf(e)) {
128                    div = true;
129                    break;
130                }
131            }
132            if (div) {
133                continue;
134            }
135            res.add(p);
136        }
137        return res;
138    }
139
140
141    /**
142     * Prune pair list of degree d.
143     * @param S pair list.
144     * @param syz list of exponent vectors representing syzygies.
145     * @param done list of treated polynomials.
146     * @param G polynomial with signature list.
147     * @return updated pair list.
148     */
149    @Override
150    List<SigPair<C>> pruneS(List<SigPair<C>> S, List<ExpVector> syz, List<SigPoly<C>> done,
151                    List<SigPoly<C>> G) {
152        List<SigPair<C>> res = new ArrayList<SigPair<C>>(S.size());
153        for (SigPair<C> p : S) {
154            ExpVector f = p.sigma.leadingExpVector();
155            if (f == null) {
156                continue;
157            }
158            boolean div = false;
159            for (ExpVector e : syz) {
160                if (f.multipleOf(e)) {
161                    div = true;
162                    break;
163                }
164            }
165            if (div) {
166                continue;
167            }
168            div = false;
169            for (SigPair<C> q : S) {
170                if (p.sigma.equals(q.sigma)) {
171                    if (p.pi.poly.compareTo(q.pi.poly) > 0) {
172                        div = true;
173                        break;
174                    }
175                }
176            }
177            if (div) {
178                continue;
179            }
180            div = false;
181            for (SigPoly<C> q : done) {
182                ExpVector e = q.sigma.leadingExpVector();
183                if (e == null) {
184                    continue;
185                }
186                if (f.multipleOf(e)) {
187                    ExpVector g = f.subtract(e);
188                    ExpVector f1 = g.sum(q.poly.leadingExpVector());
189                    ExpVector e1 = p.pi.poly.leadingExpVector();
190                    if (e1 == null) {
191                        continue;
192                    }
193                    if (f1.compareTo(e1) < 0) {
194                        div = true;
195                        break;
196                    }
197                }
198            }
199            if (div) {
200                continue;
201            }
202            res.add(p);
203            logger.debug("added p = " + p.sigma);
204        }
205        return res;
206    }
207
208
209    /**
210     * Initializes syzygy list.
211     * @param F polynomial list.
212     * @param G polynomial with signature list.
213     * @return list of exponent vectors representing syzygies.
214     */
215    @Override
216    List<ExpVector> initializeSyz(List<GenPolynomial<C>> F, List<SigPoly<C>> G) {
217        List<ExpVector> P = new ArrayList<ExpVector>();
218        for (GenPolynomial<C> p : F) {
219            if (p.isZERO()) {
220                continue;
221            }
222            P.add(p.leadingExpVector());
223        }
224        return P;
225    }
226
227
228    /**
229     * Update syzygy list.
230     * @param syz list of exponent vectors representing syzygies.
231     * @param r polynomial. <b>Note:</b> szy is modified to represent updated
232     *            list of exponent vectors.
233     */
234    @Override
235    void updateSyz(List<ExpVector> syz, SigPoly<C> r) {
236        if (r.poly.isZERO() && !r.sigma.isZERO()) {
237            syz.add(r.sigma.leadingExpVector());
238        }
239        return;
240    }
241
242}