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