001/* 002 * $Id: WordReductionSeq.java 5364 2015-12-26 12:36:37Z 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.GenWordPolynomial; 015import edu.jas.poly.Word; 016import edu.jas.structure.RingElem; 017 018 019/** 020 * Polynomial word reduction sequential use algorithm. Implements normalform. 021 * @param <C> coefficient type 022 * @author Heinz Kredel 023 */ 024 025public class WordReductionSeq<C extends RingElem<C>> // should be FieldElem<C>> 026 extends WordReductionAbstract<C> { 027 028 029 private static final Logger logger = Logger.getLogger(WordReductionSeq.class); 030 031 032 private static boolean debug = logger.isDebugEnabled(); 033 034 035 /** 036 * Constructor. 037 */ 038 public WordReductionSeq() { 039 } 040 041 042 /** 043 * Normalform. 044 * @param Ap polynomial. 045 * @param Pp polynomial list. 046 * @return nf(Ap) with respect to Pp. 047 */ 048 @SuppressWarnings("unchecked") 049 public GenWordPolynomial<C> normalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 050 if (Pp == null || Pp.isEmpty()) { 051 return Ap; 052 } 053 if (Ap == null || Ap.isZERO()) { 054 return Ap; 055 } 056 if (!Ap.ring.coFac.isField()) { 057 throw new IllegalArgumentException("coefficients not from a field"); 058 } 059 Map.Entry<Word, C> m; 060 int l; 061 GenWordPolynomial<C>[] P; 062 synchronized (Pp) { 063 l = Pp.size(); 064 P = new GenWordPolynomial[l]; 065 //P = Pp.toArray(); 066 for (int i = 0; i < Pp.size(); i++) { 067 P[i] = Pp.get(i); 068 } 069 } 070 Word[] htl = new Word[l]; 071 C[] lbc = (C[]) new RingElem[l]; // want C[] 072 GenWordPolynomial<C>[] p = new GenWordPolynomial[l]; 073 int i; 074 int j = 0; 075 for (i = 0; i < l; i++) { 076 p[i] = P[i]; 077 m = p[i].leadingMonomial(); 078 if (m != null) { 079 p[j] = p[i]; 080 htl[j] = m.getKey(); 081 lbc[j] = m.getValue(); 082 j++; 083 } 084 } 085 l = j; 086 Word e, f, g; 087 C a; 088 boolean mt = false; 089 GenWordPolynomial<C> R = Ap.ring.getZERO(); 090 C cone = Ap.ring.coFac.getONE(); 091 092 //GenWordPolynomial<C> T = null; 093 GenWordPolynomial<C> Q = null; 094 GenWordPolynomial<C> S = Ap; 095 while (S.length() > 0) { 096 m = S.leadingMonomial(); 097 e = m.getKey(); 098 a = m.getValue(); 099 for (i = 0; i < l; i++) { 100 mt = e.multipleOf(htl[i]); 101 if (mt) 102 break; 103 } 104 if (!mt) { 105 //logger.debug("irred"); 106 //T = new OrderedMapPolynomial( a, e ); 107 R = R.sum(a, e); 108 S = S.subtract(a, e); 109 // System.out.println(" S = " + S); 110 } else { 111 Word[] elr = e.divideWord(htl[i]); 112 g = e; 113 e = elr[0]; 114 f = elr[1]; 115 if (debug) { 116 logger.info("red divideWord: e = " + e + ", f = " + f); 117 } 118 a = a.divide(lbc[i]); 119 Q = p[i].multiply(a, e, cone, f); 120 S = S.subtract(Q); 121 if (!S.isZERO() && g.equals(S.leadingWord())) { 122 throw new RuntimeException("HT(S) not descending"); 123 } 124 } 125 } 126 return R; 127 } 128 129 130 /** 131 * Normalform with left and right recording. 132 * @param lrow left recording matrix, is modified. 133 * @param rrow right recording matrix, is modified. 134 * @param Pp a polynomial list for reduction. 135 * @param Ap a polynomial. 136 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. 137 */ 138 @SuppressWarnings("unchecked") 139 public GenWordPolynomial<C> normalform(List<GenWordPolynomial<C>> lrow, List<GenWordPolynomial<C>> rrow, 140 List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 141 if (Pp == null || Pp.isEmpty()) { 142 return Ap; 143 } 144 if (Ap == null || Ap.isZERO()) { 145 return Ap; 146 } 147 if (!Ap.ring.coFac.isField()) { 148 throw new IllegalArgumentException("coefficients not from a field"); 149 } 150 int l = Pp.size(); 151 GenWordPolynomial<C>[] P = new GenWordPolynomial[l]; 152 synchronized (Pp) { 153 //P = Pp.toArray(); 154 for (int i = 0; i < Pp.size(); i++) { 155 P[i] = Pp.get(i); 156 } 157 } 158 Word[] htl = new Word[l]; 159 C[] lbc = (C[]) new RingElem[l]; 160 GenWordPolynomial<C>[] p = new GenWordPolynomial[l]; 161 Map.Entry<Word, C> m; 162 int j = 0; 163 int i; 164 for (i = 0; i < l; i++) { 165 p[i] = P[i]; 166 m = p[i].leadingMonomial(); 167 if (m != null) { 168 p[j] = p[i]; 169 htl[j] = m.getKey(); 170 lbc[j] = m.getValue(); 171 j++; 172 } 173 } 174 l = j; 175 Word e, g; 176 C a, b, lc, rc; 177 boolean mt = false; 178 GenWordPolynomial<C> zero = Ap.ring.getZERO(); 179 GenWordPolynomial<C> one = Ap.ring.getONE(); 180 GenWordPolynomial<C> R = Ap.ring.getZERO(); 181 C cone = Ap.ring.coFac.getONE(); 182 // ensure polynomials at each index 183 for (i = 0; i < lrow.size(); i++) { 184 GenWordPolynomial<C> w = lrow.get(i); 185 if (w == null) { 186 lrow.set(i, zero); 187 } 188 w = rrow.get(i); 189 if (w == null) { 190 rrow.set(i, zero); 191 } 192 } 193 194 GenWordPolynomial<C> fac = null; 195 // GenWordPolynomial<C> T = null; 196 GenWordPolynomial<C> Q = null; 197 GenWordPolynomial<C> S = Ap; 198 while (S.length() > 0) { 199 m = S.leadingMonomial(); 200 e = m.getKey(); 201 a = m.getValue(); 202 for (i = 0; i < l; i++) { 203 mt = e.multipleOf(htl[i]); 204 if (mt) 205 break; 206 } 207 if (!mt) { 208 //logger.debug("irred"); 209 R = R.sum(a, e); 210 S = S.subtract(a, e); 211 // System.out.println("S = " + S); 212 } else { 213 g = e; 214 Word[] elr = e.divideWord(htl[i]); 215 e = elr[0]; 216 Word f = elr[1]; 217 if (debug) { 218 logger.info("redRec divideWord: e = " + e + ", f = " + f + ", htl = " + htl[i]); 219 } 220 C c = lbc[i]; 221 b = a.divide(c); 222 if (e.isONE()) { // TODO 223 lc = cone; 224 rc = b; 225 } else { 226 lc = b; 227 rc = cone; 228 } 229 Q = p[i].multiply(lc, e, rc, f); 230 S = S.subtract(Q); 231 //logger.info("redRec: S = " + S + ", R = " + R + ", Q = " + Q); 232 if (!S.isZERO() && g.equals(S.leadingWord())) { 233 System.out.println("divideWord: e = " + e + ", f = " + f); 234 System.out.println("R = " + R); 235 System.out.println("Q = " + Q + ", a = " + a + ", b = " + b + ", c = " + c); 236 throw new RuntimeException("HT(S) not descending, S = " + S); 237 } 238 // left row 239 fac = lrow.get(i); 240 boolean doset = true; 241 if (!lc.isONE() || !e.isONE()) { 242 if (!fac.coefficient(e).isZERO()) { 243 logger.warn("e exists in polynomial: " + fac + ", e = " + e + ", lc = " + lc); 244 logger.warn("f = " + f + ", rc = " + rc); 245 logger.warn("S = " + S + ", R = " + R); 246 } 247 fac = fac.sum(lc, e); 248 doset = false; 249 } 250 //logger.info("redRec: left = " + fac + ", lc = " + lc + ", e = " + e); 251 lrow.set(i, fac); 252 // right row 253 fac = rrow.get(i); 254 if (!rc.isONE() || !f.isONE() || doset) { 255 if (!fac.coefficient(f).isZERO()) { 256 logger.warn("f exists in polynomial: " + fac + ", f = " + f + ", rc = " + rc); 257 logger.warn("e = " + e + ", lc = " + lc); 258 logger.warn("S = " + S + ", R = " + R); 259 } 260 fac = fac.sum(rc, f); 261 } 262 //logger.info("redRec: right = " + fac + ", rc = " + rc + ", f = " + f); 263 rrow.set(i, fac); 264 } 265 } 266 // set factor to one if other non-zero 267 for (i = 0; i < lrow.size(); i++) { 268 GenWordPolynomial<C> lw = lrow.get(i); 269 GenWordPolynomial<C> rw = rrow.get(i); 270 if (!lw.isZERO() && rw.isZERO()) { 271 rrow.set(i, one); 272 } 273 if (lw.isZERO() && !rw.isZERO()) { 274 lrow.set(i, one); 275 } 276 } 277 return R; 278 } 279 280 281 /** 282 * Left normalform with recording. 283 * @param Pp a polynomial list for reduction. 284 * @param Ap a polynomial. 285 * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp. 286 */ 287 public GenWordPolynomial<C> leftNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 288 if (Pp == null || Pp.isEmpty()) { 289 return Ap; 290 } 291 if (Ap == null || Ap.isZERO()) { 292 return Ap; 293 } 294 List<GenWordPolynomial<C>> lrow = new ArrayList<GenWordPolynomial<C>>(Pp.size()); 295 for (int i = 0; i < Pp.size(); i++) { 296 lrow.add(Ap.ring.getZERO()); 297 } 298 GenWordPolynomial<C> r = leftNormalform(lrow, Pp, Ap); 299 return r; 300 } 301 302 303 /** 304 * Left normalform with recording. 305 * @param lrow left recording matrix, is modified. 306 * @param Pp a polynomial list for reduction. 307 * @param Ap a polynomial. 308 * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp. 309 */ 310 @SuppressWarnings("unchecked") 311 public GenWordPolynomial<C> leftNormalform(List<GenWordPolynomial<C>> lrow, 312 List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 313 if (Pp == null || Pp.isEmpty()) { 314 return Ap; 315 } 316 if (Ap == null || Ap.isZERO()) { 317 return Ap; 318 } 319 if (!Ap.ring.coFac.isField()) { 320 throw new IllegalArgumentException("coefficients not from a field"); 321 } 322 int l = Pp.size(); 323 GenWordPolynomial<C>[] P = new GenWordPolynomial[l]; 324 synchronized (Pp) { 325 //P = Pp.toArray(); 326 for (int i = 0; i < Pp.size(); i++) { 327 P[i] = Pp.get(i); 328 } 329 } 330 Word[] htl = new Word[l]; 331 C[] lbc = (C[]) new RingElem[l]; // want C[] 332 GenWordPolynomial<C>[] p = new GenWordPolynomial[l]; 333 Map.Entry<Word, C> m; 334 int j = 0; 335 int i; 336 for (i = 0; i < l; i++) { 337 p[i] = P[i]; 338 m = p[i].leadingMonomial(); 339 if (m != null) { 340 p[j] = p[i]; 341 htl[j] = m.getKey(); 342 lbc[j] = m.getValue(); 343 j++; 344 } 345 } 346 l = j; 347 Word e; 348 C a; 349 boolean mt = false; 350 GenWordPolynomial<C> zero = Ap.ring.getZERO(); 351 GenWordPolynomial<C> R = Ap.ring.getZERO(); 352 C cone = Ap.ring.coFac.getONE(); 353 354 GenWordPolynomial<C> fac = null; 355 // GenWordPolynomial<C> T = null; 356 GenWordPolynomial<C> Q = null; 357 GenWordPolynomial<C> S = Ap; 358 while (S.length() > 0) { 359 m = S.leadingMonomial(); 360 e = m.getKey(); 361 a = m.getValue(); 362 for (i = 0; i < l; i++) { 363 mt = e.multipleOf(htl[i]); 364 if (mt) 365 break; 366 } 367 if (!mt) { 368 //logger.info("irred_1"); 369 R = R.sum(a, e); 370 S = S.subtract(a, e); 371 // System.out.println(" S = " + S); 372 } else { 373 Word g = e; 374 Word[] elr = e.divideWord(htl[i]); 375 e = elr[0]; 376 Word f = elr[1]; 377 if (debug) { 378 logger.info("redRec divideWord: e = " + e + ", f = " + f); 379 } 380 if (f.isONE()) { 381 C c = lbc[i]; 382 //System.out.println("a = " + a + ", c = " + c); 383 a = a.divide(c); 384 //System.out.println("a/c = " + a); 385 Q = p[i].multiply(a, e, cone, f); 386 S = S.subtract(Q); 387 // left row 388 fac = lrow.get(i); 389 if (fac == null) { 390 fac = zero.sum(a, e); 391 } else { 392 fac = fac.sum(a, e); 393 } 394 lrow.set(i, fac); 395 } else { 396 //logger.info("irred_2"); 397 R = R.sum(a, g); 398 S = S.subtract(a, g); 399 } 400 } 401 } 402 return R; 403 } 404 405 406 /** 407 * Right normalform with recording. 408 * @param Pp a polynomial list for reduction. 409 * @param Ap a polynomial. 410 * @return nf(Pp,Ap), the right normal form of Ap wrt. Pp. 411 */ 412 public GenWordPolynomial<C> rightNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 413 if (Pp == null || Pp.isEmpty()) { 414 return Ap; 415 } 416 if (Ap == null || Ap.isZERO()) { 417 return Ap; 418 } 419 List<GenWordPolynomial<C>> lrow = new ArrayList<GenWordPolynomial<C>>(Pp.size()); 420 for (int i = 0; i < Pp.size(); i++) { 421 lrow.add(Ap.ring.getZERO()); 422 } 423 GenWordPolynomial<C> r = rightNormalform(lrow, Pp, Ap); 424 return r; 425 } 426 427 428 /** 429 * Right normalform with recording. 430 * @param rrow right recording matrix, is modified. 431 * @param Pp a polynomial list for reduction. 432 * @param Ap a polynomial. 433 * @return nf(Pp,Ap), the right normal form of Ap wrt. Pp. 434 */ 435 @SuppressWarnings("unchecked") 436 public GenWordPolynomial<C> rightNormalform(List<GenWordPolynomial<C>> rrow, 437 List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 438 if (Pp == null || Pp.isEmpty()) { 439 return Ap; 440 } 441 if (Ap == null || Ap.isZERO()) { 442 return Ap; 443 } 444 if (!Ap.ring.coFac.isField()) { 445 throw new IllegalArgumentException("coefficients not from a field"); 446 } 447 int l = Pp.size(); 448 GenWordPolynomial<C>[] P = new GenWordPolynomial[l]; 449 synchronized (Pp) { 450 //P = Pp.toArray(); 451 for (int i = 0; i < Pp.size(); i++) { 452 P[i] = Pp.get(i); 453 } 454 } 455 Word[] htl = new Word[l]; 456 C[] lbc = (C[]) new RingElem[l]; // want C[] 457 GenWordPolynomial<C>[] p = new GenWordPolynomial[l]; 458 Map.Entry<Word, C> m; 459 int j = 0; 460 int i; 461 for (i = 0; i < l; i++) { 462 p[i] = P[i]; 463 m = p[i].leadingMonomial(); 464 if (m != null) { 465 p[j] = p[i]; 466 htl[j] = m.getKey(); 467 lbc[j] = m.getValue(); 468 j++; 469 } 470 } 471 l = j; 472 Word e; 473 C a; 474 boolean mt = false; 475 GenWordPolynomial<C> zero = Ap.ring.getZERO(); 476 GenWordPolynomial<C> R = Ap.ring.getZERO(); 477 C cone = Ap.ring.coFac.getONE(); 478 479 GenWordPolynomial<C> fac = null; 480 // GenWordPolynomial<C> T = null; 481 GenWordPolynomial<C> Q = null; 482 GenWordPolynomial<C> S = Ap; 483 while (S.length() > 0) { 484 m = S.leadingMonomial(); 485 e = m.getKey(); 486 a = m.getValue(); 487 for (i = 0; i < l; i++) { 488 mt = e.multipleOf(htl[i]); 489 if (mt) 490 break; 491 } 492 if (!mt) { 493 //logger.info("irred_1"); 494 R = R.sum(a, e); 495 S = S.subtract(a, e); 496 // System.out.println(" S = " + S); 497 } else { 498 Word g = e; 499 Word[] elr = e.divideWord(htl[i]); 500 e = elr[0]; 501 Word f = elr[1]; 502 if (debug) { 503 logger.info("redRec divideWord: e = " + e + ", f = " + f); 504 } 505 if (e.isONE()) { 506 C c = lbc[i]; 507 //System.out.println("a = " + a + ", c = " + c); 508 a = a.divide(c); 509 //System.out.println("a/c = " + a); 510 Q = p[i].multiply(cone, e, a, f); 511 S = S.subtract(Q); 512 // left row 513 fac = rrow.get(i); 514 if (fac == null) { 515 fac = zero.sum(a, f); 516 } else { 517 fac = fac.sum(a, f); 518 } 519 rrow.set(i, fac); 520 } else { 521 //logger.info("irred_2"); 522 R = R.sum(a, g); 523 S = S.subtract(a, g); 524 } 525 } 526 } 527 return R; 528 } 529 530}