001 /*
002 * $Id: Reduction.java 3187 2010-06-16 22:07:38Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.List;
008
009 import java.io.Serializable;
010
011 import edu.jas.poly.ExpVector;
012 import edu.jas.poly.GenPolynomial;
013 import 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
024 public 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 * Is top reducible.
103 * Condition is lt(B) | lt(A) for some B in F.
104 * @param A polynomial.
105 * @param P polynomial list.
106 * @return true if A is top reducible with respect to P.
107 */
108 public boolean isTopReducible(List<GenPolynomial<C>> P,
109 GenPolynomial<C> A);
110
111
112 /**
113 * Is reducible.
114 * @param A polynomial.
115 * @param P polynomial list.
116 * @return true if A is reducible with respect to P.
117 */
118 public boolean isReducible(List<GenPolynomial<C>> P,
119 GenPolynomial<C> A);
120
121
122 /**
123 * Is in Normalform.
124 * @param A polynomial.
125 * @param P polynomial list.
126 * @return true if A is in normalform with respect to P.
127 */
128 public boolean isNormalform(List<GenPolynomial<C>> P,
129 GenPolynomial<C> A);
130
131
132 /**
133 * Is in Normalform.
134 * @param Pp polynomial list.
135 * @return true if each A in Pp is in normalform with respect to Pp\{A}.
136 */
137 public boolean isNormalform( List<GenPolynomial<C>> Pp );
138
139
140 /**
141 * Normalform.
142 * @param A polynomial.
143 * @param P polynomial list.
144 * @return nf(A) with respect to P.
145 */
146 public GenPolynomial<C> normalform(List<GenPolynomial<C>> P,
147 GenPolynomial<C> A);
148
149
150 /**
151 * Normalform Set.
152 * @param Ap polynomial list.
153 * @param Pp polynomial list.
154 * @return list of nf(a) with respect to Pp for all a in Ap.
155 */
156 public List<GenPolynomial<C>> normalform(List<GenPolynomial<C>> Pp,
157 List<GenPolynomial<C>> Ap);
158
159
160 /**
161 * Normalform with recording.
162 * @param row recording matrix, is modified.
163 * @param Pp a polynomial list for reduction.
164 * @param Ap a polynomial.
165 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
166 */
167 public GenPolynomial<C>
168 normalform(List<GenPolynomial<C>> row,
169 List<GenPolynomial<C>> Pp,
170 GenPolynomial<C> Ap);
171
172
173 /**
174 * Irreducible set.
175 * @param Pp polynomial list.
176 * @return a list P of polynomials which are in normalform wrt. P and with ideal(Pp) = ideal(P).
177 */
178 public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp);
179
180
181
182 /**
183 * Is reduction of normal form.
184 * @param row recording matrix, is modified.
185 * @param Pp a polynomial list for reduction.
186 * @param Ap a polynomial.
187 * @param Np nf(Pp,Ap), a normal form of Ap wrt. Pp.
188 * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false.
189 */
190
191 public boolean
192 isReductionNF(List<GenPolynomial<C>> row,
193 List<GenPolynomial<C>> Pp,
194 GenPolynomial<C> Ap,
195 GenPolynomial<C> Np);
196
197 }