Source code

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