001 /*
002 * $Id: CReductionSeq.java 3426 2010-12-24 13:17:58Z kredel $
003 */
004
005 package edu.jas.application;
006
007
008 import java.util.ArrayList;
009 import java.util.LinkedList;
010 import java.util.List;
011 import java.util.Map;
012 import java.util.Collections;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.poly.ExpVector;
017 import edu.jas.poly.GenPolynomial;
018 import edu.jas.poly.GenPolynomialRing;
019 import edu.jas.structure.GcdRingElem;
020 import edu.jas.structure.RingFactory;
021 import edu.jas.ufd.GCDFactory;
022 import edu.jas.ufd.GreatestCommonDivisor;
023
024
025 /**
026 * Polynomial parametric ring reduction sequential use algorithm. Implements
027 * normalform, condition construction and polynomial determination.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031 public class CReductionSeq<C extends GcdRingElem<C>>
032 /* extends ReductionAbstract<C> */
033 /* implements CReduction<C> */ {
034
035
036 private static final Logger logger = Logger.getLogger(CReductionSeq.class);
037
038
039 private final boolean debug = logger.isDebugEnabled();
040
041
042 private final boolean info = logger.isInfoEnabled();
043
044
045 /**
046 * Greatest common divisor engine.
047 */
048 protected final GreatestCommonDivisor<C> engine;
049
050
051 /**
052 * Polynomial coefficient ring factory.
053 */
054 protected final RingFactory<C> cofac;
055
056
057 /**
058 * Flag if top-reduction only should be used.
059 */
060 protected boolean top = true; // false;
061
062
063 /**
064 * Constructor.
065 * @param rf coefficient factory.
066 */
067 public CReductionSeq(RingFactory<C> rf) {
068 cofac = rf;
069 // System.out.println("cofac = " + cofac);
070 engine = GCDFactory.<C> getImplementation(cofac);
071 }
072
073
074 /**
075 * S-Polynomial.
076 * @param Ap polynomial.
077 * @param Bp polynomial.
078 * @return spol(Ap,Bp) the S-polynomial of Ap and Bp.
079 */
080 public ColorPolynomial<C> SPolynomial(ColorPolynomial<C> Ap, ColorPolynomial<C> Bp) {
081 if (Bp == null || Bp.isZERO()) {
082 return Bp;
083 }
084 if (Ap == null || Ap.isZERO()) {
085 return Ap;
086 }
087
088 Map.Entry<ExpVector, GenPolynomial<C>> ma = Ap.red.leadingMonomial();
089 Map.Entry<ExpVector, GenPolynomial<C>> mb = Bp.red.leadingMonomial();
090
091 ExpVector e = ma.getKey();
092 ExpVector f = mb.getKey();
093
094 ExpVector g = e.lcm(f); // EVLCM(e,f);
095 ExpVector e1 = g.subtract(e); // EVDIF(g,e);
096 ExpVector f1 = g.subtract(f); // EVDIF(g,f);
097
098 GenPolynomial<C> a = ma.getValue();
099 GenPolynomial<C> b = mb.getValue();
100
101 GenPolynomial<C> c = engine.gcd(a, b);
102 if (!c.isONE()) {
103 // System.out.println("gcd =s " + c);
104 a = a.divide(c);
105 b = b.divide(c);
106 }
107
108 ColorPolynomial<C> App = Ap.multiply(b, e1);
109 ColorPolynomial<C> Bpp = Bp.multiply(a, f1);
110 ColorPolynomial<C> Cp = App.subtract(Bpp);
111 return Cp;
112 }
113
114
115 /**
116 * Is top reducible.
117 * @param A polynomial.
118 * @param P polynomial list.
119 * @return true if A is top reducible with respect to P.
120 */
121 public boolean isTopReducible(List<ColorPolynomial<C>> P, ColorPolynomial<C> A) {
122 if (P == null || P.isEmpty()) {
123 return false;
124 }
125 if (A == null || A.isZERO()) {
126 return false;
127 }
128 boolean mt = false;
129 ExpVector e = A.leadingExpVector();
130 for (ColorPolynomial<C> p : P) {
131 if (p == null) {
132 return false;
133 }
134 ExpVector f = p.leadingExpVector();
135 if (f == null) {
136 return false;
137 }
138 if (e == null) {
139 return false;
140 }
141 mt = e.multipleOf(f); // EVMT( e, p.leadingExpVector() );
142 if (mt) {
143 return true;
144 }
145 }
146 return false;
147 }
148
149
150 /**
151 * Is reducible.
152 * @param Ap polynomial.
153 * @param Pp polynomial list.
154 * @return true if Ap is reducible with respect to Pp.
155 */
156 public boolean isReducible(List<ColorPolynomial<C>> Pp, ColorPolynomial<C> Ap) {
157 return !isNormalform(Pp, Ap);
158 }
159
160
161 /**
162 * Is in Normalform.
163 * @param Ap polynomial.
164 * @param Pp polynomial list.
165 * @return true if Ap is in normalform with respect to Pp.
166 */
167 @SuppressWarnings("unchecked")
168 public boolean isNormalform(List<ColorPolynomial<C>> Pp, ColorPolynomial<C> Ap) {
169 if (Pp == null || Pp.isEmpty()) {
170 return true;
171 }
172 if (Ap == null || Ap.isZERO()) {
173 return true;
174 }
175 int l;
176 ColorPolynomial<C>[] P;
177 synchronized (Pp) {
178 l = Pp.size();
179 P = new ColorPolynomial[l];
180 // P = Pp.toArray();
181 for (int i = 0; i < Pp.size(); i++) {
182 P[i] = Pp.get(i);
183 }
184 }
185 ExpVector[] htl = new ExpVector[l];
186 ColorPolynomial<C>[] p = new ColorPolynomial[l];
187 Map.Entry<ExpVector, GenPolynomial<C>> m;
188 int i;
189 int j = 0;
190 for (i = 0; i < l; i++) {
191 p[i] = P[i];
192 m = p[i].red.leadingMonomial();
193 if (m != null) {
194 p[j] = p[i];
195 htl[j] = m.getKey();
196 j++;
197 }
198 }
199 l = j;
200 boolean mt = false;
201 for (ExpVector e : Ap.red.getMap().keySet()) {
202 for (i = 0; i < l; i++) {
203 mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
204 if (mt) {
205 System.out.println("not normalform " + Ap + ", P[i] = " + P[i]);
206 return false;
207 }
208 }
209 if ( top ) {
210 return true;
211 }
212 }
213 for (ExpVector e : Ap.white.getMap().keySet()) {
214 for (i = 0; i < l; i++) {
215 mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
216 if (mt) {
217 System.out.println("not normalform " + Ap + ", P[i] = " + P[i]);
218 return false;
219 }
220 }
221 if ( top ) {
222 return true;
223 }
224 }
225 return true;
226 }
227
228
229 /**
230 * Is in Normalform.
231 * @param Pp polynomial list.
232 * @return true if each Ap in Pp is in normalform with respect to Pp\{Ap}.
233 */
234 public boolean isNormalform(List<ColorPolynomial<C>> Pp) {
235 if (Pp == null || Pp.isEmpty()) {
236 return true;
237 }
238 ColorPolynomial<C> Ap;
239 List<ColorPolynomial<C>> P = new LinkedList<ColorPolynomial<C>>(Pp);
240 int s = P.size();
241 for (int i = 0; i < s; i++) {
242 Ap = P.remove(i);
243 if (!isNormalform(P, Ap)) {
244 return false;
245 }
246 P.add(Ap);
247 }
248 return true;
249 }
250
251
252 /**
253 * Normalform.
254 * @param Ap polynomial.
255 * @param Pp polynomial list.
256 * @param cond condition for these polynomials.
257 * @return nf(Ap) with respect to Pp.
258 */
259 @SuppressWarnings("unchecked")
260 public ColorPolynomial<C> normalform(Condition<C> cond, List<ColorPolynomial<C>> Pp,
261 ColorPolynomial<C> Ap) {
262 if (Pp == null || Pp.isEmpty()) {
263 return Ap;
264 }
265 if (Ap == null || Ap.isZERO()) {
266 return Ap;
267 }
268 Map.Entry<ExpVector, GenPolynomial<C>> m;
269 int l;
270 ColorPolynomial<C>[] P;
271 synchronized (Pp) {
272 l = Pp.size();
273 P = new ColorPolynomial[l];
274 // P = Pp.toArray();
275 for (int i = 0; i < Pp.size(); i++) {
276 P[i] = Pp.get(i);
277 }
278 }
279 ExpVector[] htl = new ExpVector[l];
280 Object[] lbc = new Object[l]; // want C[]
281 ColorPolynomial<C>[] p = new ColorPolynomial[l];
282 int i;
283 int j = 0;
284 for (i = 0; i < l; i++) {
285 if (P[i] == null) {
286 continue;
287 }
288 p[i] = P[i];
289 m = p[i].red.leadingMonomial();
290 if (m != null) {
291 p[j] = p[i];
292 htl[j] = m.getKey();
293 lbc[j] = m.getValue();
294 j++;
295 }
296 }
297 l = j;
298 ExpVector e;
299 GenPolynomial<C> a;
300 boolean mt = false;
301 GenPolynomial<GenPolynomial<C>> zero = p[0].red.ring.getZERO();
302 ColorPolynomial<C> R = new ColorPolynomial<C>(zero, zero, zero);
303
304 // ColorPolynomial<C> T = null;
305 ColorPolynomial<C> Q = null;
306 ColorPolynomial<C> S = Ap;
307 while (S.length() > 0) {
308 m = S.leadingMonomial();
309 e = m.getKey();
310 a = m.getValue();
311 Condition.Color col = cond.color(a);
312 if (col == Condition.Color.GREEN) { // move to green terms
313 GenPolynomial<GenPolynomial<C>> g = S.green.sum(a, e);
314 GenPolynomial<GenPolynomial<C>> r = S.red;
315 GenPolynomial<GenPolynomial<C>> w = S.white;
316 if (S.red.isZERO()) {
317 w = w.subtract(a, e);
318 } else { // only in minimalGB
319 logger.info("green_red = " + zero.sum(a, e));
320 r = r.subtract(a, e);
321 }
322 S = new ColorPolynomial<C>(g, r, w);
323 continue;
324 }
325 if (col == Condition.Color.WHITE) { // refine condition
326 // System.out.println("white = " + zero.sum(a,e));
327 // return S; // return for new case distinction
328 }
329 // System.out.println("NF, e = " + e);
330 for (i = 0; i < l; i++) {
331 mt = e.multipleOf(htl[i]); // EVMT( e, htl[i] );
332 if (mt)
333 break;
334 }
335 if (!mt) {
336 // logger.debug("irred");
337 if (top) {
338 return S;
339 }
340 R = R.sum(a, e);
341 S = S.subtract(a, e);
342 // System.out.println(" S = " + S);
343 } else {
344 e = e.subtract(htl[i]); // EVDIF( e, htl[i] );
345 // logger.info("red div = " + e);
346 GenPolynomial<C> c = (GenPolynomial<C>) lbc[i];
347 GenPolynomial<C> g = engine.gcd(a, c);
348 if (!g.isONE()) {
349 // System.out.println("gcd = " + g);
350 a = a.divide(g);
351 c = c.divide(g);
352 }
353 S = S.multiply(c);
354 R = R.multiply(c);
355 Q = p[i].multiply(a, e);
356 S = S.subtract(Q);
357 }
358 }
359 return R;
360 }
361
362
363 /*
364 * -------- coloring and condition stuff ------------------------------
365 */
366
367 /**
368 * Case distinction conditions of parametric polynomial list. The returned
369 * condition determines the polynomial list.
370 * @param L list of parametric polynomials.
371 * @return list of conditions as case distinction.
372 */
373 public List<Condition<C>> caseDistinction(List<GenPolynomial<GenPolynomial<C>>> L) {
374 List<Condition<C>> cd = new ArrayList<Condition<C>>();
375 if (L == null || L.size() == 0) {
376 return cd;
377 }
378 for (GenPolynomial<GenPolynomial<C>> A : L) {
379 if (A != null && !A.isZERO()) {
380 cd = caseDistinction(cd, A);
381 }
382 }
383 // System.out.println("cd = " + cd);
384 return cd;
385 }
386
387
388 /**
389 * Case distinction conditions of parametric polynomial list.
390 * @param cd a list of conditions.
391 * @param A a parametric polynomial.
392 * @return list of conditions as case distinction extending the conditions
393 * in cd.
394 */
395 public List<Condition<C>> caseDistinction(List<Condition<C>> cd,
396 GenPolynomial<GenPolynomial<C>> A) {
397 if (A == null || A.isZERO()) {
398 return cd;
399 }
400 if (cd == null) {
401 cd = new ArrayList<Condition<C>>();
402 }
403 if (cd.size() == 0) { // construct empty condition
404 RingFactory<GenPolynomial<C>> crfac = A.ring.coFac;
405 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) crfac;
406 Condition<C> sc = new Condition<C>(cfac);
407 cd.add(sc);
408 }
409 GenPolynomial<GenPolynomial<C>> Ap;
410 GenPolynomial<GenPolynomial<C>> Bp;
411
412 List<Condition<C>> C = new ArrayList<Condition<C>>( /* leer! */);
413 for (Condition<C> cond : cd) {
414 // System.out.println("caseDist: " + cond);
415 Condition<C> cz = cond;
416 Ap = A;
417 while (!Ap.isZERO()) {
418 GenPolynomial<C> c = Ap.leadingBaseCoefficient();
419 Bp = Ap.reductum();
420 //System.out.println("to color: " + c);
421 switch (cz.color(c)) {
422 case GREEN:
423 // System.out.println("color green: " + c);
424 Ap = Bp;
425 continue;
426 case RED:
427 // System.out.println("color red: " + c);
428 C.add(cz);
429 // wrong: return C;
430 Ap = A.ring.getZERO();
431 continue;
432 // break;
433 case WHITE:
434 default:
435 // System.out.println("color white: " + c);
436 Condition<C> nc = cz.extendNonZero(c);
437 if (nc != null) { // no contradiction
438 if (!cz.equals(nc)) {
439 C.add(nc);
440 } else {
441 cz = null;
442 Ap = A.ring.getZERO();
443 continue;
444 }
445 } else {
446 System.out.println("this should not be printed " + c);
447 }
448 Condition<C> ez = cz.extendZero(c);
449 if (ez != null) {
450 cz = ez;
451 } else { // contradiction
452 cz = null;
453 Ap = A.ring.getZERO();
454 continue;
455 }
456 Ap = Bp;
457 }
458 }
459 // System.out.println("cond cz: " + cz);
460 if (cz == null || cz.isContradictory() || C.contains(cz)) {
461 // System.out.println("not added entry " + cz);
462 } else {
463 C.add(cz);
464 }
465 }
466 // System.out.println("C = " + C);
467 return C;
468 }
469
470
471 /**
472 * Case distinction conditions of parametric polynomial list.
473 * @param A a parametric polynomial.
474 * @param cond a condition.
475 * @return list of case distinction conditions.
476 */
477 public List<Condition<C>> caseDistinction(Condition<C> cond,
478 GenPolynomial<GenPolynomial<C>> A) {
479 List<Condition<C>> cd = new ArrayList<Condition<C>>();
480 if (A == null || A.isZERO()) {
481 return cd;
482 }
483 cd.add(cond);
484 cd = caseDistinction(cd, A);
485 if (info) {
486 StringBuffer s = new StringBuffer("extending condition: " + cond + "\n");
487 s.append("case distinctions: [ \n");
488 for (Condition<C> c : cd) {
489 s.append(c.toString() + "\n");
490 }
491 s.append("]");
492 logger.info(s.toString());
493 }
494 return cd;
495 }
496
497
498 /**
499 * Determine polynomial list.
500 * @param H polynomial list.
501 * @return new determined list of colored systems.
502 */
503 public List<ColoredSystem<C>> determine(List<GenPolynomial<GenPolynomial<C>>> H) {
504 if (H == null || H.size() == 0) {
505 List<ColoredSystem<C>> CS = new ArrayList<ColoredSystem<C>>();
506 return CS;
507 }
508 //System.out.println("of determine = " + H);
509 Collections.reverse(H);
510 List<Condition<C>> cd = caseDistinction(H);
511 //System.out.println("case Distinction = " + cd);
512 //System.out.println("of determine = " + H);
513 return determine(cd, H);
514 }
515
516
517 /**
518 * Determine polynomial list.
519 * @param H polynomial list.
520 * @param cd case distiction, a condition list.
521 * @return new determined list of colored systems.
522 */
523 public List<ColoredSystem<C>> determine(List<Condition<C>> cd,
524 List<GenPolynomial<GenPolynomial<C>>> H) {
525 List<ColoredSystem<C>> CS = new ArrayList<ColoredSystem<C>>();
526 if (H == null || H.size() == 0) {
527 return CS;
528 }
529 for (Condition<C> cond : cd) {
530 logger.info("determine wrt cond = " + cond);
531 if (cond.zero.isONE()) { // should not happen
532 System.out.println("ideal is one = " + cond.zero);
533 // continue; // can treat all coeffs as green
534 }
535 // if ( cond.isEmpty() ) { // do not use this code
536 // continue; // can skip condition (?)
537 // }
538 List<ColorPolynomial<C>> S = cond.determine(H);
539 ColoredSystem<C> cs = new ColoredSystem<C>(cond, S);
540 CS.add(cs);
541 }
542 return CS;
543 }
544
545 }