001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.io.Serializable;
009import java.util.List;
010
011import edu.jas.poly.ExpVector;
012import edu.jas.poly.GenPolynomial;
013import edu.jas.structure.RingElem;
014
015
016/**
017 * Polynomial Reduction interface. Defines S-Polynomial, normalform, criterion
018 * 4, module criterion and irreducible set.
019 * @param <C> coefficient type
020 * @author Heinz Kredel
021 */
022
023public interface Reduction<C extends RingElem<C>> extends Serializable {
024
025
026    /**
027     * S-Polynomial.
028     * @param Ap polynomial.
029     * @param Bp polynomial.
030     * @return spol(Ap,Bp) the S-polynomial of Ap and Bp.
031     */
032    public GenPolynomial<C> SPolynomial(GenPolynomial<C> Ap, GenPolynomial<C> Bp);
033
034
035    /**
036     * S-Polynomial with recording.
037     * @param S recording matrix, is modified.
038     * @param i index of Ap in basis list.
039     * @param Ap a polynomial.
040     * @param j index of Bp in basis list.
041     * @param Bp a polynomial.
042     * @return Spol(Ap, Bp), the S-Polynomial for Ap and Bp.
043     */
044    public GenPolynomial<C> SPolynomial(List<GenPolynomial<C>> S, int i, GenPolynomial<C> Ap, int j,
045                    GenPolynomial<C> Bp);
046
047
048    /**
049     * Module criterium.
050     * @param modv number of module variables.
051     * @param A polynomial.
052     * @param B polynomial.
053     * @return true if the module S-polynomial(i,j) is required.
054     */
055    public boolean moduleCriterion(int modv, GenPolynomial<C> A, GenPolynomial<C> B);
056
057
058    /**
059     * Module criterium.
060     * @param modv number of module variables.
061     * @param ei ExpVector.
062     * @param ej ExpVector.
063     * @return true if the module S-polynomial(i,j) is required.
064     */
065    public boolean moduleCriterion(int modv, ExpVector ei, ExpVector ej);
066
067
068    /**
069     * GB criterium 4. Use only for commutative polynomial rings.
070     * @param A polynomial.
071     * @param B polynomial.
072     * @param e = lcm(ht(A),ht(B))
073     * @return true if the S-polynomial(i,j) is required, else false.
074     */
075    public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B, ExpVector e);
076
077
078    /**
079     * GB criterium 4. Use only for commutative polynomial rings.
080     * @param A polynomial.
081     * @param B polynomial.
082     * @return true if the S-polynomial(i,j) is required, else false.
083     */
084    public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B);
085
086
087    /**
088     * GB criterium 4.
089     * @param ei exponent vector.
090     * @param ej exponent vector.
091     * @param e = lcm(ei,ej)
092     * @return true if the S-polynomial(i,j) is required, else false.
093     */
094    public boolean criterion4(ExpVector ei, ExpVector ej, ExpVector e);
095
096
097    /**
098     * Is top reducible. Condition is lt(B) | lt(A) for some B in F.
099     * @param A polynomial.
100     * @param P polynomial list.
101     * @return true if A is top reducible with respect to P.
102     */
103    public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A);
104
105
106    /**
107     * Is reducible.
108     * @param A polynomial.
109     * @param P polynomial list.
110     * @return true if A is reducible with respect to P.
111     */
112    public boolean isReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A);
113
114
115    /**
116     * Is in Normalform.
117     * @param A polynomial.
118     * @param P polynomial list.
119     * @return true if A is in normalform with respect to P.
120     */
121    public boolean isNormalform(List<GenPolynomial<C>> P, GenPolynomial<C> A);
122
123
124    /**
125     * Is in Normalform.
126     * @param Pp polynomial list.
127     * @return true if each A in Pp is in normalform with respect to Pp\{A}.
128     */
129    public boolean isNormalform(List<GenPolynomial<C>> Pp);
130
131
132    /**
133     * Normalform.
134     * @param A polynomial.
135     * @param P polynomial list.
136     * @return nf(A) with respect to P.
137     */
138    public GenPolynomial<C> normalform(List<GenPolynomial<C>> P, GenPolynomial<C> A);
139
140
141    /**
142     * Normalform Set.
143     * @param Ap polynomial list.
144     * @param Pp polynomial list.
145     * @return list of nf(a) with respect to Pp for all a in Ap.
146     */
147    public List<GenPolynomial<C>> normalform(List<GenPolynomial<C>> Pp, List<GenPolynomial<C>> Ap);
148
149
150    /**
151     * Normalform with recording.
152     * @param row recording matrix, is modified.
153     * @param Pp a polynomial list for reduction.
154     * @param Ap a polynomial.
155     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
156     */
157    public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
158                    GenPolynomial<C> Ap);
159
160
161    /**
162     * Irreducible set.
163     * @param Pp polynomial list.
164     * @return a list P of polynomials which are in normalform wrt. P and with
165     *         ideal(Pp) = ideal(P).
166     */
167    public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp);
168
169
170    /**
171     * Is reduction of normal form.
172     * @param row recording matrix, is modified.
173     * @param Pp a polynomial list for reduction.
174     * @param Ap a polynomial.
175     * @param Np nf(Pp,Ap), a normal form of Ap wrt. Pp.
176     * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false.
177     */
178
179    public boolean isReductionNF(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap,
180                    GenPolynomial<C> Np);
181
182}