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