Source code

001/*
002 * $Id: SolvableGroebnerBasePseudoSeq.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.OrderedPairlist;
016import edu.jas.gb.Pair;
017import edu.jas.gb.PairList;
018import edu.jas.gb.SolvableExtendedGB;
019import edu.jas.gb.SolvableGroebnerBaseAbstract;
020import edu.jas.poly.GenSolvablePolynomial;
021import edu.jas.poly.GenSolvablePolynomialRing;
022// import edu.jas.poly.GenPolynomialRing;
023import edu.jas.poly.PolynomialList;
024import edu.jas.structure.GcdRingElem;
025import edu.jas.structure.RingFactory;
026import edu.jas.ufd.GCDFactory;
027import edu.jas.ufd.GreatestCommonDivisorAbstract;
028import edu.jas.ufd.GreatestCommonDivisorFake;
029
030
031/**
032 * Solvable Groebner Base with pseudo reduction sequential algorithm. Implements
033 * coefficient fraction free Groebner bases. Coefficients can for example be
034 * integers or (commutative) univariate polynomials.
035 * @param <C> coefficient type
036 * @author Heinz Kredel
037 * 
038 * @see edu.jas.application.GBAlgorithmBuilder
039 * @see edu.jas.gbufd.GBFactory
040 */
041
042public class SolvableGroebnerBasePseudoSeq<C extends GcdRingElem<C>> extends SolvableGroebnerBaseAbstract<C> {
043
044
045    private static final Logger logger = LogManager.getLogger(SolvableGroebnerBasePseudoSeq.class);
046
047
048    private static final boolean debug = logger.isDebugEnabled();
049
050
051    /**
052     * Greatest common divisor engine for coefficient content and primitive
053     * parts.
054     */
055    protected final GreatestCommonDivisorAbstract<C> engine;
056
057
058    /**
059     * Pseudo reduction engine.
060     */
061    protected final SolvablePseudoReduction<C> sred;
062
063
064    /**
065     * Coefficient ring factory.
066     */
067    protected final RingFactory<C> cofac;
068
069
070    /**
071     * Constructor.
072     * @param rf coefficient ring factory.
073     */
074    public SolvableGroebnerBasePseudoSeq(RingFactory<C> rf) {
075        this(new SolvablePseudoReductionSeq<C>(), rf, new OrderedPairlist<C>());
076    }
077
078
079    /**
080     * Constructor.
081     * @param rf coefficient ring factory.
082     * @param pl pair selection strategy
083     */
084    public SolvableGroebnerBasePseudoSeq(RingFactory<C> rf, PairList<C> pl) {
085        this(new SolvablePseudoReductionSeq<C>(), rf, pl);
086    }
087
088
089    /**
090     * Constructor.
091     * @param red pseudo reduction engine. <b>Note:</b> red must be an instance
092     *            of PseudoReductionSeq.
093     * @param rf coefficient ring factory.
094     * @param pl pair selection strategy
095     */
096    public SolvableGroebnerBasePseudoSeq(SolvablePseudoReduction<C> red, RingFactory<C> rf, PairList<C> pl) {
097        super(red, pl);
098        this.sred = red;
099        cofac = rf;
100        if (!cofac.isCommutative()) {
101            logger.warn("right reduction not correct for " + cofac.toScript());
102            engine = new GreatestCommonDivisorFake<C>(); // only for Ore conditions
103            // TODO check that also coeffTable is empty for recursive solvable poly ring
104            //System.out.println("stack trace = "); 
105            //Exception e = new RuntimeException("get stack trace");
106            //e.printStackTrace();
107        } else {
108            //engine = GCDFactory.<C> getImplementation(rf);
109            engine = GCDFactory.<C> getProxy(rf);
110        }
111    }
112
113
114    /**
115     * Left Groebner base using pairlist class.
116     * @param modv module variable number.
117     * @param F polynomial list.
118     * @return GB(F) a Groebner base of F.
119     */
120    @Override
121    public List<GenSolvablePolynomial<C>> leftGB(int modv, List<GenSolvablePolynomial<C>> F) {
122        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F);
123        G = PolynomialList.<C> castToSolvableList(engine.basePrimitivePart(PolynomialList.<C> castToList(G)));
124        if (G.size() <= 1) {
125            return G;
126        }
127        GenSolvablePolynomialRing<C> ring = G.get(0).ring;
128        if (ring.coFac.isField()) { // remove ?
129            throw new IllegalArgumentException("coefficients from a field");
130        }
131        PairList<C> pairlist = strategy.create(modv, ring);
132        pairlist.put(PolynomialList.<C> castToList(G));
133
134        Pair<C> pair;
135        GenSolvablePolynomial<C> pi, pj, S, H;
136        while (pairlist.hasNext()) {
137            pair = pairlist.removeNext();
138            if (pair == null)
139                continue;
140
141            pi = (GenSolvablePolynomial<C>) pair.pi;
142            pj = (GenSolvablePolynomial<C>) pair.pj;
143            if (debug) {
144                logger.debug("pi    = " + pi);
145                logger.debug("pj    = " + pj);
146            }
147
148            S = sred.leftSPolynomial(pi, pj);
149            if (S.isZERO()) {
150                pair.setZero();
151                continue;
152            }
153            if (debug) {
154                logger.debug("ht(S) = " + S.leadingExpVector());
155            }
156
157            H = sred.leftNormalform(G, S);
158            if (H.isZERO()) {
159                pair.setZero();
160                continue;
161            }
162            if (debug) {
163                logger.debug("ht(H) = " + H.leadingExpVector());
164            }
165            H = (GenSolvablePolynomial<C>) engine.basePrimitivePart(H);
166            H = (GenSolvablePolynomial<C>) H.abs();
167            if (H.isConstant()) {
168                G.clear();
169                G.add(H);
170                return G; // since no threads are activated
171            }
172            if (logger.isDebugEnabled()) {
173                logger.debug("H = " + H);
174            }
175            if (H.length() > 0) {
176                G.add(H);
177                pairlist.put(H);
178            }
179        }
180        logger.debug("#sequential list = " + G.size());
181        G = leftMinimalGB(G);
182        logger.info("" + pairlist);
183        return G;
184    }
185
186
187    /**
188     * Minimal ordered Solvable Groebner basis.
189     * @param Gp a Solvable Groebner base.
190     * @return a reduced Solvable Groebner base of Gp.
191     */
192    @Override
193    public List<GenSolvablePolynomial<C>> leftMinimalGB(List<GenSolvablePolynomial<C>> Gp) {
194        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(Gp);
195        if (G.size() <= 1) {
196            return G;
197        }
198        // remove top reducible polynomials
199        GenSolvablePolynomial<C> a;
200        List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(G.size());
201        while (G.size() > 0) {
202            a = G.remove(0);
203            if (sred.isTopReducible(G, a) || sred.isTopReducible(F, a)) {
204                // drop polynomial 
205                if (debug) {
206                    System.out.println("dropped " + a);
207                    List<GenSolvablePolynomial<C>> ff;
208                    ff = new ArrayList<GenSolvablePolynomial<C>>(G);
209                    ff.addAll(F);
210                    a = sred.leftNormalform(ff, a);
211                    if (!a.isZERO()) {
212                        System.out.println("error, nf(a) " + a);
213                    }
214                }
215            } else {
216                F.add(a);
217            }
218        }
219        G = F;
220        if (G.size() <= 1) {
221            return G;
222        }
223        Collections.reverse(G); // important for lex GB
224        // reduce remaining polynomials
225        int len = G.size();
226        int i = 0;
227        while (i < len) {
228            a = G.remove(0);
229            //System.out.println("doing " + a.length());
230            a = sred.leftNormalform(G, a);
231            a = (GenSolvablePolynomial<C>) engine.basePrimitivePart(a); //a.monic(); not possible
232            a = (GenSolvablePolynomial<C>) a.abs();
233            //a = sred.normalform( F, a );
234            G.add(a); // adds as last
235            i++;
236        }
237        return G;
238    }
239
240
241    /**
242     * Twosided Solvable Groebner base using pairlist class.
243     * @param modv number of module variables.
244     * @param Fp solvable polynomial list.
245     * @return tsGB(Fp) a twosided Groebner base of Fp.
246     */
247    @Override
248    public List<GenSolvablePolynomial<C>> twosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) {
249        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(Fp);
250        G = PolynomialList.<C> castToSolvableList(engine.basePrimitivePart(PolynomialList.<C> castToList(G)));
251        if (G.size() < 1) { // two-sided!
252            return G;
253        }
254        //System.out.println("G = " + G);
255        GenSolvablePolynomialRing<C> ring = G.get(0).ring; // assert != null
256        if (ring.coFac.isField()) { // remove ?
257            throw new IllegalArgumentException("coefficients from a field");
258        }
259        // add also coefficient generators
260        List<GenSolvablePolynomial<C>> X;
261        X = PolynomialList.castToSolvableList(ring.generators(modv)); 
262        logger.info("right multipliers = " + X);
263        List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(G.size() * (1 + X.size()));
264        F.addAll(G);
265        logger.info("right multipy: F = " + F);
266        GenSolvablePolynomial<C> p, x, q;
267        for (int i = 0; i < F.size(); i++) { // F changes
268            p = F.get(i);
269            for (int j = 0; j < X.size(); j++) {
270                x = X.get(j);
271                q = p.multiply(x);
272                logger.info("right multipy: p = " + p + ", x = " + x + ", q = " + q);
273                q = sred.leftNormalform(F, q);
274                if (!q.isZERO()) {
275                    q = (GenSolvablePolynomial<C>) engine.basePrimitivePart(q);
276                    q = (GenSolvablePolynomial<C>) q.abs();
277                    logger.info("right multipy: red(q) = " + q);
278                    F.add(q);
279                }
280            }
281        }
282        G = F;
283        //System.out.println("G generated = " + G);
284        PairList<C> pairlist = strategy.create(modv, ring);
285        pairlist.put(PolynomialList.<C> castToList(G));
286
287        Pair<C> pair;
288        GenSolvablePolynomial<C> pi, pj, S, H;
289        while (pairlist.hasNext()) {
290            pair = pairlist.removeNext();
291            if (pair == null) {
292                continue;
293            }
294
295            pi = (GenSolvablePolynomial<C>) pair.pi;
296            pj = (GenSolvablePolynomial<C>) pair.pj;
297            if (debug) {
298                logger.debug("pi    = " + pi);
299                logger.debug("pj    = " + pj);
300            }
301
302            S = sred.leftSPolynomial(pi, pj);
303            if (S.isZERO()) {
304                pair.setZero();
305                continue;
306            }
307            if (debug) {
308                logger.debug("ht(S) = " + S.leadingExpVector());
309            }
310
311            H = sred.leftNormalform(G, S);
312            if (H.isZERO()) {
313                pair.setZero();
314                continue;
315            }
316            if (debug) {
317                logger.debug("ht(H) = " + H.leadingExpVector());
318            }
319
320            H = (GenSolvablePolynomial<C>) engine.basePrimitivePart(H);
321            H = (GenSolvablePolynomial<C>) H.abs();
322            if (H.isONE()) {
323                G.clear();
324                G.add(H);
325                return G; // since no threads are activated
326            }
327            if (debug) {
328                logger.debug("H = " + H);
329            }
330            if (H.length() > 0) {
331                G.add(H);
332                pairlist.put(H);
333                for (int j = 0; j < X.size(); j++) {
334                    x = X.get(j);
335                    p = H.multiply(x);
336                    p = sred.leftNormalform(G, p);
337                    if (!p.isZERO()) {
338                        p = (GenSolvablePolynomial<C>) engine.basePrimitivePart(p);
339                        p = (GenSolvablePolynomial<C>) p.abs();
340                        if (p.isONE()) {
341                            G.clear();
342                            G.add(p);
343                            return G; // since no threads are activated
344                        }
345                        G.add(p);
346                        pairlist.put(p);
347                    }
348                }
349            }
350        }
351        logger.debug("#sequential list = " + G.size());
352        G = leftMinimalGB(G);
353        logger.info("" + pairlist);
354        return G;
355    }
356
357
358    /**
359     * Solvable Extended Groebner base using critical pair class.
360     * @param modv module variable number.
361     * @param F solvable polynomial list.
362     * @return a container for an extended left Groebner base of F. <b>Note:
363     *         </b> not implemented;
364     */
365    //@SuppressWarnings("unchecked")
366    @Override
367    public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) {
368        throw new UnsupportedOperationException(); // TODO
369    }
370
371}