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