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.ExpVector;
020import edu.jas.poly.GenPolynomial;
021import edu.jas.poly.GenPolynomialRing;
022import edu.jas.structure.GcdRingElem;
023import edu.jas.structure.RingFactory;
024import edu.jas.ufd.GCDFactory;
025import edu.jas.ufd.GreatestCommonDivisorAbstract;
026
027
028/**
029 * Groebner Base with pseudo reduction sequential algorithm for integral
030 * function coefficients. Implements polynomial fraction free coefficients
031 * Groebner bases. Coefficients can for example be 
032 * (commutative) multivariate polynomials.
033 * @param <C> base coefficient type
034 * @author Heinz Kredel
035 * 
036 * @see edu.jas.application.GBAlgorithmBuilder
037 * @see edu.jas.gbufd.GBFactory
038 */
039
040public class GroebnerBasePseudoRecSeq<C extends GcdRingElem<C>> extends
041                GroebnerBaseAbstract<GenPolynomial<C>> {
042
043
044    private static final Logger logger = LogManager.getLogger(GroebnerBasePseudoRecSeq.class);
045
046
047    private static final boolean debug = logger.isDebugEnabled();
048
049
050    /**
051     * Greatest common divisor engine for coefficient content and primitive
052     * parts.
053     */
054    protected final GreatestCommonDivisorAbstract<C> engine;
055
056
057    /**
058     * Pseudo reduction engine.
059     */
060    protected final PseudoReduction<C> redRec;
061
062
063    /**
064     * Pseudo reduction engine.
065     */
066    protected final PseudoReduction<GenPolynomial<C>> red;
067
068
069    /**
070     * Coefficient ring factory.
071     */
072    protected final RingFactory<GenPolynomial<C>> cofac;
073
074
075    /**
076     * Base coefficient ring factory.
077     */
078    protected final RingFactory<C> baseCofac;
079
080
081    /**
082     * Constructor.
083     * @param rf coefficient ring factory.
084     */
085    public GroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf) {
086        this(new PseudoReductionSeq<GenPolynomial<C>>(), rf, new OrderedPairlist<GenPolynomial<C>>(
087                        new GenPolynomialRing<GenPolynomial<C>>(rf, 1))); // 1=hack
088    }
089
090
091    /**
092     * Constructor.
093     * @param rf coefficient ring factory.
094     * @param pl pair selection strategy
095     */
096    public GroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, PairList<GenPolynomial<C>> pl) {
097        this(new PseudoReductionSeq<GenPolynomial<C>>(), rf, pl);
098    }
099
100
101    /**
102     * Constructor.
103     * @param red pseudo reduction engine. <b>Note:</b> red must be an instance
104     *            of PseudoReductionSeq.
105     * @param rf coefficient ring factory.
106     * @param pl pair selection strategy
107     */
108    @SuppressWarnings("unchecked")
109    public GroebnerBasePseudoRecSeq(PseudoReduction<GenPolynomial<C>> red, RingFactory<GenPolynomial<C>> rf,
110                    PairList<GenPolynomial<C>> pl) {
111        super(red, pl);
112        this.red = red;
113        this.redRec = (PseudoReduction<C>) (PseudoReduction) red;
114        cofac = rf;
115        GenPolynomialRing<C> rp = (GenPolynomialRing<C>) cofac;
116        baseCofac = rp.coFac;
117        //engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getImplementation( baseCofac );
118        //not used: 
119        engine = GCDFactory.<C> getProxy(baseCofac);
120    }
121
122
123    /**
124     * Groebner base using pairlist class.
125     * @param modv module variable number.
126     * @param F polynomial list.
127     * @return GB(F) a Groebner base of F.
128     */
129    //@Override
130    public List<GenPolynomial<GenPolynomial<C>>> GB(int modv, List<GenPolynomial<GenPolynomial<C>>> F) {
131        List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(F);
132        G = engine.recursivePrimitivePart(G);
133        if (G.size() <= 1) {
134            return G;
135        }
136        GenPolynomialRing<GenPolynomial<C>> ring = G.get(0).ring;
137        if (ring.coFac.isField()) { // remove ?
138            throw new IllegalArgumentException("coefficients from a field");
139        }
140        PairList<GenPolynomial<C>> pairlist = strategy.create(modv, ring);
141        pairlist.put(G);
142
143        Pair<GenPolynomial<C>> pair;
144        GenPolynomial<GenPolynomial<C>> pi, pj, S, H;
145        while (pairlist.hasNext()) {
146            pair = pairlist.removeNext();
147            if (pair == null)
148                continue;
149
150            pi = pair.pi;
151            pj = pair.pj;
152            logger.debug("pi = {}, pj = {}", pi, pj);
153
154            S = red.SPolynomial(pi, pj);
155            if (S.isZERO()) {
156                pair.setZero();
157                continue;
158            }
159            if (debug) {
160                logger.info("ht(S) = {}", S.leadingExpVector());
161            }
162
163            H = redRec.normalformRecursive(G, S);
164            if (H.isZERO()) {
165                pair.setZero();
166                continue;
167            }
168            if (debug) {
169                logger.info("ht(H) = {}", H.leadingExpVector());
170            }
171            H = engine.recursivePrimitivePart(H);
172            H = H.abs();
173            if (H.isConstant()) {
174                G.clear();
175                G.add(H);
176                return G; // since no threads are activated
177            }
178            if (debug) {
179                logger.debug("H = {}", H);
180            }
181            if (H.length() > 0) {
182                //l++;
183                G.add(H);
184                pairlist.put(H);
185            }
186        }
187        logger.debug("#sequential list = {}", G.size());
188        G = minimalGB(G);
189        logger.info("{}", pairlist);
190        return G;
191    }
192
193
194    /**
195     * Minimal ordered Groebner basis.
196     * @param Gp a Groebner base.
197     * @return a reduced Groebner base of Gp.
198     */
199    @Override
200    public List<GenPolynomial<GenPolynomial<C>>> minimalGB(List<GenPolynomial<GenPolynomial<C>>> Gp) {
201        List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Gp);
202        if (G.size() <= 1) {
203            return G;
204        }
205        // remove top reducible polynomials
206        GenPolynomial<GenPolynomial<C>> a;
207        List<GenPolynomial<GenPolynomial<C>>> F;
208        F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size());
209        while (G.size() > 0) {
210            a = G.remove(0);
211            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
212                // drop polynomial 
213                if (debug) {
214                    System.out.println("dropped " + a);
215                    List<GenPolynomial<GenPolynomial<C>>> ff;
216                    ff = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G);
217                    ff.addAll(F);
218                    a = redRec.normalformRecursive(ff, a);
219                    if (!a.isZERO()) {
220                        System.out.println("error, nf(a) " + a);
221                    }
222                }
223            } else {
224                F.add(a);
225            }
226        }
227        G = F;
228        if (G.size() <= 1) {
229            return G;
230        }
231        Collections.reverse(G); // important for lex GB
232        // reduce remaining polynomials
233        int len = G.size();
234        int i = 0;
235        while (i < len) {
236            a = G.remove(0);
237            //System.out.println("doing " + a.length());
238            a = redRec.normalformRecursive(G, a);
239            a = engine.recursivePrimitivePart(a); //a.monic(); was not required
240            a = a.abs();
241            //a = redRec.normalformRecursive( F, a );
242            G.add(a); // adds as last
243            i++;
244        }
245        Collections.reverse(G); // undo reverse
246        return G;
247    }
248
249
250    /**
251     * Groebner base simple test.
252     * @param modv module variable number.
253     * @param F recursive polynomial list.
254     * @return true, if F is a Groebner base, else false.
255     */
256    @Override
257    public boolean isGBsimple(int modv, List<GenPolynomial<GenPolynomial<C>>> F) {
258        if (F == null || F.isEmpty()) {
259            return true;
260        }
261        GenPolynomial<GenPolynomial<C>> pi, pj, s, h;
262        ExpVector ei, ej, eij;
263        for (int i = 0; i < F.size(); i++) {
264            pi = F.get(i);
265            ei = pi.leadingExpVector();
266            for (int j = i + 1; j < F.size(); j++) {
267                pj = F.get(j);
268                ej = pj.leadingExpVector();
269                if (!red.moduleCriterion(modv, ei, ej)) {
270                    continue;
271                }
272                eij = ei.lcm(ej);
273                if (!red.criterion4(ei, ej, eij)) {
274                    continue;
275                }
276                //if (!criterion3(i, j, eij, F)) {
277                //    continue;
278                //}
279                s = red.SPolynomial(pi, pj);
280                if (s.isZERO()) {
281                    continue;
282                }
283                //System.out.println("i, j = " + i + ", " + j); 
284                h = redRec.normalformRecursive(F, s);
285                if (!h.isZERO()) {
286                    logger.info("no GB: pi = {}, pj = {}", pi, pj);
287                    logger.info("s = {}, h = {}", s, h);
288                    return false;
289                }
290            }
291        }
292        return true;
293    }
294
295}