001 /*
002 * $Id: RPseudoReductionSeq.java 3423 2010-12-24 10:56:50Z kredel $
003 */
004
005 package edu.jas.gbufd;
006
007
008 import java.util.List;
009 import java.util.Map;
010
011 import org.apache.log4j.Logger;
012
013 import edu.jas.poly.ExpVector;
014 import edu.jas.poly.GenPolynomial;
015 import 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
025 public class RPseudoReductionSeq<C extends RegularRingElem<C>> extends RReductionSeq<C>
026 implements 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("unchecked")
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, b;
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 GenPolynomial<C> Rp, Sp;
096 while (S.length() > 0) {
097 m = S.leadingMonomial();
098 e = m.getKey();
099 a = m.getValue();
100 //System.out.println("--a = " + a);
101 for (i = 0; i < l; i++) {
102 mt = e.multipleOf(htl[i]);
103 if (mt) {
104 C c = lbc[i];
105 //r = a.idempotent().multiply( c.idempotent() );
106 r = a.idempotentAnd(c);
107 mt = !r.isZERO(); // && mt
108 if (mt) {
109 f = e.subtract(htl[i]);
110 if (a.remainder(c).isZERO()) { //c.isUnit() ) {
111 a = a.divide(c);
112 if (a.isZERO()) {
113 throw new ArithmeticException("a.isZERO()");
114 }
115 } else {
116 c = c.fillOne();
117 S = S.multiply(c);
118 R = R.multiply(c);
119 }
120 Q = p[i].multiply(a, f);
121 S = S.subtract(Q);
122
123 f = S.leadingExpVector();
124 if (!e.equals(f)) {
125 a = Ap.ring.coFac.getZERO();
126 break;
127 }
128 a = S.leadingBaseCoefficient();
129 }
130 }
131 }
132 if (!a.isZERO()) { //! mt ) {
133 //logger.debug("irred");
134 R = R.sum(a, e);
135 S = S.reductum();
136 }
137 }
138 return R.abs(); // not monic if not boolean closed
139 }
140
141
142 /**
143 * Normalform using r-reduction.
144 * @param Pp polynomial list.
145 * @param Ap polynomial.
146 * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
147 * for Ap.
148 */
149 @SuppressWarnings("unchecked")
150 public PseudoReductionEntry<C> normalformFactor(List<GenPolynomial<C>> Pp,
151 GenPolynomial<C> Ap) {
152 if (Ap == null) {
153 return null;
154 }
155 C mfac = Ap.ring.getONECoefficient();
156 PseudoReductionEntry<C> pf = new PseudoReductionEntry<C>(Ap, mfac);
157 if (Pp == null || Pp.isEmpty()) {
158 return pf;
159 }
160 if (Ap.isZERO()) {
161 return pf;
162 }
163 int l;
164 GenPolynomial<C>[] P;
165 synchronized (Pp) {
166 l = Pp.size();
167 P = (GenPolynomial<C>[]) new GenPolynomial[l];
168 //P = Pp.toArray();
169 for (int i = 0; i < Pp.size(); i++) {
170 P[i] = Pp.get(i);
171 }
172 }
173 //System.out.println("l = " + l);
174 Map.Entry<ExpVector, C> m;
175 ExpVector[] htl = new ExpVector[l];
176 C[] lbc = (C[]) new RegularRingElem[l]; // want <C>
177 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
178 int i;
179 int j = 0;
180 for (i = 0; i < l; i++) {
181 if (P[i] == null) {
182 continue;
183 }
184 p[i] = P[i].abs();
185 m = p[i].leadingMonomial();
186 if (m != null) {
187 p[j] = p[i];
188 htl[j] = m.getKey();
189 lbc[j] = m.getValue();
190 j++;
191 }
192 }
193 l = j;
194 ExpVector e, f;
195 C a, b;
196 C r = null;
197 boolean mt = false;
198 GenPolynomial<C> R = Ap.ring.getZERO();
199 GenPolynomial<C> Q = null;
200 GenPolynomial<C> S = Ap;
201 GenPolynomial<C> Rp, Sp;
202 while (S.length() > 0) {
203 m = S.leadingMonomial();
204 e = m.getKey();
205 a = m.getValue();
206 //System.out.println("--a = " + a);
207 for (i = 0; i < l; i++) {
208 mt = e.multipleOf(htl[i]);
209 if (mt) {
210 C c = lbc[i];
211 //r = a.idempotent().multiply( c.idempotent() );
212 r = a.idempotentAnd(c);
213 mt = !r.isZERO(); // && mt
214 if (mt) {
215 f = e.subtract(htl[i]);
216 if (a.remainder(c).isZERO()) { //c.isUnit() ) {
217 a = a.divide(c);
218 if (a.isZERO()) {
219 throw new ArithmeticException("a.isZERO()");
220 }
221 } else {
222 c = c.fillOne();
223 S = S.multiply(c);
224 R = R.multiply(c);
225 mfac = mfac.multiply(c);
226 }
227 Q = p[i].multiply(a, f);
228 S = S.subtract(Q);
229
230 f = S.leadingExpVector();
231 if (!e.equals(f)) {
232 a = Ap.ring.coFac.getZERO();
233 break;
234 }
235 a = S.leadingBaseCoefficient();
236 }
237 }
238 }
239 if (!a.isZERO()) { //! mt ) {
240 //logger.debug("irred");
241 R = R.sum(a, e);
242 S = S.reductum();
243 }
244 }
245 pf = new PseudoReductionEntry<C>(R, mfac); //.abs(); // not monic if not boolean closed
246 return pf;
247 }
248
249
250 /**
251 * Normalform with recording. <b>Note:</b> Only meaningfull if all
252 * divisions are exact. Compute first the multiplication factor
253 * <code>m</code> with <code>normalform(Pp,Ap,m)</code>, then call this
254 * method with <code>normalform(row,Pp,m*Ap)</code>.
255 * @param row recording matrix, is modified.
256 * @param Pp a polynomial list for reduction.
257 * @param Ap a polynomial.
258 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
259 */
260 @Override
261 @SuppressWarnings("unchecked")
262 public GenPolynomial<C> normalform(List<GenPolynomial<C>> row,
263 List<GenPolynomial<C>> Pp, GenPolynomial<C> Ap) {
264 if (Pp == null || Pp.isEmpty()) {
265 return Ap;
266 }
267 if (Ap == null || Ap.isZERO()) {
268 return Ap;
269 }
270 int l;
271 GenPolynomial<C>[] P;
272 synchronized (Pp) {
273 l = Pp.size();
274 P = (GenPolynomial<C>[]) new GenPolynomial[l];
275 //P = Pp.toArray();
276 for (int i = 0; i < Pp.size(); i++) {
277 P[i] = Pp.get(i);
278 }
279 }
280 //System.out.println("l = " + l);
281 Map.Entry<ExpVector, C> m;
282 ExpVector[] htl = new ExpVector[l];
283 C[] lbc = (C[]) new RegularRingElem[l]; // want <C>
284 GenPolynomial<C>[] p = (GenPolynomial<C>[]) new GenPolynomial[l];
285 int i;
286 int j = 0;
287 for (i = 0; i < l; i++) {
288 p[i] = P[i];
289 m = p[i].leadingMonomial();
290 if (m != null) {
291 p[j] = p[i];
292 htl[j] = m.getKey();
293 lbc[j] = m.getValue();
294 j++;
295 }
296 }
297 l = j;
298 ExpVector e, f;
299 C a, b;
300 C r = null;
301 boolean mt = false;
302 GenPolynomial<C> fac = null;
303 GenPolynomial<C> zero = Ap.ring.getZERO();
304 GenPolynomial<C> R = Ap.ring.getZERO();
305 GenPolynomial<C> Q = null;
306 GenPolynomial<C> S = Ap;
307 while (S.length() > 0) {
308 m = S.leadingMonomial();
309 e = m.getKey();
310 a = m.getValue();
311 for (i = 0; i < l; i++) {
312 mt = e.multipleOf(htl[i]);
313 if (mt) {
314 C c = lbc[i];
315 //r = a.idempotent().multiply( c.idempotent() );
316 r = a.idempotentAnd(c);
317 //System.out.println("r = " + r);
318 mt = !r.isZERO(); // && mt
319 if (mt) {
320 b = a.remainder(c);
321 if (b.isZERO()) {
322 a = a.divide(c);
323 if (a.isZERO()) {
324 throw new ArithmeticException("a.isZERO()");
325 }
326 } else {
327 c = c.fillOne();
328 S = S.multiply(c);
329 R = R.multiply(c);
330 }
331 f = e.subtract(htl[i]);
332 //logger.info("red div = " + f);
333 Q = p[i].multiply(a, f);
334 S = S.subtract(Q); // not ok with reductum
335
336 fac = row.get(i);
337 if (fac == null) {
338 fac = zero.sum(a, f);
339 } else {
340 fac = fac.sum(a, f);
341 }
342 row.set(i, fac);
343
344 f = S.leadingExpVector();
345 if (!e.equals(f)) {
346 a = Ap.ring.coFac.getZERO();
347 break;
348 }
349 a = S.leadingBaseCoefficient();
350 }
351 }
352 }
353 if (!a.isZERO()) { //! mt ) {
354 //logger.debug("irred");
355 R = R.sum(a, e);
356 S = S.reductum();
357 }
358 }
359 return R; //.abs(); // not monic if not boolean closed
360 }
361
362
363 /*
364 * -------- boolean closure stuff -----------------------------------------
365 * -------- is all in superclass
366 */
367
368 }