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.WordReductionAbstract; 015import edu.jas.poly.GenPolynomial; 016import edu.jas.poly.GenWordPolynomial; 017import edu.jas.poly.PolyUtil; 018import edu.jas.poly.Word; 019import edu.jas.structure.RingElem; 020 021 022/** 023 * Polynomial word reduction sequential use algorithm. Implements normalform. 024 * @param <C> coefficient type 025 * @author Heinz Kredel 026 */ 027 028public class WordPseudoReductionSeq<C extends RingElem<C>> extends WordReductionAbstract<C> implements 029 WordPseudoReduction<C> { 030 031 032 private static final Logger logger = LogManager.getLogger(WordPseudoReductionSeq.class); 033 034 035 private static final boolean debug = logger.isDebugEnabled(); 036 037 038 /** 039 * Constructor. 040 */ 041 public WordPseudoReductionSeq() { 042 } 043 044 045 /** 046 * Normalform. 047 * @param Ap polynomial. 048 * @param Pp polynomial list. 049 * @return nf(Ap) with respect to Pp. 050 */ 051 @SuppressWarnings("unchecked") 052 public GenWordPolynomial<C> normalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 053 if (Pp == null || Pp.isEmpty()) { 054 return Ap; 055 } 056 if (Ap == null || Ap.isZERO()) { 057 return Ap; 058 } 059 if (!Ap.ring.coFac.isCommutative()) { 060 throw new IllegalArgumentException("coefficient ring not commutative"); 061 } 062 Map.Entry<Word, C> m; 063 GenWordPolynomial<C>[] P = new GenWordPolynomial[0]; 064 synchronized (Pp) { 065 P = Pp.toArray(P); 066 } 067 int l = P.length; 068 Word[] htl = new Word[l]; 069 C[] lbc = (C[]) new RingElem[l]; 070 GenWordPolynomial<C>[] p = new GenWordPolynomial[l]; 071 int i; 072 int j = 0; 073 for (i = 0; i < l; i++) { 074 p[i] = P[i]; 075 m = p[i].leadingMonomial(); 076 if (m != null) { 077 p[j] = p[i]; 078 htl[j] = m.getKey(); 079 lbc[j] = m.getValue(); 080 j++; 081 } 082 } 083 l = j; 084 Word e; 085 C a; 086 boolean mt = false; 087 GenWordPolynomial<C> R = Ap.ring.getZERO().copy(); 088 C cone = Ap.ring.coFac.getONE(); 089 GenWordPolynomial<C> Q = null; 090 GenWordPolynomial<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 Word[] elr = e.divideWord(htl[i]); 109 e = elr[0]; 110 Word f = elr[1]; 111 if (debug) { 112 logger.info("red divideWord: e = {}, f = {}", e, f); 113 } 114 C c = lbc[i]; 115 if (a.remainder(c).isZERO()) { 116 a = a.divide(c); 117 Q = p[i].multiply(a, e, cone, f); 118 } else { 119 R = R.multiply(c); 120 S = S.multiply(c); 121 Q = p[i].multiply(a, e, cone, f); 122 } 123 S = S.subtract(Q); 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.isCommutative()) { 148 throw new IllegalArgumentException("coefficient ring not commutative"); 149 } 150 GenWordPolynomial<C>[] P = new GenWordPolynomial[0]; 151 synchronized (Pp) { 152 P = Pp.toArray(P); 153 } 154 int l = P.length; 155 Word[] htl = new Word[l]; 156 C[] lbc = (C[]) new RingElem[l]; 157 GenWordPolynomial<C>[] p = new GenWordPolynomial[l]; 158 Map.Entry<Word, C> m; 159 int j = 0; 160 int i; 161 for (i = 0; i < l; i++) { 162 p[i] = P[i]; 163 m = p[i].leadingMonomial(); 164 if (m != null) { 165 p[j] = p[i]; 166 htl[j] = m.getKey(); 167 lbc[j] = m.getValue(); 168 j++; 169 } 170 } 171 l = j; 172 Word e; 173 C a; 174 boolean mt = false; 175 GenWordPolynomial<C> zero = Ap.ring.getZERO().copy(); 176 GenWordPolynomial<C> R = Ap.ring.getZERO(); 177 C cone = Ap.ring.coFac.getONE(); 178 GenWordPolynomial<C> fac = null; 179 GenWordPolynomial<C> Q = null; 180 GenWordPolynomial<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 Word[] elr = e.divideWord(htl[i]); 199 e = elr[0]; 200 Word f = elr[1]; 201 if (debug) { 202 logger.info("redRec divideWord: e = {}, f = {}", e, f); 203 } 204 C c = lbc[i]; 205 if (a.remainder(c).isZERO()) { 206 a = a.divide(c); 207 Q = p[i].multiply(a, e, cone, f); 208 } else { 209 R = R.multiply(c); 210 S = S.multiply(c); 211 Q = p[i].multiply(a, e, cone, f); 212 } 213 S = S.subtract(Q); 214 // left row 215 fac = lrow.get(i); 216 if (fac == null) { 217 fac = zero.sum(cone, e); 218 } else { 219 fac = fac.sum(cone, e); 220 } 221 lrow.set(i, fac); 222 // right row 223 fac = rrow.get(i); 224 if (fac == null) { 225 fac = zero.sum(a, f); 226 } else { 227 fac = fac.sum(a, f); 228 } 229 rrow.set(i, fac); 230 } 231 } 232 return R; 233 } 234 235 236 /** 237 * Normalform with multiplication factor. 238 * @param Pp polynomial list. 239 * @param Ap polynomial. 240 * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor 241 * for Ap. 242 */ 243 public WordPseudoReductionEntry<C> normalformFactor(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 244 throw new UnsupportedOperationException("normalformFactor not implemented"); 245 } 246 247 248 /** 249 * Normalform with polynomial coefficients. 250 * @param Ap polynomial. 251 * @param Pp polynomial list. 252 * @return nf(Ap) with respect to Pp. 253 */ 254 @SuppressWarnings("unchecked") 255 public GenWordPolynomial<GenPolynomial<C>> normalformRecursive( 256 List<GenWordPolynomial<GenPolynomial<C>>> Pp, GenWordPolynomial<GenPolynomial<C>> Ap) { 257 if (Pp == null || Pp.isEmpty()) { 258 return Ap; 259 } 260 if (Ap == null || Ap.isZERO()) { 261 return Ap; 262 } 263 if (!Ap.ring.coFac.isCommutative()) { 264 throw new IllegalArgumentException("coefficient ring not commutative"); 265 } 266 Map.Entry<Word, GenPolynomial<C>> m; 267 GenWordPolynomial<GenPolynomial<C>>[] P = new GenWordPolynomial[0]; 268 synchronized (Pp) { 269 P = Pp.toArray(P); 270 } 271 int l = P.length; 272 Word[] htl = new Word[l]; 273 GenPolynomial<C>[] lbc = new GenPolynomial[l]; //(GenPolynomial<C>[]) 274 GenWordPolynomial<GenPolynomial<C>>[] p = new GenWordPolynomial[l]; 275 int i; 276 int j = 0; 277 for (i = 0; i < l; i++) { 278 p[i] = P[i]; 279 m = p[i].leadingMonomial(); 280 if (m != null) { 281 p[j] = p[i]; 282 htl[j] = m.getKey(); 283 lbc[j] = m.getValue(); 284 j++; 285 } 286 } 287 l = j; 288 Word e, fr, fl; 289 GenPolynomial<C> a, b = null; 290 boolean mt = false; 291 GenWordPolynomial<GenPolynomial<C>> R = Ap.ring.getZERO().copy(); 292 GenPolynomial<C> cone = Ap.ring.coFac.getONE(); 293 GenWordPolynomial<GenPolynomial<C>> Q = null; 294 GenWordPolynomial<GenPolynomial<C>> S = Ap.copy(); 295 GenWordPolynomial<GenPolynomial<C>> Sp; 296 while (S.length() > 0) { 297 m = S.leadingMonomial(); 298 e = m.getKey(); 299 a = m.getValue(); 300 for (i = 0; i < l; i++) { 301 mt = e.multipleOf(htl[i]); 302 if (mt) 303 break; 304 } 305 if (!mt) { 306 //logger.debug("irred"); 307 //R = R.sum(a, e); 308 //S = S.subtract(a, e); 309 R.doPutToMap(e, a); 310 S.doRemoveFromMap(e, a); 311 // System.out.println(" S = " + S); 312 } else { 313 Word[] elr = e.divideWord(htl[i]); 314 fl = elr[0]; 315 fr = elr[1]; 316 if (debug) { 317 logger.info("redRec divideWord: e = {}, fl = {}, fr = {}", e, fl, fr); 318 } 319 GenPolynomial<C> c = lbc[i]; 320 if (PolyUtil.<C> baseSparsePseudoRemainder(a, c).isZERO()) { 321 b = PolyUtil.<C> basePseudoDivide(a, c); 322 Q = p[i].multiply(b, fl, cone, fr); 323 } else { 324 R = R.multiply(c); 325 S = S.multiply(c); 326 Q = p[i].multiply(a, fl, cone, fr); 327 } 328 Sp = S.subtract(Q); 329 if (e.equals(Sp.leadingWord())) { // TODO: avoid, not possible in general 330 //logger.info("redRec: e = {}, hti = {}, fl = {}, fr = {}", e, htl[i], fl, fr); 331 //logger.info("redRec: S = {}, Sp = {}, a = {}, b = {}, c = {}", S, Sp, a, b, c); 332 //throw new RuntimeException("degree not descending"); 333 R = R.multiply(c); 334 S = S.multiply(c); 335 Q = p[i].multiply(a, fl, cone, fr); 336 Sp = S.subtract(Q); 337 } 338 S = Sp; 339 } 340 } 341 return R; 342 } 343 344 345 @Override 346 public GenWordPolynomial<C> leftNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 347 throw new UnsupportedOperationException("leftNormalform not implemented"); 348 } 349 350 351 @Override 352 public GenWordPolynomial<C> leftNormalform(List<GenWordPolynomial<C>> lrow, 353 List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 354 throw new UnsupportedOperationException("leftNormalform not implemented"); 355 } 356 357 358 @Override 359 public GenWordPolynomial<C> rightNormalform(List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 360 throw new UnsupportedOperationException("rightNormalform not implemented"); 361 } 362 363 364 @Override 365 public GenWordPolynomial<C> rightNormalform(List<GenWordPolynomial<C>> rrow, 366 List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap) { 367 throw new UnsupportedOperationException("rightNormalform not implemented"); 368 } 369 370}