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