001/* 002 * $Id$ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.Map; 011 012import org.apache.logging.log4j.LogManager; 013import org.apache.logging.log4j.Logger; 014 015import edu.jas.poly.ExpVector; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenPolynomialRing; 018import edu.jas.structure.RingElem; 019 020 021/** 022 * Polynomial E-Reduction sequential use algorithm. Implements normalform. 023 * @param <C> coefficient type 024 * @author Heinz Kredel 025 */ 026 027public class EReductionSeq<C extends RingElem<C>> extends DReductionSeq<C> implements EReduction<C> { 028 029 030 private static final Logger logger = LogManager.getLogger(DReductionSeq.class); 031 032 033 /** 034 * Constructor. 035 */ 036 public EReductionSeq() { 037 } 038 039 040 /** 041 * Is top reducible. 042 * @param A polynomial. 043 * @param P polynomial list. 044 * @return true if A is top reducible with respect to P. 045 */ 046 @Override 047 public boolean isTopReducible(List<GenPolynomial<C>> P, GenPolynomial<C> A) { 048 if (P == null || P.isEmpty()) { 049 return false; 050 } 051 if (A == null || A.isZERO()) { 052 return false; 053 } 054 boolean mt = false; 055 ExpVector e = A.leadingExpVector(); 056 C a = A.leadingBaseCoefficient(); 057 for (GenPolynomial<C> p : P) { 058 mt = e.multipleOf(p.leadingExpVector()); 059 if (mt) { 060 C b = p.leadingBaseCoefficient(); 061 C r = a.remainder(b); 062 mt = !r.equals(a); 063 if (mt) { 064 return true; 065 } 066 } 067 } 068 return false; 069 } 070 071 072 /** 073 * Is in Normalform. 074 * @param Ap polynomial. 075 * @param Pp polynomial list. 076 * @return true if Ap is in normalform with respect to Pp. 077 */ 078 @SuppressWarnings("unchecked") 079 @Override 080 public boolean isNormalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 081 if (Pp == null || Pp.isEmpty()) { 082 return true; 083 } 084 if (Ap == null || Ap.isZERO()) { 085 return true; 086 } 087 int l; 088 GenPolynomial<C>[] P; 089 synchronized (Pp) { 090 l = Pp.size(); 091 P = new GenPolynomial[l]; 092 //P = Pp.toArray(); 093 for (int i = 0; i < Pp.size(); i++) { 094 P[i] = Pp.get(i); 095 } 096 } 097 ExpVector[] htl = new ExpVector[l]; 098 C[] lbc = (C[]) new RingElem[l]; // want <C> 099 GenPolynomial<C>[] p = new GenPolynomial[l]; 100 Map.Entry<ExpVector, C> m; 101 int i; 102 int j = 0; 103 for (i = 0; i < l; i++) { 104 p[i] = P[i]; 105 m = p[i].leadingMonomial(); 106 if (m != null) { 107 p[j] = p[i]; 108 htl[j] = m.getKey(); 109 lbc[j] = m.getValue(); 110 j++; 111 } 112 } 113 l = j; 114 boolean mt = false; 115 Map<ExpVector, C> Am = Ap.getMap(); 116 for (Map.Entry<ExpVector, C> me : Am.entrySet()) { 117 ExpVector e = me.getKey(); 118 C a = me.getValue(); //Am.get(e); 119 for (i = 0; i < l; i++) { 120 mt = e.multipleOf(htl[i]); 121 if (mt) { 122 C r = a.remainder(lbc[i]); 123 mt = !r.equals(a); 124 if (mt) { 125 return false; 126 } 127 } 128 } 129 } 130 return true; 131 } 132 133 134 /** 135 * Normalform using e-reduction. 136 * @param Ap polynomial. 137 * @param Pp polynomial list. 138 * @return e-nf(Ap) with respect to Pp. 139 */ 140 @SuppressWarnings("unchecked") 141 @Override 142 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) { 143 if (Pp == null || Pp.isEmpty()) { 144 return Ap; 145 } 146 if (Ap == null || Ap.isZERO()) { 147 return Ap; 148 } 149 int l; 150 GenPolynomial<C>[] P; 151 synchronized (Pp) { 152 l = Pp.size(); 153 P = (GenPolynomial<C>[]) new GenPolynomial[l]; 154 //P = Pp.toArray(); 155 for (int i = 0; i < Pp.size(); i++) { 156 P[i] = Pp.get(i); //.abs(); 157 } 158 } 159 Map.Entry<ExpVector, C> m; 160 ExpVector[] htl = new ExpVector[l]; 161 C[] lbc = (C[]) new RingElem[l]; // want <C> 162 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l]; 163 int i; 164 int j = 0; 165 for (i = 0; i < l; i++) { 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 = null; 177 ExpVector f = null; 178 C a = null; 179 C b = null; 180 C r = null; 181 GenPolynomialRing<C> pfac = Ap.ring; 182 GenPolynomial<C> R = pfac.getZERO(); 183 //GenPolynomial<C> T = pfac.getZERO(); 184 GenPolynomial<C> Q = null; 185 GenPolynomial<C> S = Ap; 186 //try { // required to avoid a compiler error in the while loop 187 while (S.length() > 0) { 188 boolean mt = false; 189 m = S.leadingMonomial(); 190 e = m.getKey(); 191 a = m.getValue(); 192 for (i = 0; i < l; i++) { 193 mt = e.multipleOf(htl[i]); 194 if (mt) { 195 f = e.subtract(htl[i]); 196 //logger.info("red div = {}", f); 197 r = a.remainder(lbc[i]); 198 b = a.divide(lbc[i]); 199 if (f == null) { // compiler produced this case ??? still ? 200 System.out.println("f = null: " + e + ", " + htl[i]); 201 Q = p[i].multiply(b); 202 } else { 203 Q = p[i].multiply(b, f); 204 } 205 S = S.subtract(Q); // ok also with reductum 206 //System.out.println(" r = " + r); 207 a = r; 208 if (r.isZERO()) { 209 break; 210 } 211 } 212 } 213 if (!a.isZERO()) { //! mt ) { 214 //logger.debug("irred"); 215 R = R.sum(a, e); 216 //S = S.subtract( a, e ); 217 S = S.reductum(); 218 } 219 //System.out.println(" R = " + R); 220 //System.out.println(" S = " + S); 221 } 222 return R; //.abs(); not ok with e-reduction 223 } 224 225 226 /** 227 * Normalform with recording. 228 * @param row recording matrix, is modified. 229 * @param Pp a polynomial list for reduction. 230 * @param Ap a polynomial. 231 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp. 232 */ 233 @Override 234 @SuppressWarnings("unchecked") 235 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, 236 GenPolynomial<C> Ap) { 237 if (Pp == null || Pp.isEmpty()) { 238 return Ap; 239 } 240 if (Ap == null || Ap.isZERO()) { 241 return Ap; 242 } 243 int l; 244 GenPolynomial<C>[] P; 245 synchronized (Pp) { 246 l = Pp.size(); 247 P = (GenPolynomial<C>[]) new GenPolynomial[l]; 248 //P = Pp.toArray(); 249 for (int i = 0; i < Pp.size(); i++) { 250 P[i] = Pp.get(i); //.abs(); 251 } 252 } 253 ExpVector[] htl = new ExpVector[l]; 254 C[] lbc = (C[]) new RingElem[l]; // want <C> 255 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l]; 256 Map.Entry<ExpVector, C> m; 257 int j = 0; 258 int i; 259 for (i = 0; i < l; i++) { 260 p[i] = P[i]; 261 m = p[i].leadingMonomial(); 262 if (m != null) { 263 p[j] = p[i]; 264 htl[j] = m.getKey(); 265 lbc[j] = m.getValue(); 266 j++; 267 } 268 } 269 l = j; 270 ExpVector e = null; 271 ExpVector f = null; 272 C a = null; 273 C b = null; 274 C r = null; 275 GenPolynomialRing<C> pfac = Ap.ring; 276 GenPolynomial<C> R = pfac.getZERO(); 277 GenPolynomial<C> zero = pfac.getZERO(); 278 //System.out.println("row_in = " + row); 279 280 GenPolynomial<C> fac = null; 281 // GenPolynomial<C> T = null; 282 GenPolynomial<C> Q = null; 283 GenPolynomial<C> S = Ap; 284 while (S.length() > 0) { 285 boolean mt = false; 286 m = S.leadingMonomial(); 287 e = m.getKey(); 288 a = m.getValue(); 289 //System.out.println("e = " + e); 290 for (i = 0; i < l; i++) { 291 mt = e.multipleOf(htl[i]); 292 if (mt) { 293 f = e.subtract(htl[i]); 294 //logger.info("red div = {}", f); 295 r = a.remainder(lbc[i]); 296 b = a.divide(lbc[i]); 297 //if (f == null) { // compiler produced this case ??? still ? 298 // System.out.println("f = null: " + e + ", " + htl[i]); 299 // f = pfac.evzero; 300 //} 301 Q = p[i].multiply(b, f); 302 S = S.subtract(Q); 303 fac = row.get(i); 304 if (fac == null) { 305 fac = zero.sum(b, f); 306 } else { 307 fac = fac.sum(b, f); 308 } 309 row.set(i, fac); 310 //System.out.println("i = " + i); 311 //System.out.println("r = " + r); 312 a = r; 313 if (r.isZERO()) { 314 break; 315 } 316 } 317 } 318 if (!a.isZERO()) { //! mt ) { 319 //logger.debug("irred"); 320 R = R.sum(a, e); 321 S = S.subtract(a, e); 322 //??S = S.reductum(); 323 } 324 } 325 return R; 326 } 327 328 329 /** 330 * Irreducible set. 331 * @param Pp polynomial list. 332 * @return a list P of polynomials which are in normalform wrt. P. 333 */ 334 @Override 335 public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) { 336 ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>(); 337 if (Pp == null) { 338 return null; 339 } 340 for (GenPolynomial<C> a : Pp) { 341 if (!a.isZERO()) { 342 P.add(a); 343 } 344 } 345 int l = P.size(); 346 if (l <= 1) 347 return P; 348 349 int irr = 0; 350 ExpVector e; 351 ExpVector f; 352 C c; 353 C d; 354 GenPolynomial<C> a; 355 //Iterator<GenPolynomial<C>> it; 356 logger.debug("irr = "); 357 while (irr != l) { 358 //it = P.listIterator(); 359 //a = P.get(0); //it.next(); 360 a = P.remove(0); 361 e = a.leadingExpVector(); 362 c = a.leadingBaseCoefficient(); 363 a = normalform(P, a); 364 logger.debug(String.valueOf(irr)); 365 if (a.isZERO()) { 366 l--; 367 if (l <= 1) { 368 return P; 369 } 370 } else { 371 f = a.leadingExpVector(); 372 d = a.leadingBaseCoefficient(); 373 if (e.equals(f) && c.equals(d)) { 374 irr++; 375 } else { 376 irr = 0; 377 } 378 P.add(a); 379 } 380 } 381 //System.out.println(); 382 return P; 383 } 384 385 386 // inherit is okay: 387 //public boolean isReductionNF(List<GenPolynomial<C>> row, List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap, 388 // GenPolynomial<C> Np) { 389 390}