001/*
002 * $Id: GroebnerBasePseudoSeq.java 5870 2018-07-20 15:56:23Z kredel $
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            if (debug) {
130                logger.debug("pi    = " + pi);
131                logger.debug("pj    = " + pj);
132            }
133
134            S = red.SPolynomial(pi, pj);
135            if (S.isZERO()) {
136                pair.setZero();
137                continue;
138            }
139            if (debug) {
140                logger.debug("ht(S) = " + S.leadingExpVector());
141            }
142
143            H = red.normalform(G, S);
144            if (H.isZERO()) {
145                pair.setZero();
146                continue;
147            }
148            if (debug) {
149                logger.debug("ht(H) = " + H.leadingExpVector());
150            }
151            H = engine.basePrimitivePart(H);
152            H = H.abs();
153            if (H.isConstant()) {
154                G.clear();
155                G.add(H);
156                return G; // since no threads are activated
157            }
158            if (logger.isDebugEnabled()) {
159                logger.debug("H = " + H);
160            }
161            if (H.length() > 0) {
162                //l++;
163                G.add(H);
164                pairlist.put(H);
165            }
166        }
167        logger.debug("#sequential list = " + G.size());
168        G = minimalGB(G);
169        logger.info("" + pairlist);
170        return G;
171    }
172
173
174    /**
175     * Minimal ordered Groebner basis.
176     * @param Gp a Groebner base.
177     * @return a reduced Groebner base of Gp.
178     */
179    @Override
180    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
181        List<GenPolynomial<C>> G = normalizeZerosOnes(Gp);
182        if (G.size() <= 1) {
183            return G;
184        }
185        // remove top reducible polynomials
186        GenPolynomial<C> a;
187        List<GenPolynomial<C>> F;
188        F = new ArrayList<GenPolynomial<C>>(G.size());
189        while (G.size() > 0) {
190            a = G.remove(0);
191            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
192                // drop polynomial 
193                if (debug) {
194                    System.out.println("dropped " + a);
195                    List<GenPolynomial<C>> ff;
196                    ff = new ArrayList<GenPolynomial<C>>(G);
197                    ff.addAll(F);
198                    a = red.normalform(ff, a);
199                    if (!a.isZERO()) {
200                        System.out.println("error, nf(a) " + a);
201                    }
202                }
203            } else {
204                F.add(a);
205            }
206        }
207        G = F;
208        if (G.size() <= 1) {
209            return G;
210        }
211        Collections.reverse(G); // important for lex GB
212        // reduce remaining polynomials
213        int len = G.size();
214        int i = 0;
215        while (i < len) {
216            a = G.remove(0);
217            //System.out.println("doing " + a.length());
218            a = red.normalform(G, a);
219            a = engine.basePrimitivePart(a); //a.monic(); not possible
220            a = a.abs();
221            //a = red.normalform( F, a );
222            G.add(a); // adds as last
223            i++;
224        }
225        Collections.reverse(G); // undo reverse
226        return G;
227    }
228
229}