Source code

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