001/*
002 * $Id$
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.kern.LocalTimeStatus;
014import edu.jas.poly.GenWordPolynomial;
015import edu.jas.poly.GenWordPolynomialRing;
016import edu.jas.poly.PolyUtil;
017import edu.jas.structure.RingElem;
018
019
020/**
021 * Non-commutative word Groebner Base sequential algorithm. Implements
022 * Groebner bases and GB test. Run-time for GB computation is limited
023 * to 20 seconds. To change this limit use
024 * <pre>
025 *   wbb.timestatus.setLimit(newLimit);
026 * </pre>
027 * or decativate it for infinite running time
028 * <pre>
029 *   wbb.timestatus.setNotActive();
030 * </pre>
031 * @param <C> coefficient type
032 * @author Heinz Kredel
033 */
034
035public class WordGroebnerBaseSeq<C extends RingElem<C>> extends WordGroebnerBaseAbstract<C> {
036
037
038    private static final Logger logger = LogManager.getLogger(WordGroebnerBaseSeq.class);
039
040
041    private static final boolean debug = logger.isDebugEnabled();
042
043
044    public final LocalTimeStatus timestatus;
045
046
047    /**
048     * Constructor.
049     */
050    public WordGroebnerBaseSeq() {
051        super();
052        timestatus = new LocalTimeStatus(true, 20*1000, false);
053    }
054
055
056    /**
057     * Constructor.
058     * @param red Reduction engine
059     */
060    public WordGroebnerBaseSeq(WordReduction<C> red) {
061        super(red);
062        timestatus = new LocalTimeStatus(true, 20*1000, false);
063    }
064
065
066    /**
067     * Constructor.
068     * @param red Reduction engine
069     * @param pl pair selection strategy
070     */
071    public WordGroebnerBaseSeq(WordReduction<C> red, WordPairList<C> pl) {
072        super(red, pl);
073        timestatus = new LocalTimeStatus(true, 20*1000, false);
074    }
075
076
077    /**
078     * Word Groebner base using word pairlist class.
079     * @param F word polynomial list.
080     * @return GB(F) a finite non-commutative Groebner base of F, if it exists.
081     */
082    @Override
083    public List<GenWordPolynomial<C>> GB(List<GenWordPolynomial<C>> F) {
084        List<GenWordPolynomial<C>> G = normalizeZerosOnes(F);
085        G = PolyUtil.<C> wordMonic(G);
086        if (G.size() <= 1) {
087            return G;
088        }
089        GenWordPolynomialRing<C> ring = G.get(0).ring;
090        if (!ring.coFac.isField()) {
091            throw new IllegalArgumentException("coefficients not from a field");
092        }
093        //Collections.sort(G);
094        OrderedWordPairlist<C> pairlist = (OrderedWordPairlist<C>) strategy.create(ring);
095        pairlist.put(G);
096        logger.info("start {}", pairlist);
097        timestatus.restart();
098        //if (timestatus.isActive()) {
099        //    throw new RuntimeException("timestatus: " + timestatus);
100        //}
101
102        WordPair<C> pair;
103        GenWordPolynomial<C> pi;
104        GenWordPolynomial<C> pj;
105        List<GenWordPolynomial<C>> S;
106        GenWordPolynomial<C> H;
107        int infin = 0;
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 (debug) {
117                logger.info("pi   = {}, pj = {}", pi, pj);
118            }
119
120            S = red.SPolynomials(pi, pj);
121            if (S.isEmpty()) {
122                continue;
123            }
124            for (GenWordPolynomial<C> s : S) {
125                if (s.isZERO()) {
126                    //pair.setZero();
127                    continue;
128                }
129                if (debug) {
130                    logger.info("ht(S) = {}", s.leadingWord());
131                }
132                boolean t = pairlist.criterion3(pair.i, pair.j, s.leadingWord());
133                //System.out.println("criterion3(" + pair.i + "," + pair.j + ") = " + t);
134                //if ( !t ) {
135                //    continue;  
136                //}
137
138                H = red.normalform(G, s);
139                if (debug) {
140                    //logger.info("pair = {}", pair);
141                    //logger.info("ht(S) = {}", S.monic()); //.leadingWord() );
142                    logger.info("ht(H) = {}", H.monic()); //.leadingWord() );
143                }
144                if (H.isZERO()) {
145                    //pair.setZero();
146                    continue;
147                }
148                if (!t) {
149                    logger.info("criterion3({},{}) wrong: {} --> {}", pair.i, pair.j, s.leadingWord(), H.leadingWord());
150                }
151
152                H = H.monic();
153                if (debug) {
154                    logger.info("ht(H) = {}", H.leadingWord());
155                }
156                if (H.isONE()) {
157                    G.clear();
158                    G.add(H);
159                    return G; // since no threads are activated
160                }
161                if (debug) {
162                    logger.info("H = {}", H);
163                }
164                if (H.length() > 0) {
165                    //l++;
166                    G.add(H);
167                    pairlist.put(H);
168                }
169                if (H.degree() > 9) {
170                    //System.out.println("deg(H): " + H.degree());
171                    //logger.warn("word GB too high degree {}", H.degree());
172                    timestatus.checkTime("word GB degree > 9: " + H.degree());
173                }
174
175                if (s.leadingWord().dependencyOnVariables().equals(H.leadingWord().dependencyOnVariables())) {
176                    logger.info("LT depend: {} --> {}", s.leadingWord().dependencyOnVariables(), H.leadingWord().dependencyOnVariables());
177                    logger.info("LT depend: {} --> {}", s, H);
178                    infin++;
179                    if (infin > 500) {
180                        //System.out.println("deg(H): " + H.degree());
181                        //throw new RuntimeException("no convergence in word GB: " + infin);
182                        timestatus.checkTime("no convergence in word GB: > 500: " + infin);
183                    }
184                }
185            }
186        }
187        //logger.info("#sequential list = {}", G.size());
188        G = minimalGB(G);
189        logger.info("end   {}", pairlist);
190        //Collections.sort(G);
191        //Collections.reverse(G);
192        return G;
193    }
194
195}