001 /*
002 * $Id: EReductionSeq.java 3288 2010-08-25 21:46:14Z kredel $
003 */
004
005 package edu.jas.gb;
006
007
008 import java.util.ArrayList;
009 import java.util.Iterator;
010 import java.util.List;
011 import java.util.Map;
012
013 import org.apache.log4j.Logger;
014
015 import edu.jas.poly.ExpVector;
016 import edu.jas.poly.GenPolynomial;
017
018 import edu.jas.structure.RingElem;
019
020
021 /**
022 * Polynomial E-Reduction sequential use algorithm. Implements normalform.
023 * @param <C> coefficient type
024 * @author Heinz Kredel
025 */
026
027 public class EReductionSeq<C extends RingElem<C>> extends DReductionSeq<C> implements EReduction<C> {
028
029
030 private static final Logger logger = Logger.getLogger(DReductionSeq.class);
031
032
033 /**
034 * Constructor.
035 */
036 public EReductionSeq() {
037 }
038
039
040 /**
041 * Is top reducible.
042 * @param A polynomial.
043 * @param P polynomial list.
044 * @return true if A is top reducible with respect to P.
045 */
046 //SuppressWarnings("unchecked") // not jet working
047 @Override
048 public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) {
049 if (P == null || P.isEmpty()) {
050 return false;
051 }
052 if (A == null || A.isZERO()) {
053 return false;
054 }
055 boolean mt = false;
056 ExpVector e = A.leadingExpVector();
057 C a = A.leadingBaseCoefficient();
058 for (GenPolynomial<C> p : P) {
059 mt = e.multipleOf(p.leadingExpVector());
060 if (mt) {
061 C b = p.leadingBaseCoefficient();
062 C r = a.remainder(b);
063 mt = !r.equals(a);
064 if (mt) {
065 return true;
066 }
067 }
068 }
069 return false;
070 }
071
072
073 /**
074 * Is in Normalform.
075 * @param Ap polynomial.
076 * @param Pp polynomial list.
077 * @return true if Ap is in normalform with respect to Pp.
078 */
079 @SuppressWarnings("unchecked")
080 @Override
081 public boolean isNormalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
082 if (Pp == null || Pp.isEmpty()) {
083 return true;
084 }
085 if (Ap == null || Ap.isZERO()) {
086 return true;
087 }
088 int l;
089 GenPolynomial<C>[] P;
090 synchronized (Pp) {
091 l = Pp.size();
092 P = new GenPolynomial[l];
093 //P = Pp.toArray();
094 for (int i = 0; i < Pp.size(); i++) {
095 P[i] = Pp.get(i);
096 }
097 }
098 ExpVector[] htl = new ExpVector[l];
099 C[] lbc = (C[]) new RingElem[l]; // want <C>
100 GenPolynomial<C>[] p = new GenPolynomial[l];
101 Map.Entry<ExpVector, C> m;
102 int i;
103 int j = 0;
104 for (i = 0; i < l; i++) {
105 p[i] = P[i];
106 m = p[i].leadingMonomial();
107 if (m != null) {
108 p[j] = p[i];
109 htl[j] = m.getKey();
110 lbc[j] = m.getValue();
111 j++;
112 }
113 }
114 l = j;
115 boolean mt = false;
116 Map<ExpVector, C> Am = Ap.getMap();
117 for (ExpVector e : Am.keySet()) {
118 for (i = 0; i < l; i++) {
119 mt = e.multipleOf(htl[i]);
120 if (mt) {
121 C a = Am.get(e);
122 C r = a.remainder(lbc[i]);
123 mt = !r.equals(a);
124 if (mt) {
125 return false;
126 }
127 }
128 }
129 }
130 return true;
131 }
132
133
134 /**
135 * Normalform using e-reduction.
136 * @param Ap polynomial.
137 * @param Pp polynomial list.
138 * @return e-nf(Ap) with respect to Pp.
139 */
140 @SuppressWarnings("unchecked")
141 @Override
142 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
143 if (Pp == null || Pp.isEmpty()) {
144 return Ap;
145 }
146 if (Ap == null || Ap.isZERO()) {
147 return Ap;
148 }
149 int l;
150 GenPolynomial<C>[] P;
151 synchronized (Pp) {
152 l = Pp.size();
153 P = (GenPolynomial<C>[]) new GenPolynomial[l];
154 //P = Pp.toArray();
155 for (int i = 0; i < Pp.size(); i++) {
156 P[i] = Pp.get(i).abs();
157 }
158 }
159 Map.Entry<ExpVector, C> m;
160 ExpVector[] htl = new ExpVector[l];
161 C[] lbc = (C[]) new RingElem[l]; // want <C>
162 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
163 int i;
164 int j = 0;
165 for (i = 0; i < l; i++) {
166 p[i] = P[i];
167 m = p[i].leadingMonomial();
168 if (m != null) {
169 p[j] = p[i];
170 htl[j] = m.getKey();
171 lbc[j] = m.getValue();
172 j++;
173 }
174 }
175 l = j;
176 ExpVector e = null;
177 ExpVector f = null;
178 C a = null;
179 C b = null;
180 C r = null;
181 GenPolynomial<C> R = Ap.ring.getZERO();
182 GenPolynomial<C> T = Ap.ring.getZERO();
183 GenPolynomial<C> Q = null;
184 GenPolynomial<C> S = Ap;
185 try { // required to avoid a compiler error in the while loop
186 while (S.length() > 0) {
187 boolean mt = false;
188 m = S.leadingMonomial();
189 e = m.getKey();
190 a = m.getValue();
191 for (i = 0; i < l; i++) {
192 mt = e.multipleOf(htl[i]);
193 if (mt) {
194 f = e.subtract(htl[i]);
195 //logger.info("red div = " + f);
196 r = a.remainder(lbc[i]);
197 b = a.divide(lbc[i]);
198 if (f == null) { // compiler produced this case
199 System.out.println("f = null: " + e + ", " + htl[i]);
200 Q = p[i].multiply(b);
201 } else {
202 Q = p[i].multiply(b, f);
203 }
204 S = S.subtract(Q); // ok also with reductum
205 //System.out.println(" r = " + r);
206 a = r;
207 if (r.isZERO()) {
208 break;
209 }
210 }
211 }
212 if (!a.isZERO()) { //! mt ) {
213 //logger.debug("irred");
214 R = R.sum(a, e);
215 //S = S.subtract( a, e );
216 S = S.reductum();
217 }
218 //System.out.println(" R = " + R);
219 //System.out.println(" S = " + S);
220 }
221 } catch (Exception ex) {
222 System.out.println("R = " + R);
223 System.out.println("S = " + S);
224 System.out.println("f = " + f + ", " + e + ", " + htl[i]);
225 System.out.println("a = " + a + ", " + b + ", " + r + ", " + lbc[i]);
226 //throw ex;
227 return T;
228 }
229 return R.abs();
230 }
231
232
233 /**
234 * Normalform with recording.
235 * @param row recording matrix, is modified.
236 * @param Pp a polynomial list for reduction.
237 * @param Ap a polynomial.
238 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
239 */
240 @Override
241 @SuppressWarnings("unchecked")
242 // not jet working
243 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
244 GenPolynomial<C> Ap) {
245 if (Pp == null || Pp.isEmpty()) {
246 return Ap;
247 }
248 if (Ap == null || Ap.isZERO()) {
249 return Ap;
250 }
251 throw new UnsupportedOperationException("not jet implemented");
252 /*
253 int l = Pp.size();
254 GenPolynomial<C>[] P = new GenPolynomial[l];
255 synchronized (Pp) {
256 //P = Pp.toArray();
257 for ( int i = 0; i < Pp.size(); i++ ) {
258 P[i] = Pp.get(i);
259 }
260 }
261 ExpVector[] htl = new ExpVector[ l ];
262 Object[] lbc = new Object[ l ]; // want <C>
263 GenPolynomial<C>[] p = new GenPolynomial[ l ];
264 Map.Entry<ExpVector,C> m;
265 int j = 0;
266 int i;
267 for ( i = 0; i < l; i++ ) {
268 p[i] = P[i];
269 m = p[i].leadingMonomial();
270 if ( m != null ) {
271 p[j] = p[i];
272 htl[j] = m.getKey();
273 lbc[j] = m.getValue();
274 j++;
275 }
276 }
277 l = j;
278 ExpVector e;
279 C a;
280 boolean mt = false;
281 GenPolynomial<C> zero = Ap.ring.getZERO();
282 GenPolynomial<C> R = Ap.ring.getZERO();
283
284 GenPolynomial<C> fac = null;
285 // GenPolynomial<C> T = null;
286 GenPolynomial<C> Q = null;
287 GenPolynomial<C> S = Ap;
288 while ( S.length() > 0 ) {
289 m = S.leadingMonomial();
290 e = m.getKey();
291 a = m.getValue();
292 for ( i = 0; i < l; i++ ) {
293 mt = e.multipleOf( htl[i] );
294 if ( mt ) break;
295 }
296 if ( ! mt ) {
297 //logger.debug("irred");
298 R = R.sum( a, e );
299 S = S.subtract( a, e );
300 // System.out.println(" S = " + S);
301 //throw new RuntimeException("Syzygy no GB");
302 } else {
303 e = e.subtract( htl[i] );
304 //logger.info("red div = " + e);
305 C c = (C)lbc[i];
306 a = a.divide( c );
307 Q = p[i].multiply( a, e );
308 S = S.subtract( Q );
309 fac = row.get(i);
310 if ( fac == null ) {
311 fac = zero.sum( a, e );
312 } else {
313 fac = fac.sum( a, e );
314 }
315 row.set(i,fac);
316 }
317 }
318 return R;
319 */
320 }
321
322
323 /**
324 * Irreducible set.
325 * @param Pp polynomial list.
326 * @return a list P of polynomials which are in normalform wrt. P.
327 */
328 @Override
329 public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
330 ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
331 if (Pp == null) {
332 return null;
333 }
334 for (GenPolynomial<C> a : Pp) {
335 if (!a.isZERO()) {
336 P.add(a);
337 }
338 }
339 int l = P.size();
340 if (l <= 1)
341 return P;
342
343 int irr = 0;
344 ExpVector e;
345 ExpVector f;
346 C c;
347 C d;
348 GenPolynomial<C> a;
349 Iterator<GenPolynomial<C>> it;
350 logger.debug("irr = ");
351 while (irr != l) {
352 //it = P.listIterator();
353 //a = P.get(0); //it.next();
354 a = P.remove(0);
355 e = a.leadingExpVector();
356 c = a.leadingBaseCoefficient();
357 a = normalform(P, a);
358 logger.debug(String.valueOf(irr));
359 if (a.isZERO()) {
360 l--;
361 if (l <= 1) {
362 return P;
363 }
364 } else {
365 f = a.leadingExpVector();
366 d = a.leadingBaseCoefficient();
367 if (e.equals(f) && c.equals(d)) {
368 irr++;
369 } else {
370 irr = 0;
371 }
372 P.add(a);
373 }
374 }
375 //System.out.println();
376 return P;
377 }
378
379 }