Source code

001/*
002 * $Id: SolvableGroebnerBasePseudoRecSeq.java 5889 2018-07-29 21:00:30Z 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.GenPolynomial;
021import edu.jas.poly.GenPolynomialRing;
022import edu.jas.poly.GenSolvablePolynomial;
023import edu.jas.poly.GenSolvablePolynomialRing;
024import edu.jas.poly.QLRSolvablePolynomialRing;
025import edu.jas.poly.PolyUtil;
026import edu.jas.poly.PolynomialList;
027import edu.jas.structure.GcdRingElem;
028import edu.jas.structure.RingFactory;
029import edu.jas.ufd.GCDFactory;
030import edu.jas.ufd.GreatestCommonDivisorAbstract;
031import edu.jas.ufd.GreatestCommonDivisorFake;
032
033
034/**
035 * Solvable Groebner Base with pseudo reduction sequential algorithm. Implements
036 * coefficient fraction free Groebner bases. Coefficients can for example be
037 * (commutative) multivariate polynomials.
038 * @param <C> coefficient type
039 * @author Heinz Kredel
040 * 
041 * @see edu.jas.application.GBAlgorithmBuilder
042 * @see edu.jas.gbufd.GBFactory
043 */
044
045public class SolvableGroebnerBasePseudoRecSeq<C extends GcdRingElem<C>> extends
046                SolvableGroebnerBaseAbstract<GenPolynomial<C>> {
047
048
049    private static final Logger logger = LogManager.getLogger(SolvableGroebnerBasePseudoRecSeq.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> sredRec;
066
067
068    /**
069     * Pseudo reduction engine.
070     */
071    protected final SolvablePseudoReduction<GenPolynomial<C>> sred;
072
073
074    /**
075     * Coefficient ring factory.
076     */
077    //protected final RingFactory<C> cofac;
078    protected final GenPolynomialRing<C> cofac;
079
080
081    /**
082     * Constructor.
083     * @param rf coefficient ring factory.
084     */
085    public SolvableGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf) {
086        this(rf, new SolvablePseudoReductionSeq<C>());
087    }
088
089
090    /**
091     * Constructor.
092     * @param rf coefficient ring factory.
093     * @param pl pair selection strategy
094     */
095    public SolvableGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, PairList<GenPolynomial<C>> pl) {
096        this(rf, new SolvablePseudoReductionSeq<C>(), pl);
097    }
098
099
100    /**
101     * Constructor.
102     * @param rf coefficient ring factory.
103     * @param red pseudo reduction engine. <b>Note:</b> red must be an instance
104     *            of PseudoReductionSeq.
105     */
106    public SolvableGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, SolvablePseudoReduction<C> red) {
107        this(rf, red, new OrderedPairlist<GenPolynomial<C>>());
108    }
109
110
111    /**
112     * Constructor.
113     * @param rf coefficient ring factory.
114     * @param red pseudo reduction engine. <b>Note:</b> red must be an instance
115     *            of PseudoReductionSeq.
116     * @param pl pair selection strategy
117     */
118    @SuppressWarnings({ "cast", "unchecked" })
119    public SolvableGroebnerBasePseudoRecSeq(RingFactory<GenPolynomial<C>> rf, SolvablePseudoReduction<C> red,
120                    PairList<GenPolynomial<C>> pl) {
121        super((SolvablePseudoReduction<GenPolynomial<C>>) (SolvablePseudoReduction) red, pl);
122        this.sred = (SolvablePseudoReduction<GenPolynomial<C>>) (SolvablePseudoReduction) red;
123        sredRec = red;
124        //this.red = sred;
125        cofac = (GenPolynomialRing<C>) rf;
126        if (!cofac.isCommutative()) {
127            logger.warn("right reduction not correct for " + cofac.toScript());
128            engine = new GreatestCommonDivisorFake<C>();
129            // TODO check that also coeffTable is empty for recursive solvable poly ring
130        } else {
131            //engine = GCDFactory.<C> getImplementation(cofac.coFac);
132            engine = GCDFactory.<C> getProxy(cofac.coFac);
133        }
134    }
135
136
137    /**
138     * Left Groebner base using pairlist class.
139     * @param modv module variable number.
140     * @param F polynomial list.
141     * @return GB(F) a Groebner base of F.
142     */
143    @Override
144    public List<GenSolvablePolynomial<GenPolynomial<C>>> leftGB(int modv,
145                    List<GenSolvablePolynomial<GenPolynomial<C>>> F) {
146        List<GenSolvablePolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(F);
147        G = PolynomialList.<GenPolynomial<C>> castToSolvableList(PolyUtil.<C> monicRec(engine
148                        .recursivePrimitivePart(PolynomialList.<GenPolynomial<C>> castToList(G))));
149        if (G.size() <= 1) {
150            return G;
151        }
152        GenSolvablePolynomialRing<GenPolynomial<C>> ring = G.get(0).ring;
153        if (ring.coFac.isField()) { // remove ? 
154            throw new IllegalArgumentException("coefficients from a field");
155        }
156        PairList<GenPolynomial<C>> pairlist = strategy.create(modv, ring);
157        pairlist.put(PolynomialList.<GenPolynomial<C>> castToList(G));
158        logger.info("leftGB start " + pairlist);
159
160        Pair<GenPolynomial<C>> pair;
161        GenSolvablePolynomial<GenPolynomial<C>> pi, pj, S, H;
162        while (pairlist.hasNext()) {
163            pair = pairlist.removeNext();
164            if (pair == null)
165                continue;
166
167            pi = (GenSolvablePolynomial<GenPolynomial<C>>) pair.pi;
168            pj = (GenSolvablePolynomial<GenPolynomial<C>>) pair.pj;
169            if (debug) {
170                logger.debug("pi    = " + pi);
171                logger.debug("pj    = " + pj);
172            }
173
174            S = sred.leftSPolynomial(pi, pj);
175            if (S.isZERO()) {
176                pair.setZero();
177                continue;
178            }
179            if (debug) {
180                logger.info("ht(S) = " + S.leadingExpVector());
181            }
182
183            H = sredRec.leftNormalformRecursive(G, S);
184            if (H.isZERO()) {
185                pair.setZero();
186                continue;
187            }
188            if (debug) {
189                logger.info("ht(H) = " + H.leadingExpVector() + ", #(H) = " + H.length());
190            }
191            H = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(H);
192            H = PolyUtil.<C> monic(H);
193            if (H.isConstant()) {
194                G.clear();
195                G.add(H);
196                return G; // since no threads are activated
197            }
198            if (debug) {
199                logger.info("lc(pp(H)) = " + H.leadingBaseCoefficient().toScript());
200            }
201            if (H.length() > 0) {
202                G.add(H);
203                pairlist.put(H);
204            }
205        }
206        logger.debug("#sequential list = " + G.size());
207        G = leftMinimalGB(G);
208        logger.info("leftGB end  " + pairlist);
209        return G;
210    }
211
212
213    /**
214     * Minimal ordered Solvable Groebner basis.
215     * @param Gp a Solvable Groebner base.
216     * @return a reduced Solvable Groebner base of Gp.
217     */
218    @Override
219    public List<GenSolvablePolynomial<GenPolynomial<C>>> leftMinimalGB(
220                    List<GenSolvablePolynomial<GenPolynomial<C>>> Gp) {
221        List<GenSolvablePolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Gp);
222        if (G.size() <= 1) {
223            return G;
224        }
225        // remove top reducible polynomials
226        GenSolvablePolynomial<GenPolynomial<C>> a;
227        List<GenSolvablePolynomial<GenPolynomial<C>>> F = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>(
228                        G.size());
229        while (G.size() > 0) {
230            a = G.remove(0);
231            if (sred.isTopReducible(G, a) || sred.isTopReducible(F, a)) {
232                // drop polynomial 
233                if (debug) {
234                    System.out.println("dropped " + a);
235                    List<GenSolvablePolynomial<GenPolynomial<C>>> ff;
236                    ff = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>(G);
237                    ff.addAll(F);
238                    a = sredRec.leftNormalformRecursive(ff, a);
239                    if (!a.isZERO()) {
240                        System.out.println("error, nf(a) " + a);
241                    }
242                }
243            } else {
244                F.add(a);
245            }
246        }
247        G = F;
248        if (G.size() <= 1) {
249            return G;
250        }
251        Collections.reverse(G); // important for lex GB
252        // reduce remaining polynomials
253        int len = G.size();
254        int i = 0;
255        while (i < len) {
256            a = G.remove(0);
257            //System.out.println("doing " + a.length());
258            a = sredRec.leftNormalformRecursive(G, a);
259            a = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(a); //a.monic(); not possible
260            a = PolyUtil.<C> monic(a);
261            G.add(a); // adds as last
262            i++;
263        }
264        return G;
265    }
266
267
268    /**
269     * Twosided Solvable Groebner base using pairlist class.
270     * @param modv number of module variables.
271     * @param Fp solvable polynomial list.
272     * @return tsGB(Fp) a twosided Groebner base of Fp.
273     */
274    @Override
275    public List<GenSolvablePolynomial<GenPolynomial<C>>> twosidedGB(int modv,
276                    List<GenSolvablePolynomial<GenPolynomial<C>>> Fp) {
277        List<GenSolvablePolynomial<GenPolynomial<C>>> G = normalizeZerosOnes(Fp);
278        G = PolynomialList.<GenPolynomial<C>> castToSolvableList(PolyUtil.<C> monicRec(engine
279                        .recursivePrimitivePart(PolynomialList.<GenPolynomial<C>> castToList(G))));
280        if (G.size() < 1) { // two-sided!
281            return G;
282        }
283        //System.out.println("G = " + G);
284        GenSolvablePolynomialRing<GenPolynomial<C>> ring = G.get(0).ring; // assert != null
285        if (ring.coFac.isField()) { // remove ?
286            throw new IllegalArgumentException("coefficients from a field");
287        }
288        // add also coefficient generators
289        List<GenSolvablePolynomial<GenPolynomial<C>>> X;
290        X = PolynomialList.castToSolvableList(ring.generators(modv)); 
291        logger.info("right multipliers = " + X);
292        List<GenSolvablePolynomial<GenPolynomial<C>>> F = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>(
293                        G.size() * (1 + X.size()));
294        F.addAll(G);
295        GenSolvablePolynomial<GenPolynomial<C>> p, x, q;
296        for (int i = 0; i < F.size(); i++) { // F changes
297            p = F.get(i);
298            for (int j = 0; j < X.size(); j++) {
299                x = X.get(j);
300                if (x.isONE()) {
301                    continue;
302                }
303                q = p.multiply(x);
304                q = sredRec.leftNormalformRecursive(F, q);
305                if (!q.isZERO()) {
306                    q = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(q);
307                    q = PolyUtil.<C> monic(q);
308                    F.add(q);
309                }
310            }
311        }
312        G = F;
313        //System.out.println("G generated = " + G);
314        PairList<GenPolynomial<C>> pairlist = strategy.create(modv, ring);
315        pairlist.put(PolynomialList.<GenPolynomial<C>> castToList(G));
316        logger.info("twosidedGB start " + pairlist);
317
318        Pair<GenPolynomial<C>> pair;
319        GenSolvablePolynomial<GenPolynomial<C>> pi, pj, S, H;
320        while (pairlist.hasNext()) {
321            pair = pairlist.removeNext();
322            if (pair == null) {
323                continue;
324            }
325
326            pi = (GenSolvablePolynomial<GenPolynomial<C>>) pair.pi;
327            pj = (GenSolvablePolynomial<GenPolynomial<C>>) pair.pj;
328            if (debug) {
329                logger.debug("pi    = " + pi);
330                logger.debug("pj    = " + pj);
331            }
332
333            S = sred.leftSPolynomial(pi, pj);
334            if (S.isZERO()) {
335                pair.setZero();
336                continue;
337            }
338            if (debug) {
339                logger.info("ht(S) = " + S.leadingExpVector());
340            }
341
342            H = sredRec.leftNormalformRecursive(G, S);
343            if (H.isZERO()) {
344                pair.setZero();
345                continue;
346            }
347            if (debug) {
348                logger.info("ht(H) = " + H.leadingExpVector());
349            }
350
351            H = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(H);
352            H = PolyUtil.<C> monic(H);
353            if (H.isONE()) {
354                G.clear();
355                G.add(H);
356                return G; // since no threads are activated
357            }
358            if (debug) {
359                logger.info("lc(pp(H)) = " + H.leadingBaseCoefficient());
360            }
361            if (H.length() > 0) {
362                G.add(H);
363                pairlist.put(H);
364                for (int j = 0; j < X.size(); j++) {
365                    x = X.get(j);
366                    if (x.isONE()) {
367                        continue;
368                    }
369                    p = H.multiply(x);
370                    p = sredRec.leftNormalformRecursive(G, p);
371                    if (!p.isZERO()) {
372                        p = (GenSolvablePolynomial<GenPolynomial<C>>) engine.recursivePrimitivePart(p);
373                        p = PolyUtil.<C> monic(p);
374                        if (p.isONE()) {
375                            G.clear();
376                            G.add(p);
377                            return G; // since no threads are activated
378                        }
379                        G.add(p);
380                        pairlist.put(p);
381                    }
382                }
383            }
384        }
385        logger.debug("#sequential list = " + G.size());
386        G = leftMinimalGB(G);
387        logger.info("twosidedGB end  " + pairlist);
388        return G;
389    }
390
391
392    /**
393     * Left Groebner base test.
394     * @param modv number of module variables.
395     * @param F solvable polynomial list.
396     * @return true, if F is a left Groebner base, else false.
397     */
398    @Override
399    public boolean isLeftGBsimple(int modv, List<GenSolvablePolynomial<GenPolynomial<C>>> F) {
400        //System.out.println("F to left check = " + F);
401        GenSolvablePolynomial<GenPolynomial<C>> pi, pj, s, h;
402        for (int i = 0; i < F.size(); i++) {
403            pi = F.get(i);
404            for (int j = i + 1; j < F.size(); j++) {
405                pj = F.get(j);
406                if (!red.moduleCriterion(modv, pi, pj)) {
407                    continue;
408                }
409                // if ( ! red.criterion4( pi, pj ) ) { continue; }
410                s = sred.leftSPolynomial(pi, pj);
411                if (s.isZERO()) {
412                    continue;
413                }
414                h = sredRec.leftNormalformRecursive(F, s);
415                if (!h.isZERO()) {
416                    return false;
417                }
418            }
419        }
420        return true;
421    }
422
423
424    /**
425     * Left Groebner base idempotence test.
426     * @param modv module variable number.
427     * @param F solvable polynomial list.
428     * @return true, if F is equal to GB(F), else false.
429     */
430    @Override
431    public boolean isLeftGBidem(int modv, List<GenSolvablePolynomial<GenPolynomial<C>>> F) {
432        if (F == null || F.isEmpty()) {
433            return true;
434        }
435        GenSolvablePolynomialRing<GenPolynomial<C>> pring = F.get(0).ring;
436        List<GenSolvablePolynomial<GenPolynomial<C>>> G = leftGB(modv, F);
437        PolynomialList<GenPolynomial<C>> Fp = new PolynomialList<GenPolynomial<C>>(pring, F);
438        PolynomialList<GenPolynomial<C>> Gp = new PolynomialList<GenPolynomial<C>>(pring, G);
439        return Fp.compareTo(Gp) == 0;
440    }
441
442
443    /**
444     * Twosided Groebner base test.
445     * @param modv number of module variables.
446     * @param Fp solvable polynomial list.
447     * @return true, if Fp is a two-sided Groebner base, else false.
448     */
449    @Override
450    public boolean isTwosidedGB(int modv, List<GenSolvablePolynomial<GenPolynomial<C>>> Fp) {
451        //System.out.println("F to twosided check = " + Fp);
452        if (Fp == null || Fp.size() == 0) { // 0 not 1
453            return true;
454        }
455        GenSolvablePolynomialRing<GenPolynomial<C>> ring = Fp.get(0).ring; // assert != null
456        //List<GenSolvablePolynomial<C>> X = generateUnivar( modv, Fp );
457        List<GenSolvablePolynomial<GenPolynomial<C>>> X, Y;
458        X = PolynomialList.castToSolvableList(ring.generators()); // modv used below
459        Y = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>();
460        for (GenSolvablePolynomial<GenPolynomial<C>> x : X) {
461             if (x.isConstant()) {
462                 Y.add(x);
463             }
464        }
465        X = Y;
466        X.addAll(ring.univariateList(modv));
467        logger.info("right multipliers = " + X);
468        List<GenSolvablePolynomial<GenPolynomial<C>>> F = new ArrayList<GenSolvablePolynomial<GenPolynomial<C>>>(
469                        Fp.size() * (1 + X.size()));
470        F.addAll(Fp);
471        GenSolvablePolynomial<GenPolynomial<C>> p, x, pi, pj, s, h;
472        for (int i = 0; i < Fp.size(); i++) {
473            p = Fp.get(i);
474            for (int j = 0; j < X.size(); j++) {
475                x = X.get(j);
476                if (x.isONE()) {
477                    continue;
478                }
479                p = p.multiply(x);
480                p = sredRec.leftNormalformRecursive(F, p);
481                if (!p.isZERO()) {
482                    return false;
483                    //F.add(p);
484                }
485            }
486        }
487        //System.out.println("F to check = " + F);
488        for (int i = 0; i < F.size(); i++) {
489            pi = F.get(i);
490            for (int j = i + 1; j < F.size(); j++) {
491                pj = F.get(j);
492                if (!red.moduleCriterion(modv, pi, pj)) {
493                    continue;
494                }
495                // if ( ! red.criterion4( pi, pj ) ) { continue; }
496                s = sred.leftSPolynomial(pi, pj);
497                if (s.isZERO()) {
498                    continue;
499                }
500                h = sredRec.leftNormalformRecursive(F, s);
501                if (!h.isZERO()) {
502                    logger.info("is not TwosidedGB: " + h);
503                    return false;
504                }
505            }
506        }
507        return true;
508    }
509
510
511    /**
512     * Solvable Extended Groebner base using critical pair class.
513     * @param modv module variable number.
514     * @param F solvable polynomial list.
515     * @return a container for an extended left Groebner base of F. <b>Note:
516     *         </b> not implemented;
517     */
518    //@SuppressWarnings("unchecked")
519    @Override
520    public SolvableExtendedGB<GenPolynomial<C>> extLeftGB(int modv,
521                    List<GenSolvablePolynomial<GenPolynomial<C>>> F) {
522        throw new UnsupportedOperationException(); // TODO
523    }
524
525}