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