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