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