001/*
002 * $Id: WordGroebnerBasePseudoSeq.java 5870 2018-07-20 15:56:23Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.logging.log4j.Logger;
012import org.apache.logging.log4j.LogManager; 
013
014import edu.jas.gb.OrderedWordPairlist;
015import edu.jas.gb.WordGroebnerBaseAbstract;
016import edu.jas.gb.WordPair;
017import edu.jas.gb.WordPairList;
018import edu.jas.poly.GenWordPolynomial;
019import edu.jas.poly.GenWordPolynomialRing;
020import edu.jas.structure.GcdRingElem;
021import edu.jas.structure.RingFactory;
022
023
024/**
025 * Non-commutative word Groebner Base sequential algorithm. Implements Groebner
026 * bases and GB test. Coefficients can for example be integers or (commutative)
027 * univariate polynomials.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032public class WordGroebnerBasePseudoSeq<C extends GcdRingElem<C>> extends WordGroebnerBaseAbstract<C> {
033
034
035    private static final Logger logger = LogManager.getLogger(WordGroebnerBasePseudoSeq.class);
036
037
038    private static final boolean debug = logger.isDebugEnabled();
039
040
041    /**
042     * Coefficient ring factory.
043     */
044    protected final RingFactory<C> cofac;
045
046
047    /**
048     * Constructor.
049     * @param rf coefficient ring factory.
050     */
051    public WordGroebnerBasePseudoSeq(RingFactory<C> rf) {
052        this(rf, new WordPseudoReductionSeq<C>());
053    }
054
055
056    /**
057     * Constructor.
058     * @param rf coefficient ring factory.
059     * @param red Reduction engine
060     */
061    public WordGroebnerBasePseudoSeq(RingFactory<C> rf, WordPseudoReductionSeq<C> red) {
062        this(rf, red, new OrderedWordPairlist<C>());
063    }
064
065
066    /**
067     * Constructor.
068     * @param rf coefficient ring factory.
069     * @param red Reduction engine
070     * @param pl pair selection strategy
071     */
072    public WordGroebnerBasePseudoSeq(RingFactory<C> rf, WordPseudoReductionSeq<C> red, WordPairList<C> pl) {
073        super(red, pl);
074        cofac = rf;
075        if (!cofac.isCommutative()) {
076            logger.warn("reduction not correct for " + cofac.toScript());
077        }
078        //engine = GCDFactory.<C> getImplementation(rf);
079        //not used: engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf );
080    }
081
082
083    /**
084     * Word Groebner base using word pairlist class.
085     * @param F word polynomial list.
086     * @return GB(F) a finite non-commutative Groebner base of F, if it exists.
087     */
088    @Override
089    public List<GenWordPolynomial<C>> GB(List<GenWordPolynomial<C>> F) {
090        List<GenWordPolynomial<C>> G = normalizeZerosOnes(F);
091        //G = PolyUtil.<C> wordMonic(G);
092        G = basePrimitivePart(G);
093        if (G.size() <= 1) {
094            return G;
095        }
096        GenWordPolynomialRing<C> ring = G.get(0).ring;
097        if (!ring.coFac.isCommutative()) {
098            throw new IllegalArgumentException("coefficient ring not commutative");
099        }
100        //Collections.sort(G);
101        OrderedWordPairlist<C> pairlist = (OrderedWordPairlist<C>) strategy.create(ring);
102        pairlist.put(G);
103        logger.info("start " + pairlist);
104
105        WordPair<C> pair;
106        GenWordPolynomial<C> pi;
107        GenWordPolynomial<C> pj;
108        List<GenWordPolynomial<C>> S;
109        GenWordPolynomial<C> H;
110        while (pairlist.hasNext()) {
111            pair = pairlist.removeNext();
112            //logger.debug("pair = " + pair);
113            if (pair == null) {
114                continue;
115            }
116            pi = pair.pi;
117            pj = pair.pj;
118            if (debug) {
119                logger.info("pi   = " + pi + ", pj = " + pj);
120                //logger.info("pj    = " + pj);
121            }
122
123            S = red.SPolynomials(pi, pj);
124            if (S.isEmpty()) {
125                continue;
126            }
127            for (GenWordPolynomial<C> s : S) {
128                if (s.isZERO()) {
129                    //pair.setZero();
130                    continue;
131                }
132                if (debug) {
133                    logger.info("ht(S) = " + s.leadingWord());
134                }
135                boolean t = pairlist.criterion3(pair.i, pair.j, s.leadingWord());
136                //System.out.println("criterion3(" + pair.i + "," + pair.j + ") = " + t);
137                //if ( !t ) {
138                //    continue;  
139                //}
140
141                H = red.normalform(G, s);
142                if (debug) {
143                    //logger.info("pair = " + pair); 
144                    //logger.info("ht(S) = " + S.monic()); //.leadingWord() );
145                    logger.info("ht(H) = " + H.monic()); //.leadingWord() );
146                }
147                if (H.isZERO()) {
148                    //pair.setZero();
149                    continue;
150                }
151                if (!t) {
152                    logger.info("criterion3(" + pair.i + "," + pair.j + ") wrong: " + s.leadingWord()
153                                    + " --> " + H.leadingWord());
154                }
155
156                //H = H.monic();
157                H = basePrimitivePart(H);
158                H = H.abs();
159                if (debug) {
160                    logger.info("ht(H) = " + H.leadingWord());
161                }
162                if (H.isONE()) {
163                    G.clear();
164                    G.add(H);
165                    return G; // since no threads are activated
166                }
167                if (debug) {
168                    logger.info("H = " + H);
169                }
170                if (H.length() > 0) {
171                    //l++;
172                    G.add(H);
173                    pairlist.put(H);
174                }
175            }
176        }
177        //logger.info("#sequential list = " + G.size());
178        G = minimalGB(G);
179        logger.info("" + pairlist);
180        //Collections.sort(G);
181        //Collections.reverse(G);
182        return G;
183    }
184
185
186    /**
187     * GenWordPolynomial base coefficient content.
188     * @param P GenWordPolynomial.
189     * @return cont(P).
190     */
191    public C baseContent(GenWordPolynomial<C> P) {
192        if (P == null) {
193            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
194        }
195        if (P.isZERO()) {
196            return P.ring.getZEROCoefficient();
197        }
198        C d = null;
199        for (C c : P.getMap().values()) {
200            if (d == null) {
201                d = c;
202            } else {
203                d = d.gcd(c);
204            }
205            if (d.isONE()) {
206                return d;
207            }
208        }
209        if (d.signum() < 0) {
210            d = d.negate();
211        }
212        return d;
213    }
214
215
216    /**
217     * GenWordPolynomial base coefficient primitive part.
218     * @param P GenWordPolynomial.
219     * @return pp(P).
220     */
221    public GenWordPolynomial<C> basePrimitivePart(GenWordPolynomial<C> P) {
222        if (P == null) {
223            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
224        }
225        if (P.isZERO()) {
226            return P;
227        }
228        C d = baseContent(P);
229        if (d.isONE()) {
230            return P;
231        }
232        GenWordPolynomial<C> pp = P.divide(d);
233        if (debug) {
234            GenWordPolynomial<C> p = pp.multiply(d);
235            if (!p.equals(P)) {
236                throw new ArithmeticException("pp(p)*cont(p) != p: ");
237            }
238        }
239        return pp;
240    }
241
242
243    /**
244     * List of GenWordPolynomial base coefficient primitive part.
245     * @param F list of GenWordPolynomials.
246     * @return pp(F).
247     */
248    public List<GenWordPolynomial<C>> basePrimitivePart(List<GenWordPolynomial<C>> F) {
249        if (F == null || F.isEmpty()) {
250            return F;
251        }
252        List<GenWordPolynomial<C>> Pp = new ArrayList<GenWordPolynomial<C>>(F.size());
253        for (GenWordPolynomial<C> f : F) {
254            GenWordPolynomial<C> p = basePrimitivePart(f);
255            Pp.add(p);
256        }
257        return Pp;
258    }
259
260}