001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.List;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.gb.GroebnerBaseAbstract;
016import edu.jas.gb.OrderedPairlist;
017import edu.jas.gb.Pair;
018import edu.jas.gb.PairList;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenPolynomialRing;
021import edu.jas.structure.GcdRingElem;
022import edu.jas.structure.RingFactory;
023import edu.jas.ufd.GCDFactory;
024import edu.jas.ufd.GreatestCommonDivisorAbstract;
025
026
027/**
028 * Groebner Base with pseudo reduction sequential algorithm. Implements
029 * coefficient fraction free Groebner bases.
030 * Coefficients can for example be integers or (commutative) univariate polynomials.
031 * @param <C> coefficient type
032 * @author Heinz Kredel
033 * 
034 * @see edu.jas.application.GBAlgorithmBuilder
035 * @see edu.jas.gbufd.GBFactory
036 */
037
038public class GroebnerBasePseudoSeq<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<C> {
039
040
041    private static final Logger logger = LogManager.getLogger(GroebnerBasePseudoSeq.class);
042
043
044    private static final boolean debug = logger.isDebugEnabled();
045
046
047    /**
048     * Greatest common divisor engine for coefficient content and primitive
049     * parts.
050     */
051    protected final GreatestCommonDivisorAbstract<C> engine;
052
053
054    /**
055     * Pseudo reduction engine.
056     */
057    protected final PseudoReduction<C> red;
058
059
060    /**
061     * Coefficient ring factory.
062     */
063    protected final RingFactory<C> cofac;
064
065
066    /**
067     * Constructor.
068     * @param rf coefficient ring factory.
069     */
070    public GroebnerBasePseudoSeq(RingFactory<C> rf) {
071        this(new PseudoReductionSeq<C>(), rf, new OrderedPairlist<C>());
072    }
073
074
075    /**
076     * Constructor.
077     * @param rf coefficient ring factory.
078     * @param pl pair selection strategy
079     */
080    public GroebnerBasePseudoSeq(RingFactory<C> rf, PairList<C> pl) {
081        this(new PseudoReductionSeq<C>(), rf, pl);
082    }
083
084
085    /**
086     * Constructor.
087     * @param red pseudo reduction engine. <b>Note:</b> red must be an instance
088     *            of PseudoReductionSeq.
089     * @param rf coefficient ring factory.
090     * @param pl pair selection strategy
091     */
092    public GroebnerBasePseudoSeq(PseudoReduction<C> red, RingFactory<C> rf, PairList<C> pl) {
093        super(red, pl);
094        this.red = red;
095        cofac = rf;
096        engine = GCDFactory.<C> getImplementation(rf);
097        //not used: engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf );
098    }
099
100
101    /**
102     * Groebner base using pairlist class.
103     * @param modv module variable number.
104     * @param F polynomial list.
105     * @return GB(F) a Groebner base of F.
106     */
107    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
108        List<GenPolynomial<C>> G = normalizeZerosOnes(F);
109        G = engine.basePrimitivePart(G);
110        if (G.size() <= 1) {
111            return G;
112        }
113        GenPolynomialRing<C> ring = G.get(0).ring;
114        if (ring.coFac.isField()) { // remove ?
115            throw new IllegalArgumentException("coefficients from a field");
116        }
117        PairList<C> pairlist = strategy.create(modv, ring);
118        pairlist.put(G);
119
120        Pair<C> pair;
121        GenPolynomial<C> pi, pj, S, H;
122        while (pairlist.hasNext()) {
123            pair = pairlist.removeNext();
124            if (pair == null)
125                continue;
126
127            pi = pair.pi;
128            pj = pair.pj;
129            logger.debug("pi = {}, pj = {}", pi, pj);
130
131            S = red.SPolynomial(pi, pj);
132            if (S.isZERO()) {
133                pair.setZero();
134                continue;
135            }
136            if (debug) {
137                logger.debug("ht(S) = {}", S.leadingExpVector());
138            }
139
140            H = red.normalform(G, S);
141            if (H.isZERO()) {
142                pair.setZero();
143                continue;
144            }
145            if (debug) {
146                logger.debug("ht(H) = {}", H.leadingExpVector());
147            }
148            H = engine.basePrimitivePart(H);
149            H = H.abs();
150            if (H.isConstant()) {
151                G.clear();
152                G.add(H);
153                return G; // since no threads are activated
154            }
155            if (debug) {
156                logger.debug("H = {}", H);
157            }
158            if (H.length() > 0) {
159                //l++;
160                G.add(H);
161                pairlist.put(H);
162            }
163        }
164        logger.debug("#sequential list = {}", G.size());
165        G = minimalGB(G);
166        logger.info("{}", pairlist);
167        return G;
168    }
169
170
171    /**
172     * Minimal ordered Groebner basis.
173     * @param Gp a Groebner base.
174     * @return a reduced Groebner base of Gp.
175     */
176    @Override
177    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
178        List<GenPolynomial<C>> G = normalizeZerosOnes(Gp);
179        if (G.size() <= 1) {
180            return G;
181        }
182        // remove top reducible polynomials
183        GenPolynomial<C> a;
184        List<GenPolynomial<C>> F;
185        F = new ArrayList<GenPolynomial<C>>(G.size());
186        while (G.size() > 0) {
187            a = G.remove(0);
188            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
189                // drop polynomial 
190                if (debug) {
191                    System.out.println("dropped " + a);
192                    List<GenPolynomial<C>> ff;
193                    ff = new ArrayList<GenPolynomial<C>>(G);
194                    ff.addAll(F);
195                    a = red.normalform(ff, a);
196                    if (!a.isZERO()) {
197                        System.out.println("error, nf(a) " + a);
198                    }
199                }
200            } else {
201                F.add(a);
202            }
203        }
204        G = F;
205        if (G.size() <= 1) {
206            return G;
207        }
208        Collections.reverse(G); // important for lex GB
209        // reduce remaining polynomials
210        int len = G.size();
211        int i = 0;
212        while (i < len) {
213            a = G.remove(0);
214            //System.out.println("doing " + a.length());
215            a = red.normalform(G, a);
216            a = engine.basePrimitivePart(a); //a.monic(); not possible
217            a = a.abs();
218            //a = red.normalform( F, a );
219            G.add(a); // adds as last
220            i++;
221        }
222        Collections.reverse(G); // undo reverse
223        return G;
224    }
225
226}