001 /*
002 * $Id: RReductionSeq.java 3423 2010-12-24 10:56:50Z kredel $
003 */
004
005 package edu.jas.gbufd;
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.gb.ReductionAbstract;
016 import edu.jas.poly.ExpVector;
017 import edu.jas.poly.GenPolynomial;
018 import edu.jas.poly.GenSolvablePolynomial;
019
020 import edu.jas.structure.RegularRingElem;
021
022
023 /**
024 * Polynomial Regular ring Reduction sequential use algorithm. Implements
025 * normalform and boolean closure stuff.
026 * @param <C> coefficient type
027 * @author Heinz Kredel
028 */
029
030 public class RReductionSeq<C extends RegularRingElem<C>> extends ReductionAbstract<C>
031 implements RReduction<C> {
032
033
034 private static final Logger logger = Logger.getLogger(RReductionSeq.class);
035
036
037 private final boolean debug = logger.isDebugEnabled();
038
039
040 /**
041 * Constructor.
042 */
043 public RReductionSeq() {
044 }
045
046
047 /**
048 * Is top reducible. Condition is a b != 0, for a=ldcf(A) and b=ldcf(B) and
049 * lt(B) | lt(A) for some B in F.
050 * @param A polynomial.
051 * @param P polynomial list.
052 * @return true if A is top reducible with respect to P.
053 */
054 @Override
055 public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) {
056 if (P == null || P.isEmpty()) {
057 return false;
058 }
059 if (A == null || A.isZERO()) {
060 return false;
061 }
062 boolean mt = false;
063 ExpVector e = A.leadingExpVector();
064 C a = A.leadingBaseCoefficient();
065 a = a.idempotent();
066 for (GenPolynomial<C> p : P) {
067 mt = e.multipleOf(p.leadingExpVector());
068 if (mt) {
069 C b = p.leadingBaseCoefficient();
070 //C r = a.multiply( b );
071 //C r = a.multiply( b.idempotent() );
072 C r = a.idempotentAnd(b);
073 mt = !r.isZERO();
074 if (mt) {
075 return true;
076 }
077 }
078 }
079 return false;
080 }
081
082
083 /**
084 * Is strong top reducible. Condition is idempotent(a) == idempotent(b), for
085 * a=ldcf(A) and b=ldcf(B) and lt(B) | lt(A) for some B in F.
086 * @param A polynomial.
087 * @param P polynomial list.
088 * @return true if A is string top reducible with respect to P.
089 */
090 public boolean isStrongTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) {
091 if (P == null || P.isEmpty()) {
092 return false;
093 }
094 if (A == null || A.isZERO()) {
095 return false;
096 }
097 boolean mt = false;
098 ExpVector e = A.leadingExpVector();
099 C a = A.leadingBaseCoefficient();
100 a = a.idempotent();
101 for (GenPolynomial<C> p : P) {
102 mt = e.multipleOf(p.leadingExpVector());
103 if (mt) {
104 C b = p.leadingBaseCoefficient();
105 mt = a.equals(b.idempotent());
106 if (mt) {
107 return true;
108 }
109 }
110 }
111 return false;
112 }
113
114
115 /**
116 * Is in Normalform.
117 * @param Ap polynomial.
118 * @param Pp polynomial list.
119 * @return true if Ap is in normalform with respect to Pp.
120 */
121 @Override
122 @SuppressWarnings("unchecked")
123 public boolean isNormalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
124 if (Pp == null || Pp.isEmpty()) {
125 return true;
126 }
127 if (Ap == null || Ap.isZERO()) {
128 return true;
129 }
130 int l;
131 GenPolynomial<C>[] P;
132 synchronized (Pp) {
133 l = Pp.size();
134 P = new GenPolynomial[l];
135 //P = Pp.toArray();
136 for (int i = 0; i < Pp.size(); i++) {
137 P[i] = Pp.get(i);
138 }
139 }
140 ExpVector[] htl = new ExpVector[l];
141 C[] lbc = (C[]) new RegularRingElem[l]; // want <C>
142 GenPolynomial<C>[] p = new GenPolynomial[l];
143 Map.Entry<ExpVector, C> m;
144 int i;
145 int j = 0;
146 for (i = 0; i < l; i++) {
147 if (P[i] == null) {
148 continue;
149 }
150 p[i] = P[i];
151 m = p[i].leadingMonomial();
152 if (m != null) {
153 p[j] = p[i];
154 htl[j] = m.getKey();
155 lbc[j] = m.getValue();
156 j++;
157 }
158 }
159 l = j;
160 boolean mt = false;
161 Map<ExpVector, C> Am = Ap.getMap();
162 for (ExpVector e : Am.keySet()) {
163 for (i = 0; i < l; i++) {
164 mt = e.multipleOf(htl[i]);
165 if (mt) {
166 C a = Am.get(e);
167 //C r = a.multiply( lbc[i] );
168 //C r = a.idempotent().multiply( lbc[i].idempotent() );
169 C r = a.idempotentAnd(lbc[i]);
170 mt = !r.isZERO();
171 if (mt) {
172 return false;
173 }
174 }
175 }
176 }
177 return true;
178 }
179
180
181 /**
182 * Normalform using r-reduction.
183 * @param Ap polynomial.
184 * @param Pp polynomial list.
185 * @return r-nf(Ap) with respect to Pp.
186 */
187 @SuppressWarnings("unchecked")
188 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
189 if (Pp == null || Pp.isEmpty()) {
190 return Ap;
191 }
192 if (Ap == null || Ap.isZERO()) {
193 return Ap;
194 }
195 int l;
196 GenPolynomial<C>[] P;
197 synchronized (Pp) {
198 l = Pp.size();
199 P = (GenPolynomial<C>[]) new GenPolynomial[l];
200 //P = Pp.toArray();
201 for (int i = 0; i < Pp.size(); i++) {
202 P[i] = Pp.get(i);
203 }
204 }
205 //System.out.println("l = " + l);
206 Map.Entry<ExpVector, C> m;
207 ExpVector[] htl = new ExpVector[l];
208 C[] lbc = (C[]) new RegularRingElem[l]; // want <C>
209 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
210 int i;
211 int j = 0;
212 for (i = 0; i < l; i++) {
213 if (P[i] == null) {
214 continue;
215 }
216 p[i] = P[i].abs();
217 m = p[i].leadingMonomial();
218 if (m != null) {
219 p[j] = p[i];
220 htl[j] = m.getKey();
221 lbc[j] = m.getValue();
222 j++;
223 }
224 }
225 l = j;
226 ExpVector e, f;
227 C a, b;
228 C r = null;
229 boolean mt = false;
230 GenPolynomial<C> R = Ap.ring.getZERO();
231 GenPolynomial<C> Q = null;
232 GenPolynomial<C> S = Ap;
233 while (S.length() > 0) {
234 m = S.leadingMonomial();
235 e = m.getKey();
236 a = m.getValue();
237 for (i = 0; i < l; i++) {
238 mt = e.multipleOf(htl[i]);
239 if (mt) {
240 //r = a.multiply( lbc[i] );
241 //r = a.idempotent().multiply( lbc[i].idempotent() );
242 r = a.idempotentAnd(lbc[i]);
243 //System.out.println("r = " + r);
244 mt = !r.isZERO(); // && mt
245 if (mt) {
246 b = a.divide(lbc[i]);
247 if (b.isZERO()) { // strange case in regular rings
248 System.out.println("b == zero: r = " + r);
249 continue;
250 }
251 f = e.subtract(htl[i]);
252 //logger.info("red div = " + f);
253 Q = p[i].multiply(b, f);
254 S = S.subtract(Q); // not ok with reductum
255 f = S.leadingExpVector();
256 if (!e.equals(f)) {
257 a = Ap.ring.coFac.getZERO();
258 break;
259 }
260 a = S.leadingBaseCoefficient();
261 }
262 }
263 }
264 if (!a.isZERO()) { //! mt ) {
265 //logger.debug("irred");
266 R = R.sum(a, e);
267 S = S.reductum();
268 }
269 }
270 return R; //.abs(); // not monic if not boolean closed
271 }
272
273
274 /**
275 * GB criterium 4. Use only for commutative polynomial rings. <b>Note:</b>
276 * Experimental version for r-Groebner bases.
277 * @param A polynomial.
278 * @param B polynomial.
279 * @param e = lcm(ht(A),ht(B))
280 * @return true if the S-polynomial(i,j) is required, else false.
281 */
282 @Override
283 public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B, ExpVector e) {
284 if (logger.isInfoEnabled()) {
285 if (!A.ring.equals(B.ring)) {
286 logger.error("rings equal");
287 }
288 if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
289 logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
290 return true;
291 }
292 }
293 ExpVector ei = A.leadingExpVector();
294 ExpVector ej = B.leadingExpVector();
295 ExpVector g = ei.sum(ej);
296 // boolean t = g == e ;
297 ExpVector h = g.subtract(e);
298 int s = h.signum();
299 if (s == 0) { // disjoint ht
300 C a = A.leadingBaseCoefficient();
301 C b = B.leadingBaseCoefficient();
302 C d = a.multiply(b);
303 if (d.isZERO()) { // a guess
304 //System.out.println("d1 = " + d + ", a = " + a + ", b = " + b);
305 return false; // can skip pair
306 }
307 }
308 return true; //! ( s == 0 );
309 }
310
311
312 /**
313 * GB criterium 4. Use only for commutative polynomial rings. <b>Note:</b>
314 * Experimental version for r-Groebner bases.
315 * @param A polynomial.
316 * @param B polynomial.
317 * @return true if the S-polynomial(i,j) is required, else false.
318 */
319 @Override
320 public boolean criterion4(GenPolynomial<C> A, GenPolynomial<C> B) {
321 if (logger.isInfoEnabled()) {
322 if (A instanceof GenSolvablePolynomial || B instanceof GenSolvablePolynomial) {
323 logger.error("GBCriterion4 not applicabable to SolvablePolynomials");
324 return true;
325 }
326 }
327 ExpVector ei = A.leadingExpVector();
328 ExpVector ej = B.leadingExpVector();
329 ExpVector g = ei.sum(ej);
330 ExpVector e = ei.lcm(ej);
331 // boolean t = g == e ;
332 ExpVector h = g.subtract(e);
333 int s = h.signum();
334 if (s == 0) { // disjoint ht
335 C a = A.leadingBaseCoefficient();
336 C b = B.leadingBaseCoefficient();
337 C d = a.multiply(b);
338 if (d.isZERO()) { // a guess
339 return false; // can skip pair
340 }
341 }
342 return true; //! ( s == 0 );
343 }
344
345
346 /**
347 * Normalform with recording.
348 * @param row recording matrix, is modified.
349 * @param Pp a polynomial list for reduction.
350 * @param Ap a polynomial.
351 * @return Ap - row*Pp = nf(Pp,Ap) , the normal form of Ap wrt. Pp.
352 */
353 @SuppressWarnings("unchecked")
354 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row,
355 List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
356 if (Pp == null || Pp.isEmpty()) {
357 return Ap;
358 }
359 if (Ap == null || Ap.isZERO()) {
360 return Ap;
361 }
362 int l;
363 GenPolynomial<C>[] P;
364 synchronized (Pp) {
365 l = Pp.size();
366 P = (GenPolynomial<C>[]) new GenPolynomial[l];
367 //P = Pp.toArray();
368 for (int i = 0; i < Pp.size(); i++) {
369 P[i] = Pp.get(i);
370 }
371 }
372 //System.out.println("l = " + l);
373 Map.Entry<ExpVector, C> m;
374 ExpVector[] htl = new ExpVector[l];
375 C[] lbc = (C[]) new RegularRingElem[l]; // want <C>
376 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
377 int i;
378 int j = 0;
379 for (i = 0; i < l; i++) {
380 p[i] = P[i];
381 m = p[i].leadingMonomial();
382 if (m != null) {
383 p[j] = p[i];
384 htl[j] = m.getKey();
385 lbc[j] = m.getValue();
386 j++;
387 }
388 }
389 l = j;
390 ExpVector e, f;
391 C a;
392 C r = null;
393 boolean mt = false;
394 GenPolynomial<C> fac = null;
395 GenPolynomial<C> zero = Ap.ring.getZERO();
396 GenPolynomial<C> R = Ap.ring.getZERO();
397 GenPolynomial<C> Q = null;
398 GenPolynomial<C> S = Ap;
399 while (S.length() > 0) {
400 m = S.leadingMonomial();
401 e = m.getKey();
402 a = m.getValue();
403 for (i = 0; i < l; i++) {
404 mt = e.multipleOf(htl[i]);
405 if (mt) {
406 //r = a.idempotent().multiply( lbc[i].idempotent() );
407 //r = a.multiply( lbc[i] );
408 r = a.idempotentAnd(lbc[i]);
409 //System.out.println("r = " + r);
410 mt = !r.isZERO(); // && mt
411 if (mt) {
412 a = a.divide(lbc[i]);
413 if (a.isZERO()) { // strange case in regular rings
414 System.out.println("b == zero: r = " + r);
415 continue;
416 }
417 f = e.subtract(htl[i]);
418 //logger.info("red div = " + f);
419 Q = p[i].multiply(a, f);
420 S = S.subtract(Q); // not ok with reductum
421
422 fac = row.get(i);
423 if (fac == null) {
424 fac = zero.sum(a, f);
425 } else {
426 fac = fac.sum(a, f);
427 }
428 row.set(i, fac);
429
430 f = S.leadingExpVector();
431 if (!e.equals(f)) {
432 a = Ap.ring.coFac.getZERO();
433 break;
434 }
435 a = S.leadingBaseCoefficient();
436 }
437 }
438 }
439 if (!a.isZERO()) { //! mt ) {
440 //logger.debug("irred");
441 R = R.sum(a, e);
442 S = S.reductum();
443 }
444 }
445 return R; //.abs(); not for recording
446 }
447
448
449 /**
450 * Irreducible set. May not be boolean closed.
451 * @param Pp polynomial list.
452 * @return a list P of polynomials which are in normalform wrt. P.
453 */
454 @Override
455 public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
456 ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
457 if (Pp == null) {
458 return null;
459 }
460 for (GenPolynomial<C> a : Pp) {
461 if (!a.isZERO()) {
462 P.add(a);
463 }
464 }
465 int l = P.size();
466 if (l <= 1)
467 return P;
468
469 int irr = 0;
470 ExpVector e;
471 ExpVector f;
472 GenPolynomial<C> a;
473 Iterator<GenPolynomial<C>> it;
474 logger.debug("irr = ");
475 while (irr != l) {
476 //it = P.listIterator();
477 //a = P.get(0); //it.next();
478 a = P.remove(0);
479 e = a.leadingExpVector();
480 a = normalform(P, a);
481 // no not make monic because of boolean closure
482 logger.debug(String.valueOf(irr));
483 if (a.isZERO()) {
484 l--;
485 if (l <= 1) {
486 return P;
487 }
488 } else {
489 f = a.leadingExpVector();
490 if (e.equals(f)) {
491 // lbcf(a) eventually shorter
492 // correct since longer coeffs can reduce shorter coeffs
493 irr++;
494 } else {
495 irr = 0;
496 }
497 P.add(a);
498 }
499 }
500 //System.out.println();
501 return P;
502 }
503
504
505 /*
506 * -------- boolean closure stuff -----------------------------------------
507 */
508
509 /**
510 * Is boolean closed, test if A == idempotent(ldcf(A)) A.
511 * @param A polynomial.
512 * @return true if A is boolean closed, else false.
513 */
514 public boolean isBooleanClosed(GenPolynomial<C> A) {
515 if (A == null || A.isZERO()) {
516 return true;
517 }
518 C a = A.leadingBaseCoefficient();
519 C i = a.idempotent();
520 GenPolynomial<C> B = A.multiply(i);
521 // better run idemAnd on coefficients
522 if (A.equals(B)) {
523 return true;
524 }
525 return false;
526 }
527
528
529 /**
530 * Is boolean closed, test if all A in F are boolean closed.
531 * @param F polynomial list.
532 * @return true if F is boolean closed, else false.
533 */
534 public boolean isBooleanClosed(List<GenPolynomial<C>> F) {
535 if (F == null || F.size() == 0) {
536 return true;
537 }
538 for (GenPolynomial<C> a : F) {
539 if (a == null || a.isZERO()) {
540 continue;
541 }
542 //System.out.println("a = " + a);
543 if (!isBooleanClosed(a)) {
544 return false;
545 }
546 }
547 return true;
548 }
549
550
551 /**
552 * Is reduced boolean closed, test if all A in F are boolean closed or br(A)
553 * reduces to zero.
554 * @param F polynomial list.
555 * @return true if F is boolean closed, else false.
556 */
557 public boolean isReducedBooleanClosed(List<GenPolynomial<C>> F) {
558 if (F == null || F.size() == 0) {
559 return true;
560 }
561 GenPolynomial<C> b;
562 GenPolynomial<C> r;
563 for (GenPolynomial<C> a : F) {
564 //System.out.println("a = " + a);
565 if (a == null) {
566 continue;
567 }
568 while (!a.isZERO()) {
569 if (!isBooleanClosed(a)) {
570 b = booleanClosure(a);
571 b = normalform(F, b);
572 if (!b.isZERO()) { //F.contains(r)
573 return false;
574 }
575 }
576 r = booleanRemainder(a);
577 r = normalform(F, r);
578 if (!r.isZERO()) { //F.contains(r)
579 return false;
580 }
581 //System.out.println("r = " + r);
582 a = r;
583 }
584 }
585 return true;
586 }
587
588
589 /**
590 * Boolean closure, compute idempotent(ldcf(A)) A.
591 * @param A polynomial.
592 * @return bc(A).
593 */
594 public GenPolynomial<C> booleanClosure(GenPolynomial<C> A) {
595 if (A == null || A.isZERO()) {
596 return A;
597 }
598 C a = A.leadingBaseCoefficient();
599 C i = a.idempotent();
600 GenPolynomial<C> B = A.multiply(i);
601 return B;
602 }
603
604
605 /**
606 * Boolean remainder, compute idemComplement(ldcf(A)) A.
607 * @param A polynomial.
608 * @return br(A).
609 */
610 public GenPolynomial<C> booleanRemainder(GenPolynomial<C> A) {
611 if (A == null || A.isZERO()) {
612 return A;
613 }
614 C a = A.leadingBaseCoefficient();
615 C i = a.idemComplement();
616 GenPolynomial<C> B = A.multiply(i);
617 return B;
618 }
619
620
621 /**
622 * Boolean closure, compute BC(A) for all A in F.
623 * @param F polynomial list.
624 * @return bc(F).
625 */
626 public List<GenPolynomial<C>> booleanClosure(List<GenPolynomial<C>> F) {
627 if (F == null || F.size() == 0) {
628 return F;
629 }
630 List<GenPolynomial<C>> B = new ArrayList<GenPolynomial<C>>(F.size());
631 for (GenPolynomial<C> a : F) {
632 if (a == null) {
633 continue;
634 }
635 while (!a.isZERO()) {
636 GenPolynomial<C> b = booleanClosure(a);
637 B.add(b);
638 a = booleanRemainder(a);
639 }
640 }
641 return B;
642 }
643
644
645 /**
646 * Reduced boolean closure, compute BC(A) for all A in F.
647 * @param F polynomial list.
648 * @return red(bc(F)) = bc(red(F)).
649 */
650 public List<GenPolynomial<C>> reducedBooleanClosure(List<GenPolynomial<C>> F) {
651 if (F == null || F.size() == 0) {
652 return F;
653 }
654 List<GenPolynomial<C>> B = new ArrayList<GenPolynomial<C>>(F);
655 GenPolynomial<C> a;
656 GenPolynomial<C> b;
657 GenPolynomial<C> c;
658 int len = B.size();
659 for (int i = 0; i < len; i++) { // not B.size(), it changes
660 a = B.remove(0);
661 if (a == null) {
662 continue;
663 }
664 while (!a.isZERO()) {
665 //System.out.println("a = " + a);
666 b = booleanClosure(a);
667 //System.out.println("b = " + b);
668 b = booleanClosure(normalform(B, b));
669 if (b.isZERO()) {
670 break;
671 }
672 B.add(b); // adds as last
673 c = a.subtract(b); // = BR(a mod B)
674 //System.out.println("c = " + c);
675 c = normalform(B, c);
676 a = c;
677 }
678 }
679 return B;
680 }
681
682
683 /**
684 * Reduced boolean closure, compute BC(A) modulo F.
685 * @param A polynomial.
686 * @param F polynomial list.
687 * @return red(bc(A)).
688 */
689 public List<GenPolynomial<C>> reducedBooleanClosure(List<GenPolynomial<C>> F,
690 GenPolynomial<C> A) {
691 List<GenPolynomial<C>> B = new ArrayList<GenPolynomial<C>>();
692 if (A == null || A.isZERO()) {
693 return B;
694 }
695 GenPolynomial<C> a = A;
696 GenPolynomial<C> b;
697 GenPolynomial<C> c;
698 while (!a.isZERO()) {
699 //System.out.println("a = " + a);
700 b = booleanClosure(a);
701 //System.out.println("b = " + b);
702 b = booleanClosure(normalform(F, b));
703 if (b.isZERO()) {
704 break;
705 }
706 B.add(b); // adds as last
707 c = a.subtract(b); // = BR(a mod F)
708 //System.out.println("c = " + c);
709 c = normalform(F, c);
710 //System.out.println("c = " + c);
711 a = c;
712 }
713 return B;
714 }
715
716 }