001/* 002 * $Id: SolvablePseudoReductionSeq.java 5364 2015-12-26 12:36:37Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.List; 009import java.util.Map; 010 011import org.apache.log4j.Logger; 012 013import edu.jas.gb.SolvableReductionAbstract; 014import edu.jas.poly.ExpVector; 015import edu.jas.poly.GenPolynomial; 016import edu.jas.poly.GenPolynomialRing; 017import edu.jas.poly.GenSolvablePolynomial; 018import edu.jas.poly.GenSolvablePolynomialRing; 019import edu.jas.poly.PolyUtil; 020import edu.jas.structure.GcdRingElem; 021 022 023/** 024 * Polynomial pseudo reduction sequential use algorithm. Coefficients of 025 * polynomials must not be from a field, i.e. the fraction free reduction is 026 * implemented. Implements normalform. 027 * @param <C> coefficient type 028 * @author Heinz Kredel 029 */ 030 031public class SolvablePseudoReductionSeq<C extends GcdRingElem<C>> extends SolvableReductionAbstract<C> 032 implements SolvablePseudoReduction<C> { 033 034 035 private static final Logger logger = Logger.getLogger(SolvablePseudoReductionSeq.class); 036 037 038 private final boolean debug = logger.isDebugEnabled(); 039 040 041 /** 042 * Constructor. 043 */ 044 public SolvablePseudoReductionSeq() { 045 } 046 047 048 /** 049 * Left normalform. 050 * @param Ap polynomial. 051 * @param Pp polynomial list. 052 * @return nf(Ap) with respect to Pp. 053 */ 054 @SuppressWarnings("unchecked") 055 public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> Pp, 056 GenSolvablePolynomial<C> Ap) { 057 if (Pp == null || Pp.isEmpty()) { 058 return Ap; 059 } 060 if (Ap == null || Ap.isZERO()) { 061 return Ap; 062 } 063 Map.Entry<ExpVector, C> m; 064 GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0]; 065 synchronized (Pp) { 066 P = Pp.toArray(P); 067 } 068 int l = P.length; 069 ExpVector[] htl = new ExpVector[l]; 070 //C[] lbc = (C[]) new GcdRingElem[l]; 071 GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l]; 072 int i; 073 int j = 0; 074 for (i = 0; i < l; i++) { 075 if (P[i] == null) { 076 continue; 077 } 078 p[i] = P[i]; 079 m = p[i].leadingMonomial(); 080 if (m != null) { 081 p[j] = p[i]; 082 htl[j] = m.getKey(); 083 //lbc[j] = m.getValue(); 084 j++; 085 } 086 } 087 l = j; 088 ExpVector e; 089 C a; 090 boolean mt = false; 091 GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy(); 092 GenSolvablePolynomial<C> Q = null; 093 GenSolvablePolynomial<C> S = Ap.copy(); 094 while (S.length() > 0) { 095 m = S.leadingMonomial(); 096 e = m.getKey(); 097 a = m.getValue(); 098 for (i = 0; i < l; i++) { 099 mt = e.multipleOf(htl[i]); 100 if (mt) 101 break; 102 } 103 if (!mt) { 104 //logger.debug("irred"); 105 //R = R.sum(a, e); 106 //S = S.subtract(a, e); 107 R.doPutToMap(e, a); 108 S.doRemoveFromMap(e, a); 109 //System.out.println(" S = " + S); 110 } else { 111 e = e.subtract(htl[i]); 112 //logger.info("red div = " + e); 113 Q = p[i].multiplyLeft(e); 114 C c = Q.leadingBaseCoefficient(); 115 ExpVector g = S.leadingExpVector(); 116 C ap = a; 117 if (a.remainder(c).isZERO()) { // && !c.isConstant()) { 118 a = a.divide(c); 119 S = S.subtractMultiple(a, Q); 120 } else { 121 R = R.multiplyLeft(c); 122 S = S.scaleSubtractMultiple(c, a, Q); 123 } 124 ExpVector h = S.leadingExpVector(); 125 if (g.equals(h)) { // Ore condition not fulfilled 126 logger.info("g==h: g = " + g + ", c = " + c); 127 throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap + ", c = " + c); 128 } 129 } 130 } 131 return R; 132 } 133 134 135 /** 136 * Left normalform recursive. 137 * @param Ap recursive polynomial. 138 * @param Pp recursive polynomial list. 139 * @return nf(Ap) with respect to Pp. 140 */ 141 @SuppressWarnings({ "unchecked" }) 142 public GenSolvablePolynomial<GenPolynomial<C>> leftNormalformRecursive( 143 List<GenSolvablePolynomial<GenPolynomial<C>>> Pp, 144 GenSolvablePolynomial<GenPolynomial<C>> Ap) { 145 if (Pp == null || Pp.isEmpty()) { 146 return Ap; 147 } 148 if (Ap == null || Ap.isZERO()) { 149 return Ap; 150 } 151 Map.Entry<ExpVector, GenPolynomial<C>> m; 152 GenSolvablePolynomial<GenPolynomial<C>>[] P = new GenSolvablePolynomial[0]; 153 synchronized (Pp) { 154 P = Pp.toArray(P); 155 } 156 int l = P.length; 157 ExpVector[] htl = new ExpVector[l]; 158 //GenPolynomial<C>[] lbc = (GenPolynomial<C>[]) new GenPolynomial[l]; 159 GenSolvablePolynomial<GenPolynomial<C>>[] p = new GenSolvablePolynomial[l]; 160 int i; 161 int j = 0; 162 for (i = 0; i < l; i++) { 163 if (P[i] == null) { 164 continue; 165 } 166 p[i] = P[i]; 167 m = p[i].leadingMonomial(); 168 if (m != null) { 169 p[j] = p[i]; 170 htl[j] = m.getKey(); 171 //lbc[j] = m.getValue(); 172 j++; 173 } 174 } 175 l = j; 176 ExpVector e, f; 177 GenPolynomial<C> a, b; 178 boolean mt = false; 179 GenSolvablePolynomialRing<GenPolynomial<C>> ring = Ap.ring; 180 final boolean commCoeff = ring.coFac.isCommutative(); 181 final SolvableSyzygyAbstract<C> ssy; 182 if (commCoeff) { 183 ssy = null; 184 } else { 185 ssy = new SolvableSyzygySeq<C>(((GenPolynomialRing<C>) ring.coFac).coFac); 186 } 187 GenSolvablePolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy(); 188 GenSolvablePolynomial<GenPolynomial<C>> Q = null; 189 GenSolvablePolynomial<GenPolynomial<C>> S = Ap.copy(); 190 //GenSolvablePolynomial<GenPolynomial<C>> Sp = null; 191 while (S.length() > 0) { 192 m = S.leadingMonomial(); 193 e = m.getKey(); 194 a = m.getValue(); 195 for (i = 0; i < l; i++) { 196 mt = e.multipleOf(htl[i]); 197 if (mt) 198 break; 199 } 200 if (!mt) { 201 //logger.debug("irred"); 202 //R = R.sum(a, e); 203 //S = S.subtract(a, e); 204 R.doPutToMap(e, a); 205 S.doRemoveFromMap(e, a); 206 //System.out.println(" S = " + S); 207 } else { 208 f = e.subtract(htl[i]); 209 if (debug) { 210 logger.info("red div = " + f); 211 //logger.info("red a = " + a); 212 } 213 Q = p[i].multiplyLeft(f); 214 //if (a.remainder(c).isZERO()) { //c.isUnit() ) { 215 ExpVector g = S.leadingExpVector(); 216 GenPolynomial<C> ap = a; 217 if (commCoeff) { 218 GenPolynomial<C> c = Q.leadingBaseCoefficient(); 219 if (!c.isConstant() && PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) { 220 //a = a.divide(c); 221 b = PolyUtil.<C> basePseudoDivide(a, c); 222 if (a.equals(b.multiply(c))) { 223 S = S.subtractMultiple(b, Q); 224 } else { 225 R = R.multiplyLeft(c); 226 S = S.scaleSubtractMultiple(c, a, Q); 227 } 228 } else { 229 R = R.multiplyLeft(c); 230 S = S.scaleSubtractMultiple(c, a, Q); 231 } 232 } else { // use Ore condition 233 GenSolvablePolynomial<C> cs = (GenSolvablePolynomial<C>) Q.leadingBaseCoefficient(); 234 GenSolvablePolynomial<C> as = (GenSolvablePolynomial<C>) a; 235 GenPolynomial<C>[] ore = ssy.leftOreCond(cs, as); 236 //System.out.println("cs = " + cs + ", as = " + as); 237 //System.out.println("ore[0] = " + ore[0] + "\nore[1] = " + ore[1]); 238 R = R.multiplyLeft(ore[1]); 239 S = S.scaleSubtractMultiple(ore[1], ore[0], Q); 240 } 241 ExpVector h = S.leadingExpVector(); 242 if (g.equals(h)) { // ! Ore cond 243 logger.info("g==h: g = " + g); 244 throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap); 245 } 246 } 247 } 248 //System.out.println("Ap = " + Ap + ", R = " + R); 249 return R; 250 } 251 252 253 /** 254 * Left normalform with recording. <b>Note:</b> Only meaningful if all 255 * divisions are exact. Compute first the multiplication factor 256 * <code>m</code> with <code>normalform(Pp,Ap,m)</code>, then call this 257 * method with <code>normalform(row,Pp,m*Ap)</code>. 258 * @param row recording matrix, is modified. 259 * @param Pp a polynomial list for reduction. 260 * @param Ap a polynomial. 261 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. 262 */ 263 @SuppressWarnings("unchecked") 264 public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> row, 265 List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) { 266 if (Pp == null || Pp.isEmpty()) { 267 return Ap; 268 } 269 if (Ap == null || Ap.isZERO()) { 270 return Ap; 271 } 272 GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0]; 273 synchronized (Pp) { 274 P = Pp.toArray(P); 275 } 276 int l = P.length; 277 ExpVector[] htl = new ExpVector[l]; 278 //C[] lbc = (C[]) new GcdRingElem[l]; 279 GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l]; 280 Map.Entry<ExpVector, C> m; 281 int j = 0; 282 int i; 283 for (i = 0; i < l; i++) { 284 p[i] = P[i]; 285 m = p[i].leadingMonomial(); 286 if (m != null) { 287 p[j] = p[i]; 288 htl[j] = m.getKey(); 289 //lbc[j] = m.getValue(); 290 j++; 291 } 292 } 293 l = j; 294 ExpVector e; 295 C a; 296 boolean mt = false; 297 GenSolvablePolynomial<C> zero = Ap.ring.getZERO(); 298 GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy(); 299 GenSolvablePolynomial<C> Q = null; 300 GenSolvablePolynomial<C> fac = null; 301 GenSolvablePolynomial<C> S = Ap.copy(); 302 while (S.length() > 0) { 303 m = S.leadingMonomial(); 304 e = m.getKey(); 305 a = m.getValue(); 306 for (i = 0; i < l; i++) { 307 mt = e.multipleOf(htl[i]); 308 if (mt) 309 break; 310 } 311 if (!mt) { 312 //logger.debug("irred"); 313 //R = R.sum(a, e); 314 //S = S.subtract(a, e); 315 R.doPutToMap(e, a); 316 S.doRemoveFromMap(e, a); 317 // System.out.println(" S = " + S); 318 //throw new RuntimeException("Syzygy no GB"); 319 } else { 320 e = e.subtract(htl[i]); 321 //logger.info("red div = " + e); 322 Q = p[i].multiplyLeft(e); 323 C c = Q.leadingBaseCoefficient(); 324 ExpVector g = S.leadingExpVector(); 325 C ap = a; 326 if (a.remainder(c).isZERO()) { //c.isUnit() ) { 327 a = a.divide(c); 328 S = S.subtractMultiple(a, Q); 329 //System.out.print("|"); 330 } else { 331 //System.out.print("*"); 332 R = R.multiplyLeft(c); 333 S = S.scaleSubtractMultiple(c, a, Q); 334 } 335 ExpVector h = S.leadingExpVector(); 336 if (g.equals(h)) { // Ore condition not fulfilled 337 System.out.println("g = " + g + ", h = " + h); 338 System.out.println("c*ap = " + c.multiply(ap) + ", ap*c = " + ap.multiply(c)); 339 throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap + ", c = " + c); 340 } 341 //Q = p[i].multiply(a, e); 342 //S = S.subtract(Q); 343 fac = row.get(i); 344 if (fac == null) { 345 fac = (GenSolvablePolynomial<C>) zero.sum(a, e); 346 } else { // doAddTo ?? 347 fac = (GenSolvablePolynomial<C>) fac.sum(a, e); 348 } 349 row.set(i, fac); 350 } 351 } 352 return R; 353 } 354 355 356 /** 357 * Left normalform with factor. 358 * @param Pp polynomial list. 359 * @param Ap polynomial. 360 * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor 361 * for Ap. 362 */ 363 @SuppressWarnings("unchecked") 364 public PseudoReductionEntry<C> leftNormalformFactor(List<GenSolvablePolynomial<C>> Pp, 365 GenSolvablePolynomial<C> Ap) { 366 if (Ap == null) { 367 return null; 368 } 369 C mfac = Ap.ring.getONECoefficient(); 370 PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac); 371 if (Pp == null || Pp.isEmpty()) { 372 return pf; 373 } 374 if (Ap.isZERO()) { 375 return pf; 376 } 377 Map.Entry<ExpVector, C> m; 378 GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0]; 379 synchronized (Pp) { 380 P = Pp.toArray(P); 381 } 382 int l = P.length; 383 ExpVector[] htl = new ExpVector[l]; 384 //C[] lbc = (C[]) new GcdRingElem[l]; 385 GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l]; 386 int i; 387 int j = 0; 388 for (i = 0; i < l; i++) { 389 if (P[i] == null) { 390 continue; 391 } 392 p[i] = P[i]; 393 m = p[i].leadingMonomial(); 394 if (m != null) { 395 p[j] = p[i]; 396 htl[j] = m.getKey(); 397 //lbc[j] = m.getValue(); 398 j++; 399 } 400 } 401 l = j; 402 ExpVector e; 403 C a; 404 boolean mt = false; 405 GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy(); 406 GenSolvablePolynomial<C> Q = null; 407 GenSolvablePolynomial<C> S = Ap.copy(); 408 while (S.length() > 0) { 409 m = S.leadingMonomial(); 410 e = m.getKey(); 411 a = m.getValue(); 412 for (i = 0; i < l; i++) { 413 mt = e.multipleOf(htl[i]); 414 if (mt) 415 break; 416 } 417 if (!mt) { 418 //logger.debug("irred"); 419 //R = R.sum(a, e); 420 //S = S.subtract(a, e); 421 R.doPutToMap(e, a); 422 S.doRemoveFromMap(e, a); 423 //System.out.println(" S = " + S); 424 } else { 425 e = e.subtract(htl[i]); 426 //logger.info("red div = " + e); 427 Q = p[i].multiplyLeft(e); 428 C c = Q.leadingBaseCoefficient(); 429 ExpVector g = S.leadingExpVector(); 430 C ap = a; 431 if (a.remainder(c).isZERO()) { 432 a = a.divide(c); 433 S = S.subtractMultiple(a, Q); 434 } else { 435 mfac = c.multiply(mfac); // left 436 R = R.multiplyLeft(c); 437 S = S.scaleSubtractMultiple(c, a, Q); 438 } 439 ExpVector h = S.leadingExpVector(); 440 if (g.equals(h)) { // Ore condition not fulfilled 441 logger.info("g==h: g = " + g + ", c = " + c); 442 throw new RuntimeException("g==h: a = " + a + ", ap = " + ap); 443 } 444 } 445 } 446 if (logger.isDebugEnabled()) { 447 logger.info("multiplicative factor = " + mfac); 448 } 449 pf = new PseudoReductionEntry<C>(R, mfac); 450 return pf; 451 } 452 453 454 /** 455 * Right normalform. 456 * @param Ap polynomial. 457 * @param Pp polynomial list. 458 * @return nf(Ap) with respect to Pp. <b>Note: </b> not implemented; 459 */ 460 @SuppressWarnings({ "unchecked" }) 461 public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> Pp, 462 GenSolvablePolynomial<C> Ap) { 463 //throw new UnsupportedOperationException(); 464 if (Pp == null || Pp.isEmpty()) { 465 return Ap; 466 } 467 if (Ap == null || Ap.isZERO()) { 468 return Ap; 469 } 470 Map.Entry<ExpVector, C> m; 471 GenSolvablePolynomial<C>[] P = new GenSolvablePolynomial[0]; 472 synchronized (Pp) { 473 P = Pp.toArray(P); 474 } 475 int l = P.length; 476 ExpVector[] htl = new ExpVector[l]; 477 //C[] lbc = (C[]) new GcdRingElem[l]; 478 GenSolvablePolynomial<C>[] p = new GenSolvablePolynomial[l]; 479 int i; 480 int j = 0; 481 for (i = 0; i < l; i++) { 482 if (P[i] == null) { 483 continue; 484 } 485 p[i] = P[i]; 486 m = p[i].leadingMonomial(); 487 if (m != null) { 488 p[j] = p[i]; 489 htl[j] = m.getKey(); 490 //lbc[j] = m.getValue(); 491 j++; 492 } 493 } 494 l = j; 495 ExpVector e; 496 C a; 497 boolean mt = false; 498 GenSolvablePolynomial<C> R = Ap.ring.getZERO().copy(); 499 GenSolvablePolynomial<C> Q = null; 500 GenSolvablePolynomial<C> S = Ap.copy(); 501 while (S.length() > 0) { 502 m = S.leadingMonomial(); 503 e = m.getKey(); 504 a = m.getValue(); 505 for (i = 0; i < l; i++) { 506 mt = e.multipleOf(htl[i]); 507 if (mt) 508 break; 509 } 510 if (!mt) { 511 //logger.debug("irred"); 512 //R = R.sum(a, e); 513 //S = S.subtract(a, e); 514 R.doPutToMap(e, a); 515 S.doRemoveFromMap(e, a); 516 //System.out.println(" S = " + S); 517 } else { 518 e = e.subtract(htl[i]); 519 //logger.info("red div = " + e); 520 // need pi * a * e, but only pi * e * a or a * pi * e available 521 Q = p[i].multiply(e); 522 assert Q.multiply(a).equals(Q.multiplyLeft(a)); 523 C c = Q.leadingBaseCoefficient(); 524 ExpVector g = S.leadingExpVector(); 525 C ap = a; 526 if (a.remainder(c).isZERO()) { 527 a = a.divide(c); // left? 528 //S = S.subtractMultiple(Q,a); 529 S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a)); 530 } else { 531 R = R.multiply(c); 532 S = S.multiply(c); 533 //S = S.scaleSubtractMultiple(c, Q, a); 534 S = (GenSolvablePolynomial<C>) S.subtract(Q.multiply(a)); 535 } 536 ExpVector h = S.leadingExpVector(); 537 if (g.equals(h)) { // Ore condition not fulfilled 538 logger.info("g==h: g = " + g + ", c = " + c); 539 throw new RuntimeException("g.equals(h): a = " + a + ", ap = " + ap); 540 } 541 } 542 } 543 //System.out.println("R = " + R); 544 return R; 545 } 546 547 548 /** 549 * Right normalform recursive. 550 * @param Ap recursive polynomial. 551 * @param Pp recursive polynomial list. 552 * @return nf(Ap) with respect to Pp. <b>Note: </b> not implemented; 553 */ 554 @SuppressWarnings("unused") 555 public GenSolvablePolynomial<GenPolynomial<C>> rightNormalformRecursive( 556 List<GenSolvablePolynomial<GenPolynomial<C>>> Pp, 557 GenSolvablePolynomial<GenPolynomial<C>> Ap) { 558 throw new UnsupportedOperationException(); // TODO 559 } 560 561 562 /** 563 * Left normalform with recording. <b>Note:</b> Only meaningful if all 564 * divisions are exact. Compute first the multiplication factor 565 * <code>m</code> with <code>normalform(Pp,Ap,m)</code>, then call this 566 * method with <code>normalform(row,Pp,m*Ap)</code>. 567 * @param row recording matrix, is modified. 568 * @param Pp a polynomial list for reduction. 569 * @param Ap a polynomial. 570 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. <b>Note: </b> not 571 * implemented; 572 */ 573 @SuppressWarnings("unused") 574 public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> row, 575 List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap) { 576 throw new UnsupportedOperationException(); // TODO 577 } 578 579 580 /** 581 * Right normalform with multiplication factor. 582 * @param Pp polynomial list. 583 * @param Ap polynomial. 584 * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor 585 * for Ap. <b>Note: </b> not implemented; 586 */ 587 @SuppressWarnings("unused") 588 public PseudoReductionEntry<C> rightNormalformFactor(List<GenSolvablePolynomial<C>> Pp, 589 GenSolvablePolynomial<C> Ap) { 590 throw new UnsupportedOperationException(); // TODO 591 } 592 593}