001 /*
002 * $Id: ReductionAbstract.java 3652 2011-06-02 18:17:04Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.ArrayList;
008 import java.util.Iterator;
009 import java.util.List;
010 import java.util.LinkedList;
011 import java.util.Map;
012
013 import org.apache.log4j.Logger;
014
015 import edu.jas.poly.ExpVector;
016 import edu.jas.poly.GenPolynomial;
017 import edu.jas.poly.GenSolvablePolynomial;
018
019 import edu.jas.structure.RingElem;
020
021
022 /**
023 * Polynomial Reduction abstract class.
024 * Implements common S-Polynomial, normalform, criterion 4
025 * module criterion and irreducible set.
026 * @param <C> coefficient type
027 * @author Heinz Kredel
028 */
029
030 public abstract class ReductionAbstract<C extends RingElem<C>>
031 implements Reduction<C> {
032
033 private static final Logger logger = Logger.getLogger(ReductionAbstract.class);
034 private boolean debug = logger.isDebugEnabled();
035
036
037 /**
038 * Constructor.
039 */
040 public ReductionAbstract() {
041 }
042
043
044 /**
045 * S-Polynomial.
046 * @param Ap polynomial.
047 * @param Bp polynomial.
048 * @return spol(Ap,Bp) the S-polynomial of Ap and Bp.
049 */
050 public GenPolynomial<C>
051 SPolynomial(GenPolynomial<C> Ap,
052 GenPolynomial<C> Bp) {
053 if ( Bp == null || Bp.isZERO() ) {
054 if ( Ap == null ) {
055 return Bp;
056 }
057 return Ap.ring.getZERO();
058 }
059 if ( Ap == null || Ap.isZERO() ) {
060 return Bp.ring.getZERO();
061 }
062 if ( debug ) {
063 if ( ! Ap.ring.equals( Bp.ring ) ) {
064 logger.error("rings not equal " + Ap.ring + ", " + Bp.ring);
065 }
066 }
067 Map.Entry<ExpVector,C> ma = Ap.leadingMonomial();
068 Map.Entry<ExpVector,C> mb = Bp.leadingMonomial();
069
070 ExpVector e = ma.getKey();
071 ExpVector f = mb.getKey();
072
073 ExpVector g = e.lcm(f);
074 ExpVector e1 = g.subtract(e);
075 ExpVector f1 = g.subtract(f);
076
077 C a = ma.getValue();
078 C b = mb.getValue();
079
080 GenPolynomial<C> App = Ap.multiply( b, e1 );
081 GenPolynomial<C> Bpp = Bp.multiply( a, f1 );
082 GenPolynomial<C> Cp = App.subtract(Bpp);
083 return Cp;
084 }
085
086
087 /**
088 * S-Polynomial with recording.
089 * @param S recording matrix, is modified.
090 * <b>Note</b> the negative Spolynomial is recorded as
091 * required by all applications.
092 * @param i index of Ap in basis list.
093 * @param Ap a polynomial.
094 * @param j index of Bp in basis list.
095 * @param Bp a polynomial.
096 * @return Spol(Ap, Bp), the S-Polynomial for Ap and Bp.
097 */
098 public GenPolynomial<C>
099 SPolynomial(List<GenPolynomial<C>> S,
100 int i,
101 GenPolynomial<C> Ap,
102 int j,
103 GenPolynomial<C> Bp) {
104 if ( debug ) {
105 if ( Bp == null || Bp.isZERO() ) {
106 throw new ArithmeticException("Spol B is zero");
107 }
108 if ( Ap == null || Ap.isZERO() ) {
109 throw new ArithmeticException("Spol A is zero");
110 }
111 if ( ! Ap.ring.equals( Bp.ring ) ) {
112 logger.error("rings not equal " + Ap.ring + ", " + Bp.ring);
113 }
114 }
115 Map.Entry<ExpVector,C> ma = Ap.leadingMonomial();
116 Map.Entry<ExpVector,C> mb = Bp.leadingMonomial();
117
118 ExpVector e = ma.getKey();
119 ExpVector f = mb.getKey();
120
121 ExpVector g = e.lcm(f);
122 ExpVector e1 = g.subtract(e);
123 ExpVector f1 = g.subtract(f);
124
125 C a = ma.getValue();
126 C b = mb.getValue();
127
128 GenPolynomial<C> App = Ap.multiply( b, e1 );
129 GenPolynomial<C> Bpp = Bp.multiply( a, f1 );
130 GenPolynomial<C> Cp = App.subtract(Bpp);
131
132 GenPolynomial<C> zero = Ap.ring.getZERO();
133 GenPolynomial<C> As = zero.sum( b.negate(), e1 );
134 GenPolynomial<C> Bs = zero.sum( a /*correct .negate()*/, f1 );
135 S.set( i, As );
136 S.set( j, Bs );
137 return Cp;
138 }
139
140
141 /**
142 * Module criterium.
143 * @param modv number of module variables.
144 * @param A polynomial.
145 * @param B polynomial.
146 * @return true if the module S-polynomial(i,j) is required.
147 */
148 public boolean moduleCriterion(int modv,
149 GenPolynomial<C> A,
150 GenPolynomial<C> B) {
151 if ( modv == 0 ) {
152 return true;
153 }
154 ExpVector ei = A.leadingExpVector();
155 ExpVector ej = B.leadingExpVector();
156 return moduleCriterion(modv,ei,ej);
157 }
158
159
160 /**
161 * Module criterium.
162 * @param modv number of module variables.
163 * @param ei ExpVector.
164 * @param ej ExpVector.
165 * @return true if the module S-polynomial(i,j) is required.
166 */
167 public boolean moduleCriterion(int modv, ExpVector ei, ExpVector ej) {
168 if ( modv == 0 ) {
169 return true;
170 }
171 if ( ei.invLexCompareTo( ej, 0, modv ) != 0 ) {
172 return false; // skip pair
173 }
174 return true;
175 }
176
177
178 /**
179 * GB criterium 4.
180 * Use only for commutative polynomial rings.
181 * @param A polynomial.
182 * @param B polynomial.
183 * @param e = lcm(ht(A),ht(B))
184 * @return true if the S-polynomial(i,j) is required, else false.
185 */
186 public boolean criterion4(GenPolynomial<C> A,
187 GenPolynomial<C> B,
188 ExpVector e) {
189 if ( logger.isInfoEnabled() ) {
190 if ( ! A.ring.equals( B.ring ) ) {
191 logger.error("rings not equal " + A.ring + ", " + B.ring);
192 }
193 if ( !A.ring.isCommutative() ) { //B instanceof GenSolvablePolynomial ) {
194 logger.error("GBCriterion4 not applicabable to non-commutative polynomials");
195 return true;
196 }
197 }
198 ExpVector ei = A.leadingExpVector();
199 ExpVector ej = B.leadingExpVector();
200 ExpVector g = ei.sum(ej);
201 // boolean t = g == e ;
202 ExpVector h = g.subtract(e);
203 int s = h.signum();
204 return ! ( s == 0 );
205 }
206
207
208 /**
209 * GB criterium 4.
210 * @param A polynomial.
211 * @param B polynomial.
212 * @return true if the S-polynomial(i,j) is required, else false.
213 */
214 public boolean criterion4(GenPolynomial<C> A,
215 GenPolynomial<C> B) {
216 if ( logger.isInfoEnabled() ) {
217 if ( !A.ring.isCommutative() || !B.ring.isCommutative() ) { // A instanceof GenSolvablePolynomial
218 logger.error("GBCriterion4 not applicabable to non-commutative polynomials");
219 return true;
220 }
221 }
222 ExpVector ei = A.leadingExpVector();
223 ExpVector ej = B.leadingExpVector();
224 ExpVector g = ei.sum(ej);
225 ExpVector e = ei.lcm(ej);
226 // boolean t = g == e ;
227 ExpVector h = g.subtract(e);
228 int s = h.signum();
229 return ! ( s == 0 );
230 }
231
232
233 /**
234 * Normalform Set.
235 * @param Ap polynomial list.
236 * @param Pp polynomial list.
237 * @return list of nf(a) with respect to Pp for all a in Ap.
238 */
239 public List<GenPolynomial<C>> normalform(List<GenPolynomial<C>> Pp,
240 List<GenPolynomial<C>> Ap) {
241 if ( Pp == null || Pp.isEmpty() ) {
242 return Ap;
243 }
244 if ( Ap == null || Ap.isEmpty() ) {
245 return Ap;
246 }
247 ArrayList<GenPolynomial<C>> red
248 = new ArrayList<GenPolynomial<C>>();
249 for ( GenPolynomial<C> A : Ap ) {
250 A = normalform( Pp, A );
251 red.add( A );
252 }
253 return red;
254 }
255
256
257 /**
258 * Is top reducible.
259 * @param A polynomial.
260 * @param P polynomial list.
261 * @return true if A is top reducible with respect to P.
262 */
263 public boolean isTopReducible(List<GenPolynomial<C>> P,
264 GenPolynomial<C> A) {
265 if ( P == null || P.isEmpty() ) {
266 return false;
267 }
268 if ( A == null || A.isZERO() ) {
269 return false;
270 }
271 boolean mt = false;
272 ExpVector e = A.leadingExpVector();
273 for ( GenPolynomial<C> p : P ) {
274 mt = e.multipleOf( p.leadingExpVector() );
275 if ( mt ) {
276 return true;
277 }
278 }
279 return false;
280 }
281
282
283 /**
284 * Is reducible.
285 * @param Ap polynomial.
286 * @param Pp polynomial list.
287 * @return true if Ap is reducible with respect to Pp.
288 */
289 public boolean isReducible(List<GenPolynomial<C>> Pp,
290 GenPolynomial<C> Ap) {
291 return !isNormalform(Pp,Ap);
292 }
293
294
295 /**
296 * Is in Normalform.
297 * @param Ap polynomial.
298 * @param Pp polynomial list.
299 * @return true if Ap is in normalform with respect to Pp.
300 */
301 @SuppressWarnings("unchecked")
302 public boolean isNormalform(List<GenPolynomial<C>> Pp,
303 GenPolynomial<C> Ap) {
304 if ( Pp == null || Pp.isEmpty() ) {
305 return true;
306 }
307 if ( Ap == null || Ap.isZERO() ) {
308 return true;
309 }
310 int l;
311 GenPolynomial<C>[] P;
312 synchronized (Pp) {
313 l = Pp.size();
314 P = new GenPolynomial[l];
315 //P = Pp.toArray();
316 for ( int i = 0; i < Pp.size(); i++ ) {
317 P[i] = Pp.get(i);
318 }
319 }
320 ExpVector[] htl = new ExpVector[ l ];
321 GenPolynomial<C>[] p = new GenPolynomial[ l ];
322 Map.Entry<ExpVector,C> m;
323 int i;
324 int j = 0;
325 for ( i = 0; i < l; i++ ) {
326 p[i] = P[i];
327 m = p[i].leadingMonomial();
328 if ( m != null ) {
329 p[j] = p[i];
330 htl[j] = m.getKey();
331 j++;
332 }
333 }
334 l = j;
335 boolean mt = false;
336 for ( ExpVector e : Ap.getMap().keySet() ) {
337 for ( i = 0; i < l; i++ ) {
338 mt = e.multipleOf( htl[i] );
339 if ( mt ) {
340 return false;
341 }
342 }
343 }
344 return true;
345 }
346
347
348 /**
349 * Is in Normalform.
350 * @param Pp polynomial list.
351 * @return true if each Ap in Pp is in normalform with respect to Pp\{Ap}.
352 */
353 public boolean isNormalform( List<GenPolynomial<C>> Pp ) {
354 if ( Pp == null || Pp.isEmpty() ) {
355 return true;
356 }
357 GenPolynomial<C> Ap;
358 List<GenPolynomial<C>> P = new LinkedList<GenPolynomial<C>>( Pp );
359 int s = P.size();
360 for ( int i = 0; i < s; i++ ) {
361 Ap = P.remove(i);
362 if ( ! isNormalform(P,Ap) ) {
363 return false;
364 }
365 P.add(Ap);
366 }
367 return true;
368 }
369
370
371 /**
372 * Irreducible set.
373 * @param Pp polynomial list.
374 * @return a list P of monic polynomials which are in normalform wrt. P and with ideal(Pp) = ideal(P).
375 */
376 public List<GenPolynomial<C>> irreducibleSet(List<GenPolynomial<C>> Pp) {
377 ArrayList<GenPolynomial<C>> P = new ArrayList<GenPolynomial<C>>();
378 for ( GenPolynomial<C> a : Pp ) {
379 if ( a.length() != 0 ) {
380 a = a.monic();
381 if ( a.isONE() ) {
382 P.clear();
383 P.add( a );
384 return P;
385 }
386 P.add( a );
387 }
388 }
389 int l = P.size();
390 if ( l <= 1 ) return P;
391
392 int irr = 0;
393 ExpVector e;
394 ExpVector f;
395 GenPolynomial<C> a;
396 Iterator<GenPolynomial<C>> it;
397 logger.debug("irr = ");
398 while ( irr != l ) {
399 //it = P.listIterator();
400 //a = P.get(0); //it.next();
401 a = P.remove(0);
402 e = a.leadingExpVector();
403 a = normalform( P, a );
404 logger.debug(String.valueOf(irr));
405 if ( a.length() == 0 ) { l--;
406 if ( l <= 1 ) { return P; }
407 } else {
408 f = a.leadingExpVector();
409 if ( f .signum() == 0 ) {
410 P = new ArrayList<GenPolynomial<C>>();
411 P.add( a.monic() );
412 return P;
413 }
414 if ( e.equals( f ) ) {
415 irr++;
416 } else {
417 irr = 0; a = a.monic();
418 }
419 P.add( a );
420 }
421 }
422 //System.out.println();
423 return P;
424 }
425
426
427 /**
428 * Is reduction of normal form.
429 * @param row recording matrix.
430 * @param Pp a polynomial list for reduction.
431 * @param Ap a polynomial.
432 * @param Np nf(Pp,Ap), a normal form of Ap wrt. Pp.
433 * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false.
434 */
435
436 public boolean
437 isReductionNF(List<GenPolynomial<C>> row,
438 List<GenPolynomial<C>> Pp,
439 GenPolynomial<C> Ap,
440 GenPolynomial<C> Np) {
441 if ( row == null && Pp == null ) {
442 if ( Ap == null ) {
443 return Np == null;
444 }
445 return Ap.equals(Np);
446 }
447 if ( row == null && Pp != null ) {
448 return false;
449 }
450 if ( row != null && Pp == null ) {
451 return false;
452 }
453 if ( row.size() != Pp.size() ) {
454 return false;
455 }
456 GenPolynomial<C> t = Np;
457 //System.out.println("t0 = " + t );
458 GenPolynomial<C> r;
459 GenPolynomial<C> p;
460 for ( int m = 0; m < Pp.size(); m++ ) {
461 r = row.get(m);
462 p = Pp.get(m);
463 if ( r != null && p != null ) {
464 if ( t == null ) {
465 t = r.multiply(p);
466 } else {
467 t = t.sum( r.multiply(p) );
468 }
469 }
470 //System.out.println("r = " + r );
471 //System.out.println("p = " + p );
472 }
473 //System.out.println("t+ = " + t );
474 if ( t == null ) {
475 if ( Ap == null ) {
476 return true;
477 } else {
478 return Ap.isZERO();
479 }
480 } else {
481 r = t.subtract( Ap );
482 boolean z = r.isZERO();
483 if ( !z ) {
484 logger.info("t = " + t );
485 logger.info("a = " + Ap );
486 logger.info("t-a = " + r );
487 }
488 return z;
489 }
490 }
491 }