001 /*
002 * $Id: GroebnerBaseAbstract.java 3627 2011-05-08 11:12:04Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.ArrayList;
008 import java.util.List;
009 import java.util.ListIterator;
010 import java.util.Set;
011 import java.util.HashSet;
012 import java.util.Collections;
013
014 import org.apache.log4j.Logger;
015
016 import edu.jas.poly.GenPolynomial;
017 import edu.jas.poly.GenPolynomialRing;
018 import edu.jas.structure.RingElem;
019 import edu.jas.poly.ExpVector;
020 import edu.jas.vector.BasicLinAlg;
021
022
023 /**
024 * Groebner Bases abstract class.
025 * Implements common Groebner bases and GB test methods.
026 * @param <C> coefficient type
027 * @author Heinz Kredel
028 */
029
030 public abstract class GroebnerBaseAbstract<C extends RingElem<C>>
031 implements GroebnerBase<C> {
032
033 private static final Logger logger = Logger.getLogger(GroebnerBaseAbstract.class);
034 private final boolean debug = logger.isDebugEnabled();
035
036
037 /**
038 * Reduction engine.
039 */
040 public final Reduction<C> red;
041
042
043 /**
044 * Strategy for pair selection.
045 */
046 public final PairList<C> strategy;
047
048
049 /**
050 * linear algebra engine.
051 */
052 public final BasicLinAlg<GenPolynomial<C>> blas;
053
054
055 /**
056 * Constructor.
057 */
058 public GroebnerBaseAbstract() {
059 this( new ReductionSeq<C>() );
060 }
061
062
063 /**
064 * Constructor.
065 * @param red Reduction engine
066 */
067 public GroebnerBaseAbstract(Reduction<C> red) {
068 this(red, new OrderedPairlist<C>() );
069 }
070
071
072 /**
073 * Constructor.
074 * @param red Reduction engine
075 * @param pl pair selection strategy
076 */
077 public GroebnerBaseAbstract(Reduction<C> red, PairList<C> pl) {
078 this.red = red;
079 this.strategy = pl;
080 blas = new BasicLinAlg<GenPolynomial<C>>();
081 }
082
083
084 /**
085 * Groebner base test.
086 * @param F polynomial list.
087 * @return true, if F is a Groebner base, else false.
088 */
089 public boolean isGB(List<GenPolynomial<C>> F) {
090 return isGB(0,F);
091 }
092
093
094 /**
095 * Groebner base test.
096 * @param modv module variable number.
097 * @param F polynomial list.
098 * @return true, if F is a Groebner base, else false.
099 */
100 public boolean isGB(int modv, List<GenPolynomial<C>> F) {
101 if ( F == null ) {
102 return true;
103 }
104 GenPolynomial<C> pi, pj, s, h;
105 for ( int i = 0; i < F.size(); i++ ) {
106 pi = F.get(i);
107 for ( int j = i+1; j < F.size(); j++ ) {
108 pj = F.get(j);
109 if ( ! red.moduleCriterion( modv, pi, pj ) ) {
110 continue;
111 }
112 if ( ! red.criterion4( pi, pj ) ) {
113 continue;
114 }
115 s = red.SPolynomial( pi, pj );
116 if ( s.isZERO() ) {
117 continue;
118 }
119 h = red.normalform( F, s );
120 if ( ! h.isZERO() ) {
121 System.out.println("pi = " + pi + ", pj = " + pj);
122 System.out.println("s = " + s + ", h = " + h);
123 return false;
124 }
125 }
126 }
127 return true;
128 }
129
130
131 /**
132 * Common zero test.
133 * @param F polynomial list.
134 * @return -1, 0 or 1 if dimension(ideal(F)) &eq; -1, 0 or ≥ 1.
135 */
136 public int commonZeroTest(List<GenPolynomial<C>> F) {
137 if (F == null || F.isEmpty()) {
138 return 1;
139 }
140 GenPolynomialRing<C> pfac = F.get(0).ring;
141 if (pfac.nvar <= 0) {
142 return -1;
143 }
144 //int uht = 0;
145 Set<Integer> v = new HashSet<Integer>(); // for non reduced GBs
146 for (GenPolynomial<C> p : F) {
147 if ( p.isZERO() ) {
148 continue;
149 }
150 if ( p.isConstant() ) { // for non-monic lists
151 return -1;
152 }
153 ExpVector e = p.leadingExpVector();
154 if (e == null) {
155 continue;
156 }
157 int[] u = e.dependencyOnVariables();
158 if (u == null) {
159 continue;
160 }
161 if (u.length == 1) {
162 //uht++;
163 v.add(u[0]);
164 }
165 }
166 if (pfac.nvar == v.size()) {
167 return 0;
168 }
169 return 1;
170 }
171
172
173 /**
174 * Groebner base using pairlist class.
175 * @param F polynomial list.
176 * @return GB(F) a Groebner base of F.
177 */
178 public List<GenPolynomial<C>>
179 GB( List<GenPolynomial<C>> F ) {
180 return GB(0,F);
181 }
182
183
184 /**
185 * Extended Groebner base using critical pair class.
186 * @param F polynomial list.
187 * @return a container for a Groebner base G of F together with back-and-forth transformations.
188 */
189 public ExtendedGB<C>
190 extGB( List<GenPolynomial<C>> F ) {
191 return extGB(0,F);
192 }
193
194
195 /**
196 * Extended Groebner base using critical pair class.
197 * @param modv module variable number.
198 * @param F polynomial list.
199 * @return a container for a Groebner base G of F together with back-and-forth transformations.
200 */
201 public ExtendedGB<C>
202 extGB( int modv,
203 List<GenPolynomial<C>> F ) {
204 throw new UnsupportedOperationException("extGB not implemented in "
205 + this.getClass().getSimpleName());
206 }
207
208
209 /**
210 * Minimal ordered Groebner basis.
211 * @param Gp a Groebner base.
212 * @return a reduced Groebner base of Gp.
213 */
214 public List<GenPolynomial<C>>
215 minimalGB(List<GenPolynomial<C>> Gp) {
216 if ( Gp == null || Gp.size() <= 1 ) {
217 return Gp;
218 }
219 // remove zero polynomials
220 List<GenPolynomial<C>> G
221 = new ArrayList<GenPolynomial<C>>( Gp.size() );
222 for ( GenPolynomial<C> a : Gp ) {
223 if ( a != null && !a.isZERO() ) { // always true in GB()
224 // already positive a = a.abs();
225 G.add( a );
226 }
227 }
228 if ( G.size() <= 1 ) {
229 return G;
230 }
231 // remove top reducible polynomials
232 GenPolynomial<C> a;
233 List<GenPolynomial<C>> F;
234 F = new ArrayList<GenPolynomial<C>>( G.size() );
235 while ( G.size() > 0 ) {
236 a = G.remove(0);
237 if ( red.isTopReducible(G,a) || red.isTopReducible(F,a) ) {
238 // drop polynomial
239 if ( debug ) {
240 System.out.println("dropped " + a);
241 List<GenPolynomial<C>> ff;
242 ff = new ArrayList<GenPolynomial<C>>( G );
243 ff.addAll(F);
244 a = red.normalform( ff, a );
245 if ( !a.isZERO() ) {
246 System.out.println("error, nf(a) " + a);
247 }
248 }
249 } else {
250 F.add(a);
251 }
252 }
253 G = F;
254 if ( G.size() <= 1 ) {
255 return G;
256 }
257 // reduce remaining polynomials
258 Collections.reverse(G); // important for lex GB
259 int len = G.size();
260 if ( debug ) {
261 System.out.println("#G " + len);
262 for (GenPolynomial<C> aa : G) {
263 System.out.println("aa = " + aa.length() + ", lt = " + aa.getMap().keySet());
264 }
265 }
266 int i = 0;
267 while ( i < len ) {
268 a = G.remove(0);
269 if ( debug ) {
270 System.out.println("doing " + a.length() + ", lt = " + a.leadingExpVector());
271 }
272 a = red.normalform( G, a );
273 G.add( a ); // adds as last
274 i++;
275 }
276 return G;
277 }
278
279
280 /**
281 * Test if reduction matrix.
282 * @param exgb an ExtendedGB container.
283 * @return true, if exgb contains a reduction matrix, else false.
284 */
285 public boolean
286 isReductionMatrix(ExtendedGB<C> exgb) {
287 if ( exgb == null ) {
288 return true;
289 }
290 return isReductionMatrix(exgb.F,exgb.G,exgb.F2G,exgb.G2F);
291 }
292
293
294 /**
295 * Test if reduction matrix.
296 * @param F a polynomial list.
297 * @param G a Groebner base.
298 * @param Mf a possible reduction matrix.
299 * @param Mg a possible reduction matrix.
300 * @return true, if Mg and Mf are reduction matrices, else false.
301 */
302 public boolean
303 isReductionMatrix(List<GenPolynomial<C>> F,
304 List<GenPolynomial<C>> G,
305 List<List<GenPolynomial<C>>> Mf,
306 List<List<GenPolynomial<C>>> Mg) {
307 // no more check G and Mg: G * Mg[i] == 0
308 // check F and Mg: F * Mg[i] == G[i]
309 int k = 0;
310 for ( List<GenPolynomial<C>> row : Mg ) {
311 boolean t = red.isReductionNF( row, F, G.get( k ), null );
312 if ( ! t ) {
313 logger.error("F isReductionMatrix s, k = " + F.size() + ", " + k);
314 return false;
315 }
316 k++;
317 }
318 // check G and Mf: G * Mf[i] == F[i]
319 k = 0;
320 for ( List<GenPolynomial<C>> row : Mf ) {
321 boolean t = red.isReductionNF( row, G, F.get( k ), null );
322 if ( ! t ) {
323 logger.error("G isReductionMatrix s, k = " + G.size() + ", " + k);
324 return false;
325 }
326 k++;
327 }
328 return true;
329 }
330
331
332 /**
333 * Normalize M.
334 * Make all rows the same size and make certain column elements zero.
335 * @param M a reduction matrix.
336 * @return normalized M.
337 */
338 public List<List<GenPolynomial<C>>>
339 normalizeMatrix(int flen, List<List<GenPolynomial<C>>> M) {
340 if ( M == null ) {
341 return M;
342 }
343 if ( M.size() == 0 ) {
344 return M;
345 }
346 List<List<GenPolynomial<C>>> N = new ArrayList<List<GenPolynomial<C>>>();
347 List<List<GenPolynomial<C>>> K = new ArrayList<List<GenPolynomial<C>>>();
348 int len = M.get( M.size()-1 ).size(); // longest row
349 // pad / extend rows
350 for ( List<GenPolynomial<C>> row : M ) {
351 List<GenPolynomial<C>> nrow = new ArrayList<GenPolynomial<C>>( row );
352 for ( int i = row.size(); i < len; i++ ) {
353 nrow.add( null );
354 }
355 N.add( nrow );
356 }
357 // System.out.println("norm N fill = " + N);
358 // make zero columns
359 int k = flen;
360 for ( int i = 0; i < N.size(); i++ ) { // 0
361 List<GenPolynomial<C>> row = N.get( i );
362 if ( debug ) {
363 logger.info("row = " + row);
364 }
365 K.add( row );
366 if ( i < flen ) { // skip identity part
367 continue;
368 }
369 List<GenPolynomial<C>> xrow;
370 GenPolynomial<C> a;
371 //System.out.println("norm i = " + i);
372 for ( int j = i+1; j < N.size(); j++ ) {
373 List<GenPolynomial<C>> nrow = N.get( j );
374 //System.out.println("nrow j = " +j + ", " + nrow);
375 if ( k < nrow.size() ) { // always true
376 a = nrow.get( k );
377 //System.out.println("k, a = " + k + ", " + a);
378 if ( a != null && !a.isZERO() ) {
379 xrow = blas.scalarProduct( a, row);
380 xrow = blas.vectorAdd(xrow,nrow);
381 //System.out.println("xrow = " + xrow);
382 N.set( j, xrow );
383 }
384 }
385 }
386 k++;
387 }
388 //System.out.println("norm K reduc = " + K);
389 // truncate
390 N.clear();
391 for ( List<GenPolynomial<C>> row: K ) {
392 List<GenPolynomial<C>> tr = new ArrayList<GenPolynomial<C>>();
393 for ( int i = 0; i < flen; i++ ) {
394 tr.add( row.get(i) );
395 }
396 N.add( tr );
397 }
398 K = N;
399 //System.out.println("norm K trunc = " + K);
400 return K;
401 }
402
403
404 /**
405 * Minimal extended groebner basis.
406 * @param Gp a Groebner base.
407 * @param M a reduction matrix, is modified.
408 * @return a (partially) reduced Groebner base of Gp in a container.
409 */
410 public ExtendedGB<C>
411 minimalExtendedGB(int flen,
412 List<GenPolynomial<C>> Gp,
413 List<List<GenPolynomial<C>>> M) {
414 if ( Gp == null ) {
415 return null; //new ExtendedGB<C>(null,Gp,null,M);
416 }
417 if ( Gp.size() <= 1 ) {
418 return new ExtendedGB<C>(null,Gp,null,M);
419 }
420 List<GenPolynomial<C>> G;
421 List<GenPolynomial<C>> F;
422 G = new ArrayList<GenPolynomial<C>>( Gp );
423 F = new ArrayList<GenPolynomial<C>>( Gp.size() );
424
425 List<List<GenPolynomial<C>>> Mg;
426 List<List<GenPolynomial<C>>> Mf;
427 Mg = new ArrayList<List<GenPolynomial<C>>>( M.size() );
428 Mf = new ArrayList<List<GenPolynomial<C>>>( M.size() );
429 List<GenPolynomial<C>> row;
430 for ( List<GenPolynomial<C>> r : M ) {
431 // must be copied also
432 row = new ArrayList<GenPolynomial<C>>( r );
433 Mg.add( row );
434 }
435 row = null;
436
437 GenPolynomial<C> a;
438 ExpVector e;
439 ExpVector f;
440 GenPolynomial<C> p;
441 boolean mt;
442 ListIterator<GenPolynomial<C>> it;
443 ArrayList<Integer> ix = new ArrayList<Integer>();
444 ArrayList<Integer> jx = new ArrayList<Integer>();
445 int k = 0;
446 //System.out.println("flen, Gp, M = " + flen + ", " + Gp.size() + ", " + M.size() );
447 while ( G.size() > 0 ) {
448 a = G.remove(0);
449 e = a.leadingExpVector();
450
451 it = G.listIterator();
452 mt = false;
453 while ( it.hasNext() && ! mt ) {
454 p = it.next();
455 f = p.leadingExpVector();
456 mt = e.multipleOf( f );
457 }
458 it = F.listIterator();
459 while ( it.hasNext() && ! mt ) {
460 p = it.next();
461 f = p.leadingExpVector();
462 mt = e.multipleOf( f );
463 }
464 //System.out.println("k, mt = " + k + ", " + mt);
465 if ( ! mt ) {
466 F.add( a );
467 ix.add( k );
468 } else { // drop polynomial and corresponding row and column
469 // F.add( a.ring.getZERO() );
470 jx.add( k );
471 }
472 k++;
473 }
474 if ( debug ) {
475 logger.debug("ix, #M, jx = " + ix + ", " + Mg.size() + ", " + jx);
476 }
477 int fix = -1; // copied polys
478 // copy Mg to Mf as indicated by ix
479 for ( int i = 0; i < ix.size(); i++ ) {
480 int u = ix.get(i);
481 if ( u >= flen && fix == -1 ) {
482 fix = Mf.size();
483 }
484 //System.out.println("copy u, fix = " + u + ", " + fix);
485 if ( u >= 0 ) {
486 row = Mg.get( u );
487 Mf.add( row );
488 }
489 }
490 if ( F.size() <= 1 || fix == -1 ) {
491 return new ExtendedGB<C>(null,F,null,Mf);
492 }
493 // must return, since extended normalform has not correct order of polys
494 /*
495 G = F;
496 F = new ArrayList<GenPolynomial<C>>( G.size() );
497 List<GenPolynomial<C>> temp;
498 k = 0;
499 final int len = G.size();
500 while ( G.size() > 0 ) {
501 a = G.remove(0);
502 if ( k >= fix ) { // dont touch copied polys
503 row = Mf.get( k );
504 //System.out.println("doing k = " + k + ", " + a);
505 // must keep order, but removed polys missing
506 temp = new ArrayList<GenPolynomial<C>>( len );
507 temp.addAll( F );
508 temp.add( a.ring.getZERO() ); // ??
509 temp.addAll( G );
510 //System.out.println("row before = " + row);
511 a = red.normalform( row, temp, a );
512 //System.out.println("row after = " + row);
513 }
514 F.add( a );
515 k++;
516 }
517 // does Mf need renormalization?
518 */
519 return new ExtendedGB<C>(null,F,null,Mf);
520 }
521
522
523 /**
524 * Cleanup and terminate ThreadPool.
525 */
526 public void terminate() {
527 logger.info("terminate not implemented");
528 }
529
530
531 /**
532 * Cancel ThreadPool.
533 */
534 public int cancel() {
535 logger.info("cancel not implemented");
536 return 0;
537 }
538
539 }