001 /*
002 * $Id: GroebnerBaseSeq.java 3420 2010-12-19 21:34:25Z 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.structure.RingElem;
014
015 //import edu.jas.poly.ExpVector;
016 import edu.jas.gb.OrderedPairlist;
017 import edu.jas.poly.GenPolynomial;
018 import edu.jas.poly.GenPolynomialRing;
019
020
021 /**
022 * Groebner Base sequential algorithm.
023 * Implements Groebner bases and GB test.
024 * @param <C> coefficient type
025 * @author Heinz Kredel
026 */
027
028 public class GroebnerBaseSeq<C extends RingElem<C>>
029 extends GroebnerBaseAbstract<C> {
030
031 private static final Logger logger = Logger.getLogger(GroebnerBaseSeq.class);
032 private final boolean debug = logger.isDebugEnabled();
033
034
035 /**
036 * Constructor.
037 */
038 public GroebnerBaseSeq() {
039 super();
040 }
041
042
043 /**
044 * Constructor.
045 * @param red Reduction engine
046 */
047 public GroebnerBaseSeq(Reduction<C> red) {
048 super(red);
049 }
050
051
052 /**
053 * Constructor.
054 * @param red Reduction engine
055 * @param pl pair selection strategy
056 */
057 public GroebnerBaseSeq(Reduction<C> red, PairList<C> pl) {
058 super(red,pl);
059 }
060
061
062 /**
063 * Groebner base using pairlist class.
064 * @param modv module variable number.
065 * @param F polynomial list.
066 * @return GB(F) a Groebner base of F.
067 */
068 public List<GenPolynomial<C>>
069 GB( int modv,
070 List<GenPolynomial<C>> F ) {
071 GenPolynomial<C> p;
072 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
073 PairList<C> pairlist = null;
074 int l = F.size();
075 ListIterator<GenPolynomial<C>> it = F.listIterator();
076 while ( it.hasNext() ) {
077 p = it.next();
078 if ( p.length() > 0 ) {
079 p = p.monic();
080 if ( p.isONE() ) {
081 G.clear(); G.add( p );
082 return G; // since no threads are activated
083 }
084 G.add( p );
085 if ( pairlist == null ) {
086 //pairlist = new OrderedPairlist<C>( modv, p.ring );
087 pairlist = strategy.create( modv, p.ring );
088 if ( ! p.ring.coFac.isField() ) {
089 throw new IllegalArgumentException("coefficients not from a field");
090 }
091 }
092 // putOne not required
093 pairlist.put( p );
094 } else {
095 l--;
096 }
097 }
098 if ( l <= 1 ) {
099 return G; // since no threads are activated
100 }
101 logger.info("start " + pairlist);
102
103 Pair<C> pair;
104 GenPolynomial<C> pi;
105 GenPolynomial<C> pj;
106 GenPolynomial<C> S;
107 GenPolynomial<C> H;
108 while ( pairlist.hasNext() ) {
109 pair = pairlist.removeNext();
110 //logger.debug("pair = " + pair);
111 if ( pair == null ) {
112 continue;
113 }
114 pi = pair.pi;
115 pj = pair.pj;
116 if ( /*false &&*/ debug ) {
117 logger.debug("pi = " + pi );
118 logger.debug("pj = " + pj );
119 }
120
121 S = red.SPolynomial( pi, pj );
122 if ( S.isZERO() ) {
123 pair.setZero();
124 continue;
125 }
126 if ( debug ) {
127 logger.debug("ht(S) = " + S.leadingExpVector() );
128 }
129
130 H = red.normalform( G, S );
131 if ( debug ) {
132 //logger.info("pair = " + pair);
133 //logger.info("ht(S) = " + S.monic()); //.leadingExpVector() );
134 logger.info("ht(H) = " + H.monic()); //.leadingExpVector() );
135 }
136 if ( H.isZERO() ) {
137 pair.setZero();
138 continue;
139 }
140 H = H.monic();
141 if ( debug ) {
142 logger.info("ht(H) = " + H.leadingExpVector() );
143 }
144
145 H = H.monic();
146 if ( H.isONE() ) {
147 G.clear(); G.add( H );
148 return G; // since no threads are activated
149 }
150 if ( debug ) {
151 logger.info("H = " + H );
152 }
153 if ( H.length() > 0 ) {
154 l++;
155 G.add( H );
156 pairlist.put( H );
157 }
158 }
159 logger.debug("#sequential list = "+G.size());
160 G = minimalGB(G);
161 logger.info("" + pairlist);
162 return G;
163 }
164
165
166 /**
167 * Extended Groebner base using critical pair class.
168 * @param modv module variable number.
169 * @param F polynomial list.
170 * @return a container for an extended Groebner base of F.
171 */
172 @Override
173 public ExtendedGB<C>
174 extGB( int modv,
175 List<GenPolynomial<C>> F ) {
176 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
177 List<List<GenPolynomial<C>>> F2G = new ArrayList<List<GenPolynomial<C>>>();
178 List<List<GenPolynomial<C>>> G2F = new ArrayList<List<GenPolynomial<C>>>();
179 PairList<C> pairlist = null;
180 boolean oneInGB = false;
181 int len = F.size();
182
183 List<GenPolynomial<C>> row = null;
184 List<GenPolynomial<C>> rows = null;
185 List<GenPolynomial<C>> rowh = null;
186 GenPolynomialRing<C> ring = null;
187 GenPolynomial<C> H;
188 GenPolynomial<C> p;
189
190 int nzlen = 0;
191 for ( GenPolynomial<C> f : F ) {
192 if ( f.length() > 0 ) {
193 nzlen++;
194 }
195 if ( ring == null ) {
196 ring = f.ring;
197 }
198 }
199 GenPolynomial<C> mone = ring.getONE(); //.negate();
200 int k = 0;
201 ListIterator<GenPolynomial<C>> it = F.listIterator();
202 while ( it.hasNext() ) {
203 p = it.next();
204 if ( p.length() > 0 ) {
205 row = new ArrayList<GenPolynomial<C>>( nzlen );
206 for ( int j = 0; j < nzlen; j++ ) {
207 row.add(null);
208 }
209 //C c = p.leadingBaseCoefficient();
210 //c = c.inverse();
211 //p = p.multiply( c );
212 row.set( k, mone ); //.multiply(c) );
213 k++;
214 if ( p.isUnit() ) {
215 G.clear(); G.add( p );
216 G2F.clear(); G2F.add( row );
217 oneInGB = true;
218 break;
219 }
220 G.add( p );
221 G2F.add( row );
222 if ( pairlist == null ) {
223 //pairlist = new OrderedPairlist<C>( modv, p.ring );
224 pairlist = strategy.create( modv, p.ring );
225 if ( ! p.ring.coFac.isField() ) {
226 throw new RuntimeException("coefficients not from a field");
227 }
228 }
229 // putOne not required
230 pairlist.put( p );
231 } else {
232 len--;
233 }
234 }
235 ExtendedGB<C> exgb;
236 if ( len <= 1 || oneInGB ) {
237 // adjust F2G
238 for ( GenPolynomial<C> f : F ) {
239 row = new ArrayList<GenPolynomial<C>>( G.size() );
240 for ( int j = 0; j < G.size(); j++ ) {
241 row.add(null);
242 }
243 H = red.normalform( row, G, f );
244 if ( ! H.isZERO() ) {
245 logger.error("nonzero H = " + H );
246 }
247 F2G.add( row );
248 }
249 exgb = new ExtendedGB<C>(F,G,F2G,G2F);
250 //System.out.println("exgb 1 = " + exgb);
251 return exgb;
252 }
253
254 Pair<C> pair;
255 int i, j;
256 GenPolynomial<C> pi;
257 GenPolynomial<C> pj;
258 GenPolynomial<C> S;
259 GenPolynomial<C> x;
260 GenPolynomial<C> y;
261 //GenPolynomial<C> z;
262 while ( pairlist.hasNext() && ! oneInGB ) {
263 pair = pairlist.removeNext();
264 if ( pair == null ) {
265 continue;
266 }
267 i = pair.i;
268 j = pair.j;
269 pi = pair.pi;
270 pj = pair.pj;
271 if ( debug ) {
272 logger.info("i, pi = " + i + ", " + pi );
273 logger.info("j, pj = " + j + ", " + pj );
274 }
275
276 rows = new ArrayList<GenPolynomial<C>>( G.size() );
277 for ( int m = 0; m < G.size(); m++ ) {
278 rows.add(null);
279 }
280 S = red.SPolynomial( rows, i, pi, j, pj );
281 if ( debug ) {
282 logger.debug("is reduction S = "
283 + red.isReductionNF( rows, G, ring.getZERO(), S ) );
284 }
285 if ( S.isZERO() ) {
286 // do not add to G2F
287 continue;
288 }
289 if ( debug ) {
290 logger.debug("ht(S) = " + S.leadingExpVector() );
291 }
292
293 rowh = new ArrayList<GenPolynomial<C>>( G.size() );
294 for ( int m = 0; m < G.size(); m++ ) {
295 rowh.add(null);
296 }
297 H = red.normalform( rowh, G, S );
298 if ( debug ) {
299 logger.debug("is reduction H = "
300 + red.isReductionNF( rowh, G, S, H ) );
301 }
302 if ( H.isZERO() ) {
303 // do not add to G2F
304 continue;
305 }
306 if ( debug ) {
307 logger.debug("ht(H) = " + H.leadingExpVector() );
308 }
309
310 row = new ArrayList<GenPolynomial<C>>( G.size()+1 );
311 for ( int m = 0; m < G.size(); m++ ) {
312 x = rows.get(m);
313 if ( x != null ) {
314 //System.out.println("ms = " + m + " " + x);
315 x = x.negate();
316 }
317 y = rowh.get(m);
318 if ( y != null ) {
319 y = y.negate();
320 //System.out.println("mh = " + m + " " + y);
321 }
322 if ( x == null ) {
323 x = y;
324 } else {
325 x = x.sum( y );
326 }
327 //System.out.println("mx = " + m + " " + x);
328 row.add( x );
329 }
330 if ( debug ) {
331 logger.debug("is reduction 0+sum(row,G) == H : "
332 + red.isReductionNF( row, G, H, ring.getZERO() ) );
333 }
334 row.add( null );
335
336
337 // H = H.monic();
338 C c = H.leadingBaseCoefficient();
339 c = c.inverse();
340 H = H.multiply( c );
341 row = blas.scalarProduct( mone.multiply(c), row );
342 row.set( G.size(), mone );
343 if ( H.isONE() ) {
344 // G.clear();
345 G.add( H );
346 G2F.add( row );
347 oneInGB = true;
348 break;
349 }
350 if ( debug ) {
351 logger.debug("H = " + H );
352 }
353 G.add( H );
354 pairlist.put( H );
355 G2F.add( row );
356 }
357 if ( debug ) {
358 exgb = new ExtendedGB<C>(F,G,F2G,G2F);
359 logger.info("exgb unnorm = " + exgb);
360 }
361 G2F = normalizeMatrix( F.size(), G2F );
362 if ( debug ) {
363 exgb = new ExtendedGB<C>(F,G,F2G,G2F);
364 logger.info("exgb nonmin = " + exgb);
365 boolean t2 = isReductionMatrix( exgb );
366 logger.info("exgb t2 = " + t2);
367 }
368 exgb = minimalExtendedGB(F.size(),G,G2F);
369 G = exgb.G;
370 G2F = exgb.G2F;
371 logger.debug("#sequential list = " + G.size());
372 logger.info("" + pairlist);
373 // setup matrices F and F2G
374 for ( GenPolynomial<C> f : F ) {
375 row = new ArrayList<GenPolynomial<C>>( G.size() );
376 for ( int m = 0; m < G.size(); m++ ) {
377 row.add(null);
378 }
379 H = red.normalform( row, G, f );
380 if ( ! H.isZERO() ) {
381 logger.error("nonzero H = " + H );
382 }
383 F2G.add( row );
384 }
385 exgb = new ExtendedGB<C>(F,G,F2G,G2F);
386 if ( debug ) {
387 logger.info("exgb nonmin = " + exgb);
388 boolean t2 = isReductionMatrix( exgb );
389 logger.info("exgb t2 = " + t2);
390 }
391 return exgb;
392 }
393
394 }