001 /*
002 * $Id: SolvableGroebnerBaseAbstract.java 3452 2010-12-27 12:48:08Z 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
011 import org.apache.log4j.Logger;
012
013 import edu.jas.poly.ExpVector;
014 import edu.jas.poly.GenPolynomial;
015 import edu.jas.poly.GenSolvablePolynomial;
016 import edu.jas.poly.GenSolvablePolynomialRing;
017 import edu.jas.poly.PolynomialList;
018
019 import edu.jas.structure.RingElem;
020
021 import edu.jas.vector.BasicLinAlg;
022
023
024 /**
025 * Solvable Groebner Bases abstract class.
026 * Implements common left, right and twosided Groebner bases
027 * and left, right and twosided GB tests.
028 * @param <C> coefficient type
029 * @author Heinz Kredel.
030 */
031
032 public abstract class SolvableGroebnerBaseAbstract<C extends RingElem<C>>
033 implements SolvableGroebnerBase<C> {
034
035 private static final Logger logger = Logger.getLogger(SolvableGroebnerBaseAbstract.class);
036 private final boolean debug = logger.isDebugEnabled();
037
038
039 /**
040 * Solvable reduction engine.
041 */
042 protected SolvableReduction<C> sred;
043
044
045 /**
046 * Reduction engine.
047 */
048 protected final Reduction<C> red;
049
050
051 /**
052 * Strategy for pair selection.
053 */
054 public final PairList<C> strategy;
055
056
057 /**
058 * Linear algebra engine.
059 */
060 protected final BasicLinAlg<GenPolynomial<C>> blas;
061
062
063 /**
064 * Constructor.
065 */
066 public SolvableGroebnerBaseAbstract() {
067 this( new SolvableReductionSeq<C>() );
068 }
069
070
071 /**
072 * Constructor.
073 * @param sred Solvable reduction engine
074 */
075 public SolvableGroebnerBaseAbstract(SolvableReduction<C> sred) {
076 this(sred,new OrderedPairlist<C>());
077 }
078
079
080 /**
081 * Constructor.
082 * @param sred Solvable reduction engine
083 * @param pl pair selection strategy
084 */
085 public SolvableGroebnerBaseAbstract(SolvableReduction<C> sred, PairList<C> pl) {
086 this.red = new ReductionSeq<C>();
087 this.sred = sred;
088 this.strategy = pl;
089 blas = new BasicLinAlg<GenPolynomial<C>>();
090 }
091
092
093 /**
094 * Left Groebner base test.
095 * @param F solvable polynomial list.
096 * @return true, if F is a left Groebner base, else false.
097 */
098 public boolean isLeftGB(List<GenSolvablePolynomial<C>> F) {
099 return isLeftGB(0,F);
100 }
101
102
103 /**
104 * Left Groebner base test.
105 * @param modv number of module variables.
106 * @param F solvable polynomial list.
107 * @return true, if F is a left Groebner base, else false.
108 */
109 public boolean isLeftGB(int modv,
110 List<GenSolvablePolynomial<C>> F) {
111 GenSolvablePolynomial<C> pi, pj, s, h;
112 for ( int i = 0; i < F.size(); i++ ) {
113 pi = F.get(i);
114 for ( int j = i+1; j < F.size(); j++ ) {
115 pj = F.get(j);
116 if ( ! red.moduleCriterion( modv, pi, pj ) ) {
117 continue;
118 }
119 // if ( ! red.criterion4( pi, pj ) ) { continue; }
120 s = sred.leftSPolynomial( pi, pj );
121 if ( s.isZERO() ) {
122 continue;
123 }
124 h = sred.leftNormalform( F, s );
125 if ( ! h.isZERO() ) {
126 return false;
127 }
128 }
129 }
130 return true;
131 }
132
133
134 /**
135 * Twosided Groebner base test.
136 * @param Fp solvable polynomial list.
137 * @return true, if Fp is a two-sided Groebner base, else false.
138 */
139 public boolean isTwosidedGB(List<GenSolvablePolynomial<C>> Fp) {
140 return isTwosidedGB(0,Fp);
141 }
142
143
144 /**
145 * Twosided Groebner base test.
146 * @param modv number of module variables.
147 * @param Fp solvable polynomial list.
148 * @return true, if Fp is a two-sided Groebner base, else false.
149 */
150 public boolean isTwosidedGB(int modv,
151 List<GenSolvablePolynomial<C>> Fp) {
152 if ( Fp == null || Fp.size() == 0 ) { // 0 not 1
153 return true;
154 }
155 GenSolvablePolynomialRing<C> fac = Fp.get(0).ring; // assert != null
156 //List<GenSolvablePolynomial<C>> X = generateUnivar( modv, Fp );
157 List<GenSolvablePolynomial<C>> X = fac.univariateList( modv );
158 List<GenSolvablePolynomial<C>> F
159 = new ArrayList<GenSolvablePolynomial<C>>( Fp.size() * (1+X.size()) );
160 F.addAll( Fp );
161 GenSolvablePolynomial<C> p, x, pi, pj, s, h;
162 for ( int i = 0; i < Fp.size(); i++ ) {
163 p = Fp.get(i);
164 for ( int j = 0; j < X.size(); j++ ) {
165 x = X.get(j);
166 p = p.multiply( x );
167 F.add( p );
168 }
169 }
170 //System.out.println("F to check = " + F);
171 for ( int i = 0; i < F.size(); i++ ) {
172 pi = F.get(i);
173 for ( int j = i+1; j < F.size(); j++ ) {
174 pj = F.get(j);
175 if ( ! red.moduleCriterion( modv, pi, pj ) ) {
176 continue;
177 }
178 // if ( ! red.criterion4( pi, pj ) ) { continue; }
179 s = sred.leftSPolynomial( pi, pj );
180 if ( s.isZERO() ) {
181 continue;
182 }
183 h = sred.leftNormalform( F, s );
184 if ( ! h.isZERO() ) {
185 logger.info("is not TwosidedGB: " + h);
186 return false;
187 }
188 }
189 }
190 return true;
191 }
192
193
194 /**
195 * Right Groebner base test.
196 * @param F solvable polynomial list.
197 * @return true, if F is a right Groebner base, else false.
198 */
199 public boolean isRightGB(List<GenSolvablePolynomial<C>> F) {
200 return isRightGB(0,F);
201 }
202
203
204 /**
205 * Right Groebner base test.
206 * @param modv number of module variables.
207 * @param F solvable polynomial list.
208 * @return true, if F is a right Groebner base, else false.
209 */
210 public boolean isRightGB(int modv, List<GenSolvablePolynomial<C>> F) {
211 GenSolvablePolynomial<C> pi, pj, s, h;
212 for ( int i = 0; i < F.size(); i++ ) {
213 pi = F.get(i);
214 //System.out.println("pi right = " + pi);
215 for ( int j = i+1; j < F.size(); j++ ) {
216 pj = F.get(j);
217 //System.out.println("pj right = " + pj);
218 if ( ! red.moduleCriterion( modv, pi, pj ) ) {
219 continue;
220 }
221 // if ( ! red.criterion4( pi, pj ) ) { continue; }
222 s = sred.rightSPolynomial( pi, pj );
223 if ( s.isZERO() ) {
224 continue;
225 }
226 //System.out.println("s right = " + s);
227 h = sred.rightNormalform( F, s );
228 if ( ! h.isZERO() ) {
229 logger.info("isRightGB non zero h = " + h);
230 return false;
231 } else {
232 //logger.info("isRightGB zero h = " + h);
233 }
234 }
235 }
236 return true;
237 }
238
239
240 /**
241 * Left Groebner base using pairlist class.
242 * @param F solvable polynomial list.
243 * @return leftGB(F) a left Groebner base of F.
244 */
245 public List<GenSolvablePolynomial<C>>
246 leftGB(List<GenSolvablePolynomial<C>> F) {
247 return leftGB(0,F);
248 }
249
250
251 /**
252 * Solvable Extended Groebner base using critical pair class.
253 * @param F solvable polynomial list.
254 * @return a container for an extended left Groebner base of F.
255 */
256 public SolvableExtendedGB<C>
257 extLeftGB( List<GenSolvablePolynomial<C>> F ) {
258 return extLeftGB(0,F);
259 }
260
261
262 /**
263 * Left minimal ordered groebner basis.
264 * @param Gp a left Groebner base.
265 * @return leftGBmi(F) a minimal left Groebner base of Gp.
266 */
267 public List<GenSolvablePolynomial<C>>
268 leftMinimalGB(List<GenSolvablePolynomial<C>> Gp) {
269 ArrayList<GenSolvablePolynomial<C>> G
270 = new ArrayList<GenSolvablePolynomial<C>>();
271 ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator();
272 for ( GenSolvablePolynomial<C> a: Gp ) {
273 // a = (SolvablePolynomial) it.next();
274 if ( a.length() != 0 ) { // always true
275 // already monic a = a.monic();
276 G.add( a );
277 }
278 }
279 if ( G.size() <= 1 ) {
280 return G;
281 }
282
283 ExpVector e;
284 ExpVector f;
285 GenSolvablePolynomial<C> a, p;
286 ArrayList<GenSolvablePolynomial<C>> F
287 = new ArrayList<GenSolvablePolynomial<C>>();
288 boolean mt;
289
290 while ( G.size() > 0 ) {
291 a = G.remove(0);
292 e = a.leadingExpVector();
293
294 it = G.listIterator();
295 mt = false;
296 while ( it.hasNext() && ! mt ) {
297 p = it.next();
298 f = p.leadingExpVector();
299 mt = e.multipleOf( f );
300 }
301 it = F.listIterator();
302 while ( it.hasNext() && ! mt ) {
303 p = it.next();
304 f = p.leadingExpVector();
305 mt = e.multipleOf( f );
306 }
307 if ( ! mt ) {
308 F.add( a );
309 } else {
310 // System.out.println("dropped " + a.length());
311 }
312 }
313 G = F;
314 if ( G.size() <= 1 ) {
315 return G;
316 }
317
318 F = new ArrayList<GenSolvablePolynomial<C>>();
319 while ( G.size() > 0 ) {
320 a = G.remove(0);
321 // System.out.println("doing " + a.length());
322 a = sred.leftNormalform( G, a );
323 a = sred.leftNormalform( F, a );
324 F.add( a );
325 }
326 return F;
327 }
328
329
330 /**
331 * Twosided Groebner base using pairlist class.
332 * @param Fp solvable polynomial list.
333 * @return tsGB(Fp) a twosided Groebner base of Fp.
334 */
335 public List<GenSolvablePolynomial<C>>
336 twosidedGB(List<GenSolvablePolynomial<C>> Fp) {
337 return twosidedGB(0,Fp);
338 }
339
340
341 /**
342 * Right Groebner base using opposite ring left GB.
343 * @param F solvable polynomial list.
344 * @return rightGB(F) a right Groebner base of F.
345 */
346 public List<GenSolvablePolynomial<C>>
347 rightGB(List<GenSolvablePolynomial<C>> F) {
348 return rightGB(0,F);
349 }
350
351
352 /**
353 * Right Groebner base using opposite ring left GB.
354 * @param modv number of module variables.
355 * @param F solvable polynomial list.
356 * @return rightGB(F) a right Groebner base of F.
357 */
358 public List<GenSolvablePolynomial<C>>
359 rightGB(int modv,
360 List<GenSolvablePolynomial<C>> F) {
361 GenSolvablePolynomialRing<C> ring = null;
362 for ( GenSolvablePolynomial<C> p : F ) {
363 if ( p != null ) {
364 ring = p.ring;
365 break;
366 }
367 }
368 if ( ring == null ) {
369 return F;
370 }
371 GenSolvablePolynomialRing<C> rring = ring.reverse(true); //true
372 //ring = rring.reverse(true); // true
373 GenSolvablePolynomial<C> q;
374 List<GenSolvablePolynomial<C>> rF;
375 rF = new ArrayList<GenSolvablePolynomial<C>>( F.size() );
376 for ( GenSolvablePolynomial<C> p : F ) {
377 if ( p != null ) {
378 q = (GenSolvablePolynomial<C>)p.reverse(rring);
379 rF.add( q );
380 }
381 }
382 if ( true || debug ) {
383 PolynomialList<C> pl = new PolynomialList<C>(rring,rF);
384 logger.info("reversed problem = " + pl);
385 }
386 List<GenSolvablePolynomial<C>> rG = leftGB( modv, rF );
387 if ( true || debug ) {
388 //PolynomialList<C> pl = new PolynomialList<C>(rring,rG);
389 //logger.info("reversed GB = " + pl);
390 long t = System.currentTimeMillis();
391 boolean isit = isLeftGB( rG );
392 t = System.currentTimeMillis() - t;
393 logger.info("is left GB = " + isit + ", in " + t + " milliseconds");
394 }
395 ring = rring.reverse(true); // true
396 List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(rG.size());
397 for ( GenSolvablePolynomial<C> p : rG ) {
398 if ( p != null ) {
399 q = (GenSolvablePolynomial<C>)p.reverse(ring);
400 G.add( q );
401 }
402 }
403 if ( true || debug ) {
404 //PolynomialList<C> pl = new PolynomialList<C>(ring,G);
405 //logger.info("GB = " + pl);
406 long t = System.currentTimeMillis();
407 boolean isit = isRightGB( G );
408 t = System.currentTimeMillis() - t;
409 logger.info("is right GB = " + isit + ", in " + t + " milliseconds");
410 }
411 return G;
412 }
413
414
415 /**
416 * Test if left reduction matrix.
417 * @param exgb an SolvableExtendedGB container.
418 * @return true, if exgb contains a left reduction matrix, else false.
419 */
420 public boolean
421 isLeftReductionMatrix(SolvableExtendedGB<C> exgb) {
422 if ( exgb == null ) {
423 return true;
424 }
425 return isLeftReductionMatrix(exgb.F,exgb.G,exgb.F2G,exgb.G2F);
426 }
427
428
429 /**
430 * Test if left reduction matrix.
431 * @param F a solvable polynomial list.
432 * @param G a left Groebner base.
433 * @param Mf a possible left reduction matrix.
434 * @param Mg a possible left reduction matrix.
435 * @return true, if Mg and Mf are left reduction matrices, else false.
436 */
437 public boolean
438 isLeftReductionMatrix(List<GenSolvablePolynomial<C>> F,
439 List<GenSolvablePolynomial<C>> G,
440 List<List<GenSolvablePolynomial<C>>> Mf,
441 List<List<GenSolvablePolynomial<C>>> Mg) {
442 // no more check G and Mg: G * Mg[i] == 0
443 // check F and Mg: F * Mg[i] == G[i]
444 int k = 0;
445 for ( List<GenSolvablePolynomial<C>> row : Mg ) {
446 boolean t = sred.isLeftReductionNF( row, F, G.get( k ), null );
447 if ( ! t ) {
448 System.out.println("row = " + row);
449 System.out.println("F = " + F);
450 System.out.println("Gk = " + G.get(k));
451 logger.info("F isLeftReductionMatrix s, k = " + F.size() + ", " + k);
452 return false;
453 }
454 k++;
455 }
456 // check G and Mf: G * Mf[i] == F[i]
457 k = 0;
458 for ( List<GenSolvablePolynomial<C>> row : Mf ) {
459 boolean t = sred.isLeftReductionNF( row, G, F.get( k ), null );
460 if ( ! t ) {
461 logger.error("G isLeftReductionMatrix s, k = " + G.size() + ", " + k);
462 return false;
463 }
464 k++;
465 }
466 return true;
467 }
468
469 }