001/*
002 * $Id: WordGroebnerBaseSeq.java 4150 2012-09-01 09:18:23Z 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;
014import edu.jas.poly.Word;
015import edu.jas.poly.GenWordPolynomial;
016import edu.jas.poly.GenWordPolynomialRing;
017
018
019/**
020 * Word Groebner Base sequential algorithm.
021 * Implements Groebner bases and GB test.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025
026public class WordGroebnerBaseSeq<C extends RingElem<C>> 
027       extends WordGroebnerBaseAbstract<C>  {
028
029    private static final Logger logger = Logger.getLogger(WordGroebnerBaseSeq.class);
030    private final boolean debug = logger.isDebugEnabled();
031
032
033    /**
034     * Constructor.
035     */
036    public WordGroebnerBaseSeq() {
037        super();
038    }
039
040
041    /**
042     * Constructor.
043     * @param red Reduction engine
044     */
045    public WordGroebnerBaseSeq(WordReduction<C> red) {
046        super(red);
047    }
048
049
050    /**
051     * Constructor.
052     * @param red Reduction engine
053     * @param pl pair selection strategy
054     */
055    public WordGroebnerBaseSeq(WordReduction<C> red, WordPairList<C> pl) {
056        super(red,pl);
057    }
058
059
060    /**
061     * Word Groebner base using word pairlist class.
062     * @param F word polynomial list.
063     * @return GB(F) a finite non-commutative Groebner base of F, if it exists.
064     */
065    public List<GenWordPolynomial<C>> GB( List<GenWordPolynomial<C>> F ) {  
066        GenWordPolynomial<C> p;
067        List<GenWordPolynomial<C>> G = new ArrayList<GenWordPolynomial<C>>();
068        WordPairList<C> pairlist = null; 
069        int l = F.size();
070        ListIterator<GenWordPolynomial<C>> it = F.listIterator();
071        while ( it.hasNext() ) { 
072            p = it.next();
073            if ( p.length() > 0 ) {
074               p = p.monic();
075               if ( p.isONE() ) {
076                  G.clear(); G.add( p );
077                  return G; // since no threads are activated
078               }
079               G.add( p );
080               if ( pairlist == null ) {
081                   //pairlist = new OrderedPairlist<C>(p.ring );
082                  pairlist = strategy.create( p.ring );
083                  if ( ! p.ring.coFac.isField() ) {
084                     throw new IllegalArgumentException("coefficients not from a field");
085                  }
086               }
087               // putOne not required
088               pairlist.put( p );
089            } else { 
090               l--;
091            }
092        }
093        if ( l <= 1 ) {
094           return G; // since no threads are activated
095        }
096        logger.info("start " + pairlist); 
097
098        WordPair<C> pair;
099        GenWordPolynomial<C> pi;
100        GenWordPolynomial<C> pj;
101        List<GenWordPolynomial<C>> S;
102        GenWordPolynomial<C> H;
103        while ( pairlist.hasNext() ) {
104              pair = pairlist.removeNext();
105              //logger.debug("pair = " + pair);
106              if ( pair == null ) {
107                  continue; 
108              }
109              pi = pair.pi; 
110              pj = pair.pj; 
111              if ( /*false &&*/ debug ) {
112                 logger.debug("pi    = " + pi );
113                 logger.debug("pj    = " + pj );
114              }
115
116              S = red.SPolynomials( pi, pj );
117              if ( S.isEmpty() ) {
118                 continue;
119              }
120              for ( GenWordPolynomial<C> s : S ) {
121                  if ( s.isZERO() ) {
122                      //pair.setZero();
123                      continue;
124                  }
125                  if ( debug ) {
126                      logger.debug("ht(S) = " + s.leadingWord() );
127                  }
128
129                  H = red.normalform( G, s );
130                  if ( debug ) {
131                      //logger.info("pair = " + pair); 
132                      //logger.info("ht(S) = " + S.monic()); //.leadingWord() );
133                      logger.info("ht(H) = " + H.monic()); //.leadingWord() );
134                  }
135                  if ( H.isZERO() ) {
136                      //pair.setZero();
137                      continue;
138                  }
139                  H = H.monic();
140                  if ( debug ) {
141                      logger.info("ht(H) = " + H.leadingWord() );
142                  }
143                  if ( H.isONE() ) {
144                      G.clear(); G.add( H );
145                      return G; // since no threads are activated
146                  }
147                  if ( debug ) {
148                      logger.info("H = " + H );
149                  }
150                  if ( H.length() > 0 ) {
151                      l++;
152                      G.add( H );
153                      pairlist.put( H );
154                  }
155              }
156        }
157        logger.debug("#sequential list = " + G.size());
158        G = minimalGB(G);
159        logger.info("" + pairlist); 
160        return G;
161    }
162
163}