Source code

001/*
002 * $Id: SigReductionSeq.java 5998 2020-03-17 15:40:05Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.Comparator;
010import java.util.List;
011import java.util.Map;
012import java.util.stream.Collectors;
013
014import org.apache.logging.log4j.LogManager;
015import org.apache.logging.log4j.Logger;
016
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.structure.RingElem;
021
022
023/**
024 * Polynomial SigReduction class. Implements common S-Polynomial, normalform
025 * with respect to signatures.
026 * @param <C> coefficient type
027 * @author Heinz Kredel
028 */
029
030public class SigReductionSeq<C extends RingElem<C>> implements SigReduction<C> {
031
032
033    private static final Logger logger = LogManager.getLogger(SigReductionSeq.class);
034
035
036    //private static final boolean debug = logger.isDebugEnabled();
037
038
039    final ReductionAbstract<C> red;
040
041
042    /**
043     * Constructor.
044     */
045    public SigReductionSeq() {
046        red = new ReductionSeq<C>();
047    }
048
049
050    /**
051     * S-Polynomial.
052     * @param A polynomial.
053     * @param B polynomial.
054     * @return spol(A,B) the S-polynomial of A and B.
055     */
056    public GenPolynomial<C> SPolynomial(SigPoly<C> A, SigPoly<C> B) {
057        GenPolynomial<C> s = red.SPolynomial(A.poly, B.poly);
058        return s;
059    }
060
061
062    /**
063     * S-Polynomial factors.
064     * @param A monic polynomial.
065     * @param B monic polynomial.
066     * @return exponent vectors [e,f] such that spol(A,B) = e*a - f*B.
067     */
068    public ExpVector[] SPolynomialExpVectorFactors(SigPoly<C> A, SigPoly<C> B) {
069        Map.Entry<ExpVector, C> ma = A.poly.leadingMonomial();
070        Map.Entry<ExpVector, C> mb = B.poly.leadingMonomial();
071        ExpVector e = ma.getKey();
072        ExpVector f = mb.getKey();
073        ExpVector g = e.lcm(f);
074        ExpVector e1 = g.subtract(e);
075        ExpVector f1 = g.subtract(f);
076        ExpVector[] F = new ExpVector[] { e1, f1 };
077        return F;
078    }
079
080
081    /**
082     * S-Polynomial half.
083     * @param A monic polynomial.
084     * @param B monic polynomial.
085     * @return e*A "half" of an S-polynomial such that spol(A,B) = e*A - f*B.
086     */
087    public GenPolynomial<C> SPolynomialHalf(SigPoly<C> A, SigPoly<C> B) {
088        Map.Entry<ExpVector, C> ma = A.poly.leadingMonomial();
089        Map.Entry<ExpVector, C> mb = B.poly.leadingMonomial();
090        ExpVector e = ma.getKey();
091        ExpVector f = mb.getKey();
092        ExpVector g = e.lcm(f);
093        ExpVector e1 = g.subtract(e);
094        GenPolynomial<C> F = A.poly.multiply(e1);
095        return F;
096    }
097
098
099    /**
100     * S-Polynomial polynomial factors.
101     * @param A monic polynomial.
102     * @param B monic polynomial.
103     * @return polynomials [e,f] such that spol(A,B) = e*a - f*B.
104     */
105    public GenPolynomial<C>[] SPolynomialFactors(SigPoly<C> A, SigPoly<C> B) {
106        ExpVector[] ev = SPolynomialExpVectorFactors(A, B);
107        GenPolynomial<C> e1 = A.poly.ring.valueOf(ev[0]);
108        GenPolynomial<C> f1 = A.poly.ring.valueOf(ev[1]);
109        @SuppressWarnings("unchecked")
110        GenPolynomial<C>[] F = new GenPolynomial[] { e1, f1 };
111        return F;
112    }
113
114
115    /**
116     * Is top reducible. Condition is lt(B) | lt(A) for some B in F or G.
117     * @param A polynomial.
118     * @param F polynomial list.
119     * @param G polynomial list.
120     * @return true if A is top reducible with respect to F and G.
121     */
122    public boolean isSigReducible(List<SigPoly<C>> F, List<SigPoly<C>> G, SigPoly<C> A) {
123        return !isSigNormalform(F, G, A);
124    }
125
126
127    /**
128     * Is in top normalform.
129     * @param A polynomial.
130     * @param F polynomial list.
131     * @param G polynomial list.
132     * @return true if A is in top normalform with respect to F and G.
133     */
134    public boolean isSigNormalform(List<SigPoly<C>> F, List<SigPoly<C>> G, SigPoly<C> A) {
135        if (F.isEmpty() && G.isEmpty()) {
136            return true;
137        }
138        if (A.poly.isZERO()) {
139            return true;
140        }
141        boolean mt = false;
142        for (ExpVector e : A.poly.getMap().keySet()) {
143            for (SigPoly<C> p : F) {
144                ExpVector f = p.poly.leadingExpVector();
145                mt = e.multipleOf(f);
146                if (mt) {
147                    return false;
148                }
149            }
150            for (SigPoly<C> p : G) {
151                if (p.poly.isZERO()) {
152                    continue;
153                }
154                ExpVector f = p.poly.leadingExpVector();
155                mt = e.multipleOf(f);
156                if (mt) {
157                    ExpVector g = e.subtract(f);
158                    GenPolynomial<C> sigma = p.sigma.multiply(g);
159                    if (sigma.leadingExpVector().compareTo(A.sigma.leadingExpVector()) < 0) {
160                        return false;
161                    }
162                    if (sigma.leadingExpVector().compareTo(A.sigma.leadingExpVector()) == 0
163                                    && sigma.leadingBaseCoefficient()
164                                                    .compareTo(A.sigma.leadingBaseCoefficient()) != 0) {
165                        return false;
166                    }
167                }
168            }
169        }
170        return true;
171    }
172
173
174    /**
175     * Is sigma redundant.
176     * @param A polynomial.
177     * @param G polynomial list.
178     * @return true if A is sigma redundant with respect to G.
179     */
180    public boolean isSigRedundant(List<SigPoly<C>> G, SigPoly<C> A) {
181        if (G.isEmpty()) {
182            return false;
183        }
184        ExpVector e = A.sigma.leadingExpVector();
185        if (e == null) {
186            e = A.poly.ring.evzero;
187        }
188        for (SigPoly<C> p : G) {
189            if (p.sigma.isZERO()) {
190                continue;
191            }
192            ExpVector f = p.sigma.leadingExpVector();
193            if (f == null) { // does not happen
194                f = p.poly.ring.evzero;
195            }
196            boolean mt = e.multipleOf(f);
197            if (mt) {
198                ExpVector g = e.subtract(f);
199                ExpVector h = p.poly.leadingExpVector();
200                h = h.sum(g);
201                if (h.compareTo(A.poly.leadingExpVector()) == 0) {
202                    return true;
203                }
204            }
205        }
206        return false;
207    }
208
209
210    /**
211     * Is sigma redundant, alternative algorithm.
212     * @param A polynomial.
213     * @param G polynomial list.
214     * @return true if A is sigma redundant per alternative algorithm with
215     *         respect to G.
216     */
217    public boolean isSigRedundantAlt(List<SigPoly<C>> G, SigPoly<C> A) {
218        if (G.isEmpty()) {
219            return false;
220        }
221        ExpVector e = A.sigma.leadingExpVector();
222        if (e == null) {
223            e = A.poly.ring.evzero;
224        }
225        for (SigPoly<C> p : G) {
226            if (p.sigma.isZERO()) {
227                continue;
228            }
229            ExpVector f = p.sigma.leadingExpVector();
230            if (f == null) { // does not happen
231                f = p.poly.ring.evzero;
232            }
233            boolean mt = e.multipleOf(f);
234            if (mt) {
235                if (p.poly.isZERO()) {
236                    continue;
237                }
238                ExpVector h = p.poly.leadingExpVector();
239                ExpVector g = A.poly.leadingExpVector();
240                if (g.multipleOf(h)) {
241                    return true;
242                }
243            }
244        }
245        return false;
246    }
247
248
249    /**
250     * Top normalform.
251     * @param A polynomial.
252     * @param F polynomial list.
253     * @param G polynomial list.
254     * @return nf(A) with respect to F and G.
255     */
256    public SigPoly<C> sigNormalform(List<GenPolynomial<C>> F, List<SigPoly<C>> G, SigPoly<C> A) {
257        if (F.isEmpty() && G.isEmpty()) {
258            return A;
259        }
260        if (A.poly.isZERO()) {
261            return A;
262        }
263        List<GenPolynomial<C>> ff = F; //polys(F);
264        GenPolynomial<C> a = A.poly;
265        GenPolynomial<C> sigma = A.sigma;
266        GenPolynomialRing<C> ring = a.ring;
267        boolean reduced = true;
268        while (!a.isZERO() && reduced) {
269            reduced = false;
270            a = red.normalform(ff, a);
271            if (a.isZERO()) {
272                continue;
273            }
274            ExpVector e = a.leadingExpVector();
275            for (SigPoly<C> p : G) {
276                if (p.poly.isZERO()) {
277                    continue;
278                }
279                ExpVector f = p.poly.leadingExpVector();
280                boolean mt = e.multipleOf(f);
281                if (mt) {
282                    ExpVector g = e.subtract(f);
283                    C sc = a.leadingBaseCoefficient().divide(p.poly.leadingBaseCoefficient());
284                    GenPolynomial<C> sigup = p.sigma.multiply(sc, g);
285                    ExpVector se = sigma.leadingExpVector();
286                    if (se == null) {
287                        se = ring.evzero;
288                    }
289                    ExpVector sp = sigup.leadingExpVector();
290                    if (sp == null) {
291                        sp = ring.evzero;
292                    }
293                    //logger.info("sigup, sigma  = " + sigup + ", " + sigma);
294                    boolean sigeq = (sigup.compareTo(sigma) < 0)
295                                    || ((sp.compareTo(se) == 0 && (sigup.leadingBaseCoefficient()
296                                                    .compareTo(sigma.leadingBaseCoefficient()) != 0)));
297                    //logger.info("sigup < sigma = " + sigup.compareTo(sigma));
298                    if (sigeq) {
299                        reduced = true;
300                        a = a.subtractMultiple(sc, g, p.poly);
301                        if (sp.invGradCompareTo(se) == 0) {
302                            sigma = sigma.subtract(sigup);
303                        }
304                        if (a.isZERO()) {
305                            break;
306                        }
307                        e = a.leadingExpVector();
308                    } else {
309                        //logger.info("not reduced: a = " + a + ", p = " + p.poly);
310                    }
311                }
312            }
313        }
314        if (!a.isZERO()) {
315            C ac = a.leadingBaseCoefficient();
316            if (!ac.isONE()) {
317                ac = ac.inverse();
318                a = a.multiply(ac);
319                sigma = sigma.multiply(ac);
320            }
321        }
322        return new SigPoly<C>(sigma, a);
323    }
324
325
326    /**
327     * Top semi-complete normalform.
328     * @param A polynomial.
329     * @param F polynomial list.
330     * @param G polynomial list.
331     * @return nf(A) with respect to F and G.
332     */
333    public SigPoly<C> sigSemiNormalform(List<GenPolynomial<C>> F, List<SigPoly<C>> G, SigPoly<C> A) {
334        if (F.isEmpty() && G.isEmpty()) {
335            return A;
336        }
337        if (A.poly.isZERO()) {
338            return A;
339        }
340        List<GenPolynomial<C>> ff = F; //polys(F);
341        GenPolynomial<C> a = A.poly;
342        GenPolynomial<C> sigma = A.sigma;
343        ExpVector esig = sigma.leadingExpVector();
344        if (esig == null) {
345            logger.info("esig = null");
346            //esig = a.ring.evzero;
347        }
348        //GenPolynomialRing<C> ring = a.ring;
349        boolean reduced = true;
350        while (!a.isZERO() && reduced) {
351            reduced = false;
352            a = red.normalform(ff, a);
353            if (a.isZERO()) {
354                continue;
355            }
356            ExpVector e = a.leadingExpVector();
357            for (SigPoly<C> p : G) {
358                if (p.poly.isZERO()) {
359                    continue;
360                }
361                ExpVector f = p.poly.leadingExpVector();
362                boolean mt = e.multipleOf(f);
363                if (mt) {
364                    ExpVector g = e.subtract(f);
365                    C sc = a.leadingBaseCoefficient().divide(p.poly.leadingBaseCoefficient());
366                    GenPolynomial<C> sigup = p.sigma.multiply(sc, g);
367                    ExpVector eup = sigup.leadingExpVector();
368                    if (eup == null) {
369                        logger.info("eup = null");
370                        //eup = a.ring.evzero;
371                        throw new IllegalArgumentException("eup == null: " + sigup);
372                    }
373
374                    //wrong: boolean sigeq = (sigup.compareTo(sigma) < 0);
375                    boolean sigeq = (eup.compareTo(esig) < 0);
376                    if (sigeq) {
377                        //logger.info("reduced: sigup = " + sigup + ", sigma = " + sigma);
378                        reduced = true;
379                        a = a.subtractMultiple(sc, g, p.poly);
380                        if (a.isZERO()) {
381                            break;
382                        }
383                        e = a.leadingExpVector();
384                    } else {
385                        //logger.info("not reduced: a = " + a + ", p = " + p.poly);
386                    }
387                }
388            }
389        }
390        if (!a.isZERO()) {
391            C ac = a.leadingBaseCoefficient();
392            if (!ac.isONE()) {
393                ac = ac.inverse();
394                a = a.multiply(ac);
395            }
396        }
397        return new SigPoly<C>(sigma, a);
398    }
399
400
401    /**
402     * Select polynomials.
403     * @param F list of signature polynomials.
404     * @return the polynomials in F.
405     */
406    public List<GenPolynomial<C>> polys(List<SigPoly<C>> F) {
407        List<GenPolynomial<C>> ff = new ArrayList<GenPolynomial<C>>();
408        for (SigPoly<C> p : F) {
409            if (!p.poly.isZERO()) {
410                ff.add(p.poly);
411            }
412        }
413        return ff;
414    }
415
416
417    /**
418     * Select signatures.
419     * @param F list of signature polynomials.
420     * @return the signatures in F.
421     */
422    public List<GenPolynomial<C>> sigmas(List<SigPair<C>> F) {
423        List<GenPolynomial<C>> ff = new ArrayList<GenPolynomial<C>>();
424        for (SigPair<C> p : F) {
425            ff.add(p.sigma);
426        }
427        return ff;
428    }
429
430
431    /**
432     * Minimal degree of signatures.
433     * @param F list of signature polynomials.
434     * @return the minimal degree of the signatures in F.
435     */
436    public long minimalSigDegree(List<SigPair<C>> F) {
437        long deg = Long.MAX_VALUE;
438        for (SigPair<C> p : F) {
439            //long d = p.sigma.totalDegree();
440            long d = p.sigma.degree();
441            if (d < deg) {
442                deg = d;
443            }
444        }
445        return deg;
446    }
447
448
449    /**
450     * Select signature polynomials of minimal degree and non minimal degree.
451     * @param F list of signature polynomials.
452     * @return [m,p] where m is the list of signature polynomials of F of
453     *         minimal degree and p contains the rest of the signature
454     *         polynomials with non minimal degree.
455     */
456    public List<SigPair<C>>[] minDegSubset(List<SigPair<C>> F) {
457        long mdeg = minimalSigDegree(F);
458        List<SigPair<C>> ff = new ArrayList<SigPair<C>>();
459        List<SigPair<C>> pp = new ArrayList<SigPair<C>>();
460        for (SigPair<C> p : F) {
461            //if (p.sigma.totalDegree() == mdeg) {
462            if (p.sigma.degree() == mdeg) {
463                ff.add(p);
464            } else {
465                pp.add(p);
466            }
467        }
468        @SuppressWarnings("unchecked")
469        List<SigPair<C>>[] P = new List[2];
470        P[0] = ff;
471        P[1] = pp;
472        return P;
473    }
474
475
476    /**
477     * Sort signature polynomials according to the degree its signatures.
478     * @param F list of signature polynomials.
479     * @return list of signature polynomials sorted by degree of sigma.
480     */
481    public List<SigPair<C>> sortSigma(List<SigPair<C>> F) {
482        //Comparator<SigPair<C>> sigcmp = Comparator.comparing(SigPair::getSigma::degree);
483        Comparator<SigPair<C>> sigcmp = Comparator.comparingLong(SigPair::getSigmaDegree);
484        List<SigPair<C>> ff = F.stream().sorted(sigcmp).collect(Collectors.toList());
485        return ff;
486    }
487}