001/* 002 * $Id$ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.List; 009import java.util.Map; 010 011import org.apache.logging.log4j.Logger; 012import org.apache.logging.log4j.LogManager; 013 014import edu.jas.gb.ReductionAbstract; 015import edu.jas.poly.ExpVector; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.PolyUtil; 018import edu.jas.structure.RingElem; 019 020 021/** 022 * Polynomial pseudo reduction sequential use algorithm. Coefficients of 023 * polynomials must not be from a field, i.e. the fraction free reduction is 024 * implemented. Implements normalform. 025 * @param <C> coefficient type 026 * @author Heinz Kredel 027 */ 028 029public class PseudoReductionSeq<C extends RingElem<C>> extends ReductionAbstract<C> implements 030 PseudoReduction<C> { 031 032 033 private static final Logger logger = LogManager.getLogger(PseudoReductionSeq.class); 034 035 036 private static final boolean debug = logger.isDebugEnabled(); 037 038 039 /** 040 * Constructor. 041 */ 042 public PseudoReductionSeq() { 043 } 044 045 046 /** 047 * Normalform. 048 * @param Ap polynomial. 049 * @param Pp polynomial list. 050 * @return nf(Ap) with respect to Pp. 051 */ 052 @SuppressWarnings("unchecked") 053 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 054 if (Pp == null || Pp.isEmpty()) { 055 return Ap; 056 } 057 if (Ap == null || Ap.isZERO()) { 058 return Ap; 059 } 060 Map.Entry<ExpVector, C> m; 061 GenPolynomial<C>[] P = new GenPolynomial[0]; 062 synchronized (Pp) { 063 P = Pp.toArray(P); 064 } 065 int l = P.length; 066 ExpVector[] htl = new ExpVector[l]; 067 C[] lbc = (C[]) new RingElem[l]; 068 GenPolynomial<C>[] p = new GenPolynomial[l]; 069 int i; 070 int j = 0; 071 for (i = 0; i < l; i++) { 072 if (P[i] == null) { 073 continue; 074 } 075 p[i] = P[i]; 076 m = p[i].leadingMonomial(); 077 if (m != null) { 078 p[j] = p[i]; 079 htl[j] = m.getKey(); 080 lbc[j] = m.getValue(); 081 j++; 082 } 083 } 084 l = j; 085 ExpVector e, f; 086 C a, b; 087 boolean mt = false; 088 GenPolynomial<C> R = Ap.ring.getZERO().copy(); 089 090 GenPolynomial<C> S = Ap.copy(); 091 while (S.length() > 0) { 092 m = S.leadingMonomial(); 093 e = m.getKey(); 094 a = m.getValue(); 095 for (i = 0; i < l; i++) { 096 mt = e.multipleOf(htl[i]); 097 if (mt) 098 break; 099 } 100 if (!mt) { 101 //logger.debug("irred"); 102 //R = R.sum(a, e); 103 //S = S.subtract(a, e); 104 R.doPutToMap(e, a); 105 S.doRemoveFromMap(e, a); 106 //System.out.println(" S = " + S); 107 } else { 108 f = e.subtract(htl[i]); 109 //logger.info("red div = {}", e); 110 @SuppressWarnings("unchecked") 111 C c = (C) lbc[i]; 112 if (a.remainder(c).isZERO()) { //c.isUnit() ) { 113 b = a.divide(c); 114 GenPolynomial<C> Sp = S.subtractMultiple(b, f, p[i]); 115 if (e.equals(Sp.leadingExpVector())) { // TODO: avoid if possible 116 logger.info("degree not descending: S = {}, Sp = {}", S, Sp); 117 R = R.multiply(c); 118 //S = S.multiply(c); 119 Sp = S.scaleSubtractMultiple(c, a, f, p[i]); 120 } 121 S = Sp; 122 } else { 123 R = R.multiply(c); 124 //S = S.multiply(c); 125 S = S.scaleSubtractMultiple(c, a, f, p[i]); 126 } 127 //Q = p[i].multiply(a, e); 128 //S = S.subtract(Q); 129 } 130 } 131 return R; 132 } 133 134 135 /** 136 * 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 GenPolynomial<GenPolynomial<C>> normalformRecursive(List<GenPolynomial<GenPolynomial<C>>> Pp, 143 GenPolynomial<GenPolynomial<C>> Ap) { 144 if (Pp == null || Pp.isEmpty()) { 145 return Ap; 146 } 147 if (Ap == null || Ap.isZERO()) { 148 return Ap; 149 } 150 Map.Entry<ExpVector, GenPolynomial<C>> m; 151 GenPolynomial<GenPolynomial<C>>[] P = new GenPolynomial[0]; 152 synchronized (Pp) { 153 P = Pp.toArray(P); 154 } 155 int l = P.length; 156 ExpVector[] htl = new ExpVector[l]; 157 GenPolynomial<C>[] lbc = (GenPolynomial<C>[]) new GenPolynomial[l]; 158 GenPolynomial<GenPolynomial<C>>[] p = new GenPolynomial[l]; 159 int i; 160 int j = 0; 161 for (i = 0; i < l; i++) { 162 if (P[i] == null) { 163 continue; 164 } 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 ExpVector e, f; 176 GenPolynomial<C> a, b; 177 boolean mt = false; 178 GenPolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy(); 179 180 GenPolynomial<GenPolynomial<C>> S = Ap.copy(); 181 while (S.length() > 0) { 182 m = S.leadingMonomial(); 183 e = m.getKey(); 184 a = m.getValue(); 185 for (i = 0; i < l; i++) { 186 mt = e.multipleOf(htl[i]); 187 if (mt) 188 break; 189 } 190 if (!mt) { 191 //logger.debug("irred"); 192 //R = R.sum(a, e); 193 //S = S.subtract(a, e); 194 R.doPutToMap(e, a); 195 S.doRemoveFromMap(e, a); 196 //System.out.println(" S = " + S); 197 } else { 198 f = e.subtract(htl[i]); 199 if (debug) { 200 logger.info("red div = {}", f); 201 //logger.info("red a = {}", a); 202 } 203 GenPolynomial<C> c = (GenPolynomial<C>) lbc[i]; 204 //if (a.remainder(c).isZERO()) { //c.isUnit() ) { 205 if (PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) { //c.isUnit() ) { 206 if (debug) { 207 logger.info("red c = {}", c); 208 } 209 //a = a.divide(c); 210 b = PolyUtil.<C> basePseudoDivide(a, c); 211 GenPolynomial<GenPolynomial<C>> Sp = S.subtractMultiple(b, f, p[i]); 212 if (e.equals(Sp.leadingExpVector())) { // TODO: avoid if possible 213 //throw new RuntimeException("degree not descending"); 214 logger.info("degree not descending: S = {}, Sp = {}", S, Sp); 215 R = R.multiply(c); 216 //S = S.multiply(c); 217 Sp = S.scaleSubtractMultiple(c, a, f, p[i]); 218 } 219 S = Sp; 220 } else { 221 R = R.multiply(c); 222 //S = S.multiply(c); 223 S = S.scaleSubtractMultiple(c, a, f, p[i]); 224 } 225 //Q = p[i].multiply(a, e); 226 //S = S.subtract(Q); 227 } 228 } 229 return R; 230 } 231 232 233 /** 234 * Normalform with recording. <b>Note:</b> Only meaningful if all divisions 235 * are exact. Compute first the multiplication factor <code>m</code> with 236 * <code>normalform(Pp,Ap,m)</code>, then call this method with 237 * <code>normalform(row,Pp,m*Ap)</code>. 238 * @param row recording matrix, is modified. 239 * @param Pp a polynomial list for reduction. 240 * @param Ap a polynomial. 241 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. 242 */ 243 @SuppressWarnings("unchecked") 244 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, 245 GenPolynomial<C> Ap) { 246 if (Pp == null || Pp.isEmpty()) { 247 return Ap; 248 } 249 if (Ap == null || Ap.isZERO()) { 250 return Ap; 251 } 252 GenPolynomial<C>[] P = new GenPolynomial[0]; 253 synchronized (Pp) { 254 P = Pp.toArray(P); 255 } 256 int l = P.length; 257 ExpVector[] htl = new ExpVector[l]; 258 Object[] lbc = new Object[l]; // want C 259 GenPolynomial<C>[] p = new GenPolynomial[l]; 260 Map.Entry<ExpVector, C> m; 261 int j = 0; 262 int i; 263 for (i = 0; i < l; i++) { 264 p[i] = P[i]; 265 m = p[i].leadingMonomial(); 266 if (m != null) { 267 p[j] = p[i]; 268 htl[j] = m.getKey(); 269 lbc[j] = m.getValue(); 270 j++; 271 } 272 } 273 l = j; 274 ExpVector e; 275 C a; 276 boolean mt = false; 277 GenPolynomial<C> zero = Ap.ring.getZERO(); 278 GenPolynomial<C> R = Ap.ring.getZERO().copy(); 279 GenPolynomial<C> fac = null; 280 GenPolynomial<C> S = Ap.copy(); 281 while (S.length() > 0) { 282 m = S.leadingMonomial(); 283 e = m.getKey(); 284 a = m.getValue(); 285 for (i = 0; i < l; i++) { 286 mt = e.multipleOf(htl[i]); 287 if (mt) 288 break; 289 } 290 if (!mt) { 291 //logger.debug("irred"); 292 //R = R.sum(a, e); 293 //S = S.subtract(a, e); 294 R.doPutToMap(e, a); 295 S.doRemoveFromMap(e, a); 296 // System.out.println(" S = " + S); 297 } else { 298 e = e.subtract(htl[i]); 299 //logger.info("red div = {}", e); 300 C c = (C) lbc[i]; 301 if (a.remainder(c).isZERO()) { //c.isUnit() ) { 302 a = a.divide(c); 303 S = S.subtractMultiple(a, e, p[i]); 304 //System.out.print("|"); 305 } else { 306 //System.out.print("*"); 307 R = R.multiply(c); 308 //S = S.multiply(c); 309 S = S.scaleSubtractMultiple(c, a, e, p[i]); 310 } 311 //Q = p[i].multiply(a, e); 312 //S = S.subtract(Q); 313 fac = row.get(i); 314 if (fac == null) { 315 fac = zero.sum(a, e); 316 } else { 317 fac = fac.sum(a, e); 318 } 319 row.set(i, fac); 320 } 321 } 322 return R; 323 } 324 325 326 /** 327 * Normalform. 328 * @param Pp polynomial list. 329 * @param Ap polynomial. 330 * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor 331 * for Ap. 332 */ 333 @SuppressWarnings("unchecked") 334 public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 335 if (Ap == null) { 336 return null; 337 } 338 C mfac = Ap.ring.getONECoefficient(); 339 PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac); 340 if (Pp == null || Pp.isEmpty()) { 341 return pf; 342 } 343 if (Ap.isZERO()) { 344 return pf; 345 } 346 Map.Entry<ExpVector, C> m; 347 GenPolynomial<C>[] P = new GenPolynomial[0]; 348 synchronized (Pp) { 349 P = Pp.toArray(P); 350 } 351 int l = P.length; 352 ExpVector[] htl = new ExpVector[l]; 353 C[] lbc = (C[]) new RingElem[l]; // want C[] 354 GenPolynomial<C>[] p = new GenPolynomial[l]; 355 int i; 356 int j = 0; 357 for (i = 0; i < l; i++) { 358 if (P[i] == null) { 359 continue; 360 } 361 p[i] = P[i]; 362 m = p[i].leadingMonomial(); 363 if (m != null) { 364 p[j] = p[i]; 365 htl[j] = m.getKey(); 366 lbc[j] = m.getValue(); 367 j++; 368 } 369 } 370 l = j; 371 ExpVector e; 372 C a; 373 boolean mt = false; 374 GenPolynomial<C> R = Ap.ring.getZERO().copy(); 375 376 GenPolynomial<C> S = Ap.copy(); 377 while (S.length() > 0) { 378 m = S.leadingMonomial(); 379 e = m.getKey(); 380 a = m.getValue(); 381 for (i = 0; i < l; i++) { 382 mt = e.multipleOf(htl[i]); 383 if (mt) 384 break; 385 } 386 if (!mt) { 387 //logger.debug("irred"); 388 //R = R.sum(a, e); 389 //S = S.subtract(a, e); 390 R.doPutToMap(e, a); 391 S.doRemoveFromMap(e, a); 392 //System.out.println(" S = " + S); 393 } else { 394 e = e.subtract(htl[i]); 395 //logger.info("red div = {}", e); 396 C c = lbc[i]; 397 if (a.remainder(c).isZERO()) { //c.isUnit() ) { 398 a = a.divide(c); 399 S = S.subtractMultiple(a, e, p[i]); 400 } else { 401 mfac = mfac.multiply(c); 402 R = R.multiply(c); 403 //S = S.multiply(c); 404 S = S.scaleSubtractMultiple(c, a, e, p[i]); 405 } 406 //Q = p[i].multiply(a, e); 407 //S = S.subtract(Q); 408 } 409 } 410 logger.info("multiplicative factor = {}", mfac); 411 pf = new PseudoReductionEntry<C>(R, mfac); 412 return pf; 413 } 414 415}