001 /*
002 * $Id: DReductionSeq.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 import edu.jas.poly.GenSolvablePolynomial;
018
019 import edu.jas.structure.RingElem;
020
021
022 /**
023 * Polynomial D-Reduction sequential use algorithm. Implements normalform.
024 * @param <C> coefficient type
025 * @author Heinz Kredel
026 */
027
028 public class DReductionSeq<C extends RingElem<C>> extends ReductionAbstract<C> implements DReduction<C> {
029
030
031 private static final Logger logger = Logger.getLogger(DReductionSeq.class);
032
033
034 private final boolean debug = logger.isDebugEnabled();
035
036
037 /**
038 * Constructor.
039 */
040 public DReductionSeq() {
041 }
042
043
044 /**
045 * Is top reducible.
046 * @param A polynomial.
047 * @param P polynomial list.
048 * @return true if A is top reducible with respect to P.
049 */
050 //SuppressWarnings("unchecked") // not jet working
051 @Override
052 public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) {
053 if (P == null || P.isEmpty()) {
054 return false;
055 }
056 if (A == null || A.isZERO()) {
057 return false;
058 }
059 boolean mt = false;
060 ExpVector e = A.leadingExpVector();
061 C a = A.leadingBaseCoefficient();
062 for (GenPolynomial<C> p : P) {
063 mt = e.multipleOf(p.leadingExpVector());
064 if (mt) {
065 C b = p.leadingBaseCoefficient();
066 C r = a.remainder(b);
067 mt = r.isZERO();
068 if (mt) {
069 return true;
070 }
071 }
072 }
073 return false;
074 }
075
076
077 /**
078 * Is in Normalform.
079 * @param Ap polynomial.
080 * @param Pp polynomial list.
081 * @return true if Ap is in normalform with respect to Pp.
082 */
083 @SuppressWarnings("unchecked")
084 @Override
085 public boolean isNormalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
086 if (Pp == null || Pp.isEmpty()) {
087 return true;
088 }
089 if (Ap == null || Ap.isZERO()) {
090 return true;
091 }
092 int l;
093 GenPolynomial<C>[] P;
094 synchronized (Pp) {
095 l = Pp.size();
096 P = new GenPolynomial[l];
097 //P = Pp.toArray();
098 for (int i = 0; i < Pp.size(); i++) {
099 P[i] = Pp.get(i);
100 }
101 }
102 ExpVector[] htl = new ExpVector[l];
103 C[] lbc = (C[]) new RingElem[l]; // want <C>
104 GenPolynomial<C>[] p = new GenPolynomial[l];
105 Map.Entry<ExpVector, C> m;
106 int i;
107 int j = 0;
108 for (i = 0; i < l; i++) {
109 p[i] = P[i];
110 m = p[i].leadingMonomial();
111 if (m != null) {
112 p[j] = p[i];
113 htl[j] = m.getKey();
114 lbc[j] = m.getValue();
115 j++;
116 }
117 }
118 l = j;
119 boolean mt = false;
120 Map<ExpVector, C> Am = Ap.getMap();
121 for (ExpVector e : Am.keySet()) {
122 for (i = 0; i < l; i++) {
123 mt = e.multipleOf(htl[i]);
124 if (mt) {
125 C a = Am.get(e);
126 C r = a.remainder(lbc[i]);
127 mt = r.isZERO();
128 if (mt) {
129 return false;
130 }
131 }
132 }
133 }
134 return true;
135 }
136
137
138 /**
139 * Normalform using d-reduction.
140 * @param Ap polynomial.
141 * @param Pp polynomial list.
142 * @return d-nf(Ap) with respect to Pp.
143 */
144 @SuppressWarnings("unchecked")
145 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
146 if (Pp == null || Pp.isEmpty()) {
147 return Ap;
148 }
149 if (Ap == null || Ap.isZERO()) {
150 return Ap;
151 }
152 int l;
153 GenPolynomial<C>[] P;
154 synchronized (Pp) {
155 l = Pp.size();
156 P = (GenPolynomial<C>[]) new GenPolynomial[l];
157 //P = Pp.toArray();
158 for (int i = 0; i < Pp.size(); i++) {
159 P[i] = Pp.get(i).abs();
160 }
161 }
162 //System.out.println("l = " + l);
163 Map.Entry<ExpVector, C> m;
164 ExpVector[] htl = new ExpVector[l];
165 C[] lbc = (C[]) new RingElem[l]; // want <C>
166 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
167 int i;
168 int j = 0;
169 for (i = 0; i < l; i++) {
170 p[i] = P[i];
171 m = p[i].leadingMonomial();
172 if (m != null) {
173 p[j] = p[i];
174 htl[j] = m.getKey();
175 lbc[j] = m.getValue();
176 j++;
177 }
178 }
179 l = j;
180 ExpVector e;
181 C a;
182 C r = null;
183 boolean mt = false;
184 GenPolynomial<C> R = Ap.ring.getZERO();
185 GenPolynomial<C> Q = null;
186 GenPolynomial<C> S = Ap;
187 while (S.length() > 0) {
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 r = a.remainder(lbc[i]);
195 mt = r.isZERO(); // && mt
196 }
197 if (mt)
198 break;
199 }
200 if (!mt) {
201 //logger.debug("irred");
202 R = R.sum(a, e);
203 //S = S.subtract( a, e );
204 S = S.reductum();
205 //System.out.println(" S = " + S);
206 } else {
207 //logger.info("red div = " + e);
208 ExpVector f = e.subtract(htl[i]);
209 C b = a.divide(lbc[i]);
210 R = R.sum(r, e);
211 Q = p[i].multiply(b, f);
212 S = S.reductum().subtract(Q.reductum()); // ok also with reductum
213 }
214 }
215 return R.abs();
216 }
217
218
219 /**
220 * S-Polynomial.
221 * @param Ap polynomial.
222 * @param Bp polynomial.
223 * @return spol(Ap,Bp) the S-polynomial of Ap and Bp.
224 */
225 @Override
226 public GenPolynomial<C> SPolynomial(GenPolynomial<C> Ap, GenPolynomial<C> Bp) {
227 if (logger.isInfoEnabled()) {
228 if (Bp == null || Bp.isZERO()) {
229 return Ap.ring.getZERO();
230 }
231 if (Ap == null || Ap.isZERO()) {
232 return Bp.ring.getZERO();
233 }
234 if (!Ap.ring.equals(Bp.ring)) {
235 logger.error("rings not equal");
236 }
237 }
238 Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
239 Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
240
241 ExpVector e = ma.getKey();
242 ExpVector f = mb.getKey();
243
244 ExpVector g = e.lcm(f);
245 ExpVector e1 = g.subtract(e);
246 ExpVector f1 = g.subtract(f);
247
248 C a = ma.getValue();
249 C b = mb.getValue();
250 C c = a.gcd(b);
251 C m = a.multiply(b);
252 C l = m.divide(c); // = lcm(a,b)
253
254 C a1 = l.divide(a);
255 C b1 = l.divide(b);
256
257 GenPolynomial<C> App = Ap.multiply(a1, e1);
258 GenPolynomial<C> Bpp = Bp.multiply(b1, f1);
259 GenPolynomial<C> Cp = App.subtract(Bpp);
260 return Cp;
261 }
262
263
264 /**
265 * G-Polynomial.
266 * @param Ap polynomial.
267 * @param Bp polynomial.
268 * @return gpol(Ap,Bp) the g-polynomial of Ap and Bp.
269 */
270 public GenPolynomial<C> GPolynomial(GenPolynomial<C> Ap, GenPolynomial<C> Bp) {
271 if (logger.isInfoEnabled()) {
272 if (Bp == null || Bp.isZERO()) {
273 return Ap.ring.getZERO();
274 }
275 if (Ap == null || Ap.isZERO()) {
276 return Bp.ring.getZERO();
277 }
278 if (!Ap.ring.equals(Bp.ring)) {
279 logger.error("rings not equal");
280 }
281 }
282 Map.Entry<ExpVector, C> ma = Ap.leadingMonomial();
283 Map.Entry<ExpVector, C> mb = Bp.leadingMonomial();
284
285 ExpVector e = ma.getKey();
286 ExpVector f = mb.getKey();
287
288 ExpVector g = e.lcm(f);
289 ExpVector e1 = g.subtract(e);
290 ExpVector f1 = g.subtract(f);
291
292 C a = ma.getValue();
293 C b = mb.getValue();
294 C[] c = a.egcd(b);
295
296 //System.out.println("egcd[0] " + c[0]);
297
298 GenPolynomial<C> App = Ap.multiply(c[1], e1);
299 GenPolynomial<C> Bpp = Bp.multiply(c[2], f1);
300 GenPolynomial<C> Cp = App.sum(Bpp);
301 return Cp;
302 }
303
304
305 /**
306 * D-Polynomial with recording.
307 * @param S recording matrix, is modified.
308 * @param i index of Ap in basis list.
309 * @param Ap a polynomial.
310 * @param j index of Bp in basis list.
311 * @param Bp a polynomial.
312 * @return gpol(Ap, Bp), the g-Polynomial for Ap and Bp.
313 */
314 public GenPolynomial<C> GPolynomial(List<GenPolynomial<C>> S, int i, GenPolynomial<C> Ap, int j,
315 GenPolynomial<C> Bp) {
316 throw new UnsupportedOperationException("not jet implemented");
317 }
318
319
320 /**
321 * GB criterium 4. Use only for commutative polynomial rings. This version
322 * works also for d-Groebner bases.
323 * @param A polynomial.
324 * @param B polynomial.
325 * @param e = lcm(ht(A),ht(B))
326 * @return true if the S-polynomial(i,j) is required, else false.
327 */
328 @Override
329 public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B, ExpVector e) {
330 if (logger.isInfoEnabled()) {
331 if (!A.ring.equals(B.ring)) {
332 logger.error("rings equal");
333 }
334 if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
335 logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
336 return true;
337 }
338 }
339 ExpVector ei = A.leadingExpVector();
340 ExpVector ej = B.leadingExpVector();
341 ExpVector g = ei.sum(ej);
342 // boolean t = g == e ;
343 ExpVector h = g.subtract(e);
344 int s = h.signum();
345 if (s == 0) { // disjoint ht
346 C a = A.leadingBaseCoefficient();
347 C b = B.leadingBaseCoefficient();
348 C d = a.gcd(b);
349 if (d.isONE()) { // disjoint hc
350 //System.out.println("d1 = " + d + ", a = " + a + ", b = " + b);
351 return false; // can skip pair
352 }
353 }
354 return true; //! ( s == 0 );
355 }
356
357
358 /**
359 * GB criterium 4. Use only for commutative polynomial rings. This version
360 * works also for d-Groebner bases.
361 * @param A polynomial.
362 * @param B polynomial.
363 * @return true if the S-polynomial(i,j) is required, else false.
364 */
365 @Override
366 public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B) {
367 if (logger.isInfoEnabled()) {
368 if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
369 logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
370 return true;
371 }
372 }
373 ExpVector ei = A.leadingExpVector();
374 ExpVector ej = B.leadingExpVector();
375 ExpVector g = ei.sum(ej);
376 ExpVector e = ei.lcm(ej);
377 // boolean t = g == e ;
378 ExpVector h = g.subtract(e);
379 int s = h.signum();
380 if (s == 0) { // disjoint ht
381 C a = A.leadingBaseCoefficient();
382 C b = B.leadingBaseCoefficient();
383 C d = a.gcd(b);
384 if (d.isONE()) { // disjoint hc
385 return false; // can skip pair
386 }
387 }
388 return true; //! ( s == 0 );
389 }
390
391
392 /**
393 * Normalform with recording.
394 * @param row recording matrix, is modified.
395 * @param Pp a polynomial list for reduction.
396 * @param Ap a polynomial.
397 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
398 */
399 @SuppressWarnings("unchecked")
400 // not jet working
401 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp,
402 GenPolynomial<C> Ap) {
403 if (Pp == null || Pp.isEmpty()) {
404 return Ap;
405 }
406 if (Ap == null || Ap.isZERO()) {
407 return Ap;
408 }
409 throw new UnsupportedOperationException("not jet implemented");
410 /*
411 int l = Pp.size();
412 GenPolynomial<C>[] P = new GenPolynomial[l];
413 synchronized (Pp) {
414 //P = Pp.toArray();
415 for ( int i = 0; i < Pp.size(); i++ ) {
416 P[i] = Pp.get(i);
417 }
418 }
419 ExpVector[] htl = new ExpVector[ l ];
420 Object[] lbc = new Object[ l ]; // want <C>
421 GenPolynomial<C>[] p = new GenPolynomial[ l ];
422 Map.Entry<ExpVector,C> m;
423 int j = 0;
424 int i;
425 for ( i = 0; i < l; i++ ) {
426 p[i] = P[i];
427 m = p[i].leadingMonomial();
428 if ( m != null ) {
429 p[j] = p[i];
430 htl[j] = m.getKey();
431 lbc[j] = m.getValue();
432 j++;
433 }
434 }
435 l = j;
436 ExpVector e;
437 C a;
438 boolean mt = false;
439 GenPolynomial<C> zero = Ap.ring.getZERO();
440 GenPolynomial<C> R = Ap.ring.getZERO();
441
442 GenPolynomial<C> fac = null;
443 // GenPolynomial<C> T = null;
444 GenPolynomial<C> Q = null;
445 GenPolynomial<C> S = Ap;
446 while ( S.length() > 0 ) {
447 m = S.leadingMonomial();
448 e = m.getKey();
449 a = m.getValue();
450 for ( i = 0; i < l; i++ ) {
451 mt = e.multipleOf( htl[i] );
452 if ( mt ) break;
453 }
454 if ( ! mt ) {
455 //logger.debug("irred");
456 R = R.sum( a, e );
457 S = S.subtract( a, e );
458 // System.out.println(" S = " + S);
459 //throw new RuntimeException("Syzygy no GB");
460 } else {
461 e = e.subtract( htl[i] );
462 //logger.info("red div = " + e);
463 C c = (C)lbc[i];
464 a = a.divide( c );
465 Q = p[i].multiply( a, e );
466 S = S.subtract( Q );
467 fac = row.get(i);
468 if ( fac == null ) {
469 fac = zero.sum( a, e );
470 } else {
471 fac = fac.sum( a, e );
472 }
473 row.set(i,fac);
474 }
475 }
476 return R;
477 */
478 }
479
480
481 /**
482 * Irreducible set.
483 * @param Pp polynomial list.
484 * @return a list P of polynomials which are in normalform wrt. P.
485 */
486 @Override
487 public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
488 ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
489 if (Pp == null) {
490 return null;
491 }
492 for (GenPolynomial<C> a : Pp) {
493 if (!a.isZERO()) {
494 P.add(a);
495 }
496 }
497 int l = P.size();
498 if (l <= 1)
499 return P;
500
501 int irr = 0;
502 ExpVector e;
503 ExpVector f;
504 GenPolynomial<C> a;
505 Iterator<GenPolynomial<C>> it;
506 logger.debug("irr = ");
507 while (irr != l) {
508 //it = P.listIterator();
509 //a = P.get(0); //it.next();
510 a = P.remove(0);
511 e = a.leadingExpVector();
512 a = normalform(P, a);
513 logger.debug(String.valueOf(irr));
514 if (a.isZERO()) {
515 l--;
516 if (l <= 1) {
517 return P;
518 }
519 } else {
520 f = a.leadingExpVector();
521 if (e.equals(f)) {
522 irr++;
523 } else {
524 irr = 0;
525 }
526 P.add(a);
527 }
528 }
529 //System.out.println();
530 return P;
531 }
532
533 }