Source code

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