001/* 002 * $Id: RPseudoReductionSeq.java 5046 2014-12-30 16:46:04Z 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.poly.ExpVector; 014import edu.jas.poly.GenPolynomial; 015import edu.jas.structure.RegularRingElem; 016 017 018/** 019 * Polynomial regular ring pseudo reduction sequential use algorithm. Implements 020 * fraction free normalform algorithm. 021 * @param <C> coefficient type 022 * @author Heinz Kredel 023 */ 024 025public class RPseudoReductionSeq<C extends RegularRingElem<C>> extends RReductionSeq<C> implements 026 RPseudoReduction<C> { 027 028 029 private static final Logger logger = Logger.getLogger(RPseudoReductionSeq.class); 030 031 032 private final boolean debug = logger.isDebugEnabled(); 033 034 035 /** 036 * Constructor. 037 */ 038 public RPseudoReductionSeq() { 039 } 040 041 042 /** 043 * Normalform using r-reduction. 044 * @param Ap polynomial. 045 * @param Pp polynomial list. 046 * @return r-nf(Ap) with respect to Pp. 047 */ 048 @Override 049 @SuppressWarnings("cast") 050 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 051 if (Pp == null || Pp.isEmpty()) { 052 return Ap; 053 } 054 if (Ap == null || Ap.isZERO()) { 055 return Ap; 056 } 057 int l; 058 GenPolynomial<C>[] P; 059 synchronized (Pp) { 060 l = Pp.size(); 061 P = (GenPolynomial<C>[]) new GenPolynomial[l]; 062 //P = Pp.toArray(); 063 for (int i = 0; i < Pp.size(); i++) { 064 P[i] = Pp.get(i); 065 } 066 } 067 //System.out.println("l = " + l); 068 Map.Entry<ExpVector, C> m; 069 ExpVector[] htl = new ExpVector[l]; 070 C[] lbc = (C[]) new RegularRingElem[l]; // want <C> 071 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[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].abs(); 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, f; 089 C a; 090 C r = null; 091 boolean mt = false; 092 GenPolynomial<C> R = Ap.ring.getZERO(); 093 GenPolynomial<C> Q = null; 094 GenPolynomial<C> S = Ap; 095 while (S.length() > 0) { 096 m = S.leadingMonomial(); 097 e = m.getKey(); 098 a = m.getValue(); 099 //System.out.println("--a = " + a); 100 for (i = 0; i < l; i++) { 101 mt = e.multipleOf(htl[i]); 102 if (mt) { 103 C c = lbc[i]; 104 //r = a.idempotent().multiply( c.idempotent() ); 105 r = a.idempotentAnd(c); 106 mt = !r.isZERO(); // && mt 107 if (mt) { 108 f = e.subtract(htl[i]); 109 if (a.remainder(c).isZERO()) { //c.isUnit() ) { 110 a = a.divide(c); 111 if (a.isZERO()) { 112 throw new ArithmeticException("a.isZERO()"); 113 } 114 } else { 115 c = c.fillOne(); 116 S = S.multiply(c); 117 R = R.multiply(c); 118 } 119 Q = p[i].multiply(a, f); 120 S = S.subtract(Q); 121 122 f = S.leadingExpVector(); 123 if (!e.equals(f)) { 124 a = Ap.ring.coFac.getZERO(); 125 break; 126 } 127 a = S.leadingBaseCoefficient(); 128 } 129 } 130 } 131 if (!a.isZERO()) { //! mt ) { 132 //logger.debug("irred"); 133 R = R.sum(a, e); 134 S = S.reductum(); 135 } 136 } 137 return R.abs(); // not monic if not boolean closed 138 } 139 140 141 /** 142 * Normalform using r-reduction. 143 * @param Pp polynomial list. 144 * @param Ap polynomial. 145 * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor 146 * for Ap. 147 */ 148 @SuppressWarnings("cast") 149 public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 150 if (Ap == null) { 151 return null; 152 } 153 C mfac = Ap.ring.getONECoefficient(); 154 PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac); 155 if (Pp == null || Pp.isEmpty()) { 156 return pf; 157 } 158 if (Ap.isZERO()) { 159 return pf; 160 } 161 int l; 162 GenPolynomial<C>[] P; 163 synchronized (Pp) { 164 l = Pp.size(); 165 P = (GenPolynomial<C>[]) new GenPolynomial[l]; 166 //P = Pp.toArray(); 167 for (int i = 0; i < Pp.size(); i++) { 168 P[i] = Pp.get(i); 169 } 170 } 171 //System.out.println("l = " + l); 172 Map.Entry<ExpVector, C> m; 173 ExpVector[] htl = new ExpVector[l]; 174 C[] lbc = (C[]) new RegularRingElem[l]; // want <C> 175 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l]; 176 int i; 177 int j = 0; 178 for (i = 0; i < l; i++) { 179 if (P[i] == null) { 180 continue; 181 } 182 p[i] = P[i].abs(); 183 m = p[i].leadingMonomial(); 184 if (m != null) { 185 p[j] = p[i]; 186 htl[j] = m.getKey(); 187 lbc[j] = m.getValue(); 188 j++; 189 } 190 } 191 l = j; 192 ExpVector e, f; 193 C a; 194 C r = null; 195 boolean mt = false; 196 GenPolynomial<C> R = Ap.ring.getZERO(); 197 GenPolynomial<C> Q = null; 198 GenPolynomial<C> S = Ap; 199 while (S.length() > 0) { 200 m = S.leadingMonomial(); 201 e = m.getKey(); 202 a = m.getValue(); 203 //System.out.println("--a = " + a); 204 for (i = 0; i < l; i++) { 205 mt = e.multipleOf(htl[i]); 206 if (mt) { 207 C c = lbc[i]; 208 //r = a.idempotent().multiply( c.idempotent() ); 209 r = a.idempotentAnd(c); 210 mt = !r.isZERO(); // && mt 211 if (mt) { 212 f = e.subtract(htl[i]); 213 if (a.remainder(c).isZERO()) { //c.isUnit() ) { 214 a = a.divide(c); 215 if (a.isZERO()) { 216 throw new ArithmeticException("a.isZERO()"); 217 } 218 } else { 219 c = c.fillOne(); 220 S = S.multiply(c); 221 R = R.multiply(c); 222 mfac = mfac.multiply(c); 223 } 224 Q = p[i].multiply(a, f); 225 S = S.subtract(Q); 226 227 f = S.leadingExpVector(); 228 if (!e.equals(f)) { 229 a = Ap.ring.coFac.getZERO(); 230 break; 231 } 232 a = S.leadingBaseCoefficient(); 233 } 234 } 235 } 236 if (!a.isZERO()) { //! mt ) { 237 //logger.debug("irred"); 238 R = R.sum(a, e); 239 S = S.reductum(); 240 } 241 } 242 pf = new PseudoReductionEntry<C>(R, mfac); //.abs(); // not monic if not boolean closed 243 return pf; 244 } 245 246 247 /** 248 * Normalform with recording. <b>Note:</b> Only meaningfull if all divisions 249 * are exact. Compute first the multiplication factor <code>m</code> with 250 * <code>normalform(Pp,Ap,m)</code>, then call this method with 251 * <code>normalform(row,Pp,m*Ap)</code>. 252 * @param row recording matrix, is modified. 253 * @param Pp a polynomial list for reduction. 254 * @param Ap a polynomial. 255 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. 256 */ 257 @Override 258 @SuppressWarnings("cast") 259 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, 260 GenPolynomial<C> Ap) { 261 if (Pp == null || Pp.isEmpty()) { 262 return Ap; 263 } 264 if (Ap == null || Ap.isZERO()) { 265 return Ap; 266 } 267 int l; 268 GenPolynomial<C>[] P; 269 synchronized (Pp) { 270 l = Pp.size(); 271 P = (GenPolynomial<C>[]) new GenPolynomial[l]; 272 //P = Pp.toArray(); 273 for (int i = 0; i < Pp.size(); i++) { 274 P[i] = Pp.get(i); 275 } 276 } 277 //System.out.println("l = " + l); 278 Map.Entry<ExpVector, C> m; 279 ExpVector[] htl = new ExpVector[l]; 280 C[] lbc = (C[]) new RegularRingElem[l]; // want <C> 281 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l]; 282 int i; 283 int j = 0; 284 for (i = 0; i < l; i++) { 285 p[i] = P[i]; 286 m = p[i].leadingMonomial(); 287 if (m != null) { 288 p[j] = p[i]; 289 htl[j] = m.getKey(); 290 lbc[j] = m.getValue(); 291 j++; 292 } 293 } 294 l = j; 295 ExpVector e, f; 296 C a, b; 297 C r = null; 298 boolean mt = false; 299 GenPolynomial<C> fac = null; 300 GenPolynomial<C> zero = Ap.ring.getZERO(); 301 GenPolynomial<C> R = Ap.ring.getZERO(); 302 GenPolynomial<C> Q = null; 303 GenPolynomial<C> S = Ap; 304 while (S.length() > 0) { 305 m = S.leadingMonomial(); 306 e = m.getKey(); 307 a = m.getValue(); 308 for (i = 0; i < l; i++) { 309 mt = e.multipleOf(htl[i]); 310 if (mt) { 311 C c = lbc[i]; 312 //r = a.idempotent().multiply( c.idempotent() ); 313 r = a.idempotentAnd(c); 314 //System.out.println("r = " + r); 315 mt = !r.isZERO(); // && mt 316 if (mt) { 317 b = a.remainder(c); 318 if (b.isZERO()) { 319 a = a.divide(c); 320 if (a.isZERO()) { 321 throw new ArithmeticException("a.isZERO()"); 322 } 323 } else { 324 c = c.fillOne(); 325 S = S.multiply(c); 326 R = R.multiply(c); 327 } 328 f = e.subtract(htl[i]); 329 if (debug) { 330 logger.info("red div = " + f); 331 } 332 Q = p[i].multiply(a, f); 333 S = S.subtract(Q); // not ok with reductum 334 335 fac = row.get(i); 336 if (fac == null) { 337 fac = zero.sum(a, f); 338 } else { 339 fac = fac.sum(a, f); 340 } 341 row.set(i, fac); 342 343 f = S.leadingExpVector(); 344 if (!e.equals(f)) { 345 a = Ap.ring.coFac.getZERO(); 346 break; 347 } 348 a = S.leadingBaseCoefficient(); 349 } 350 } 351 } 352 if (!a.isZERO()) { //! mt ) { 353 //logger.debug("irred"); 354 R = R.sum(a, e); 355 S = S.reductum(); 356 } 357 } 358 return R; //.abs(); // not monic if not boolean closed 359 } 360 361 362 /** 363 * Normalform recursive. 364 * @param Ap recursive polynomial. 365 * @param Pp recursive polynomial list. 366 * @return nf(Ap) with respect to Pp. 367 */ 368 @SuppressWarnings("unchecked") 369 public GenPolynomial<GenPolynomial<C>> normalformRecursive(List<GenPolynomial<GenPolynomial<C>>> Pp, 370 GenPolynomial<GenPolynomial<C>> Ap) { 371 throw new UnsupportedOperationException("not implemented"); 372 } 373 374 375 /* 376 * -------- boolean closure stuff ----------------------------------------- 377 * -------- is all in superclass 378 */ 379 380}