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