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