001/*
002 * $Id: GroebnerBasePseudoRecSeq.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.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            if (debug) {
153                logger.debug("pi    = " + pi);
154                logger.debug("pj    = " + pj);
155            }
156
157            S = red.SPolynomial(pi, pj);
158            if (S.isZERO()) {
159                pair.setZero();
160                continue;
161            }
162            if (debug) {
163                logger.info("ht(S) = " + S.leadingExpVector());
164            }
165
166            H = redRec.normalformRecursive(G, S);
167            if (H.isZERO()) {
168                pair.setZero();
169                continue;
170            }
171            if (debug) {
172                logger.info("ht(H) = " + H.leadingExpVector());
173            }
174            H = engine.recursivePrimitivePart(H);
175            H = H.abs();
176            if (H.isConstant()) {
177                G.clear();
178                G.add(H);
179                return G; // since no threads are activated
180            }
181            if (debug) {
182                logger.debug("H = " + H);
183            }
184            if (H.length() > 0) {
185                //l++;
186                G.add(H);
187                pairlist.put(H);
188            }
189        }
190        logger.debug("#sequential list = " + G.size());
191        G = minimalGB(G);
192        logger.info("" + pairlist);
193        return G;
194    }
195
196
197    /**
198     * Minimal ordered Groebner basis.
199     * @param Gp a Groebner base.
200     * @return a reduced Groebner base of Gp.
201     */
202    @Override
203    public List<GenPolynomial<GenPolynomial<C>>> minimalGB(List<GenPolynomial<GenPolynomial<C>>> Gp) {
204        List<GenPolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Gp);
205        if (G.size() <= 1) {
206            return G;
207        }
208        // remove top reducible polynomials
209        GenPolynomial<GenPolynomial<C>> a;
210        List<GenPolynomial<GenPolynomial<C>>> F;
211        F = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G.size());
212        while (G.size() > 0) {
213            a = G.remove(0);
214            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
215                // drop polynomial 
216                if (debug) {
217                    System.out.println("dropped " + a);
218                    List<GenPolynomial<GenPolynomial<C>>> ff;
219                    ff = new ArrayList<GenPolynomial<GenPolynomial<C>>>(G);
220                    ff.addAll(F);
221                    a = redRec.normalformRecursive(ff, a);
222                    if (!a.isZERO()) {
223                        System.out.println("error, nf(a) " + a);
224                    }
225                }
226            } else {
227                F.add(a);
228            }
229        }
230        G = F;
231        if (G.size() <= 1) {
232            return G;
233        }
234        Collections.reverse(G); // important for lex GB
235        // reduce remaining polynomials
236        int len = G.size();
237        int i = 0;
238        while (i < len) {
239            a = G.remove(0);
240            //System.out.println("doing " + a.length());
241            a = redRec.normalformRecursive(G, a);
242            a = engine.recursivePrimitivePart(a); //a.monic(); was not required
243            a = a.abs();
244            //a = redRec.normalformRecursive( F, a );
245            G.add(a); // adds as last
246            i++;
247        }
248        Collections.reverse(G); // undo reverse
249        return G;
250    }
251
252
253    /**
254     * Groebner base simple test.
255     * @param modv module variable number.
256     * @param F recursive polynomial list.
257     * @return true, if F is a Groebner base, else false.
258     */
259    @Override
260    public boolean isGBsimple(int modv, List<GenPolynomial<GenPolynomial<C>>> F) {
261        if (F == null || F.isEmpty()) {
262            return true;
263        }
264        GenPolynomial<GenPolynomial<C>> pi, pj, s, h;
265        ExpVector ei, ej, eij;
266        for (int i = 0; i < F.size(); i++) {
267            pi = F.get(i);
268            ei = pi.leadingExpVector();
269            for (int j = i + 1; j < F.size(); j++) {
270                pj = F.get(j);
271                ej = pj.leadingExpVector();
272                if (!red.moduleCriterion(modv, ei, ej)) {
273                    continue;
274                }
275                eij = ei.lcm(ej);
276                if (!red.criterion4(ei, ej, eij)) {
277                    continue;
278                }
279                //if (!criterion3(i, j, eij, F)) {
280                //    continue;
281                //}
282                s = red.SPolynomial(pi, pj);
283                if (s.isZERO()) {
284                    continue;
285                }
286                //System.out.println("i, j = " + i + ", " + j); 
287                h = redRec.normalformRecursive(F, s);
288                if (!h.isZERO()) {
289                    logger.info("no GB: pi = " + pi + ", pj = " + pj);
290                    logger.info("s  = " + s + ", h = " + h);
291                    return false;
292                }
293            }
294        }
295        return true;
296    }
297
298}