Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.ListIterator;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.GenSolvablePolynomial;
019import edu.jas.poly.GenSolvablePolynomialRing;
020import edu.jas.poly.QLRSolvablePolynomialRing;
021import edu.jas.poly.PolyUtil;
022import edu.jas.poly.PolynomialList;
023import edu.jas.poly.ModuleList;
024import edu.jas.poly.TermOrder;
025import edu.jas.structure.RingElem;
026import edu.jas.structure.RingFactory;
027import edu.jas.vector.BasicLinAlg;
028
029
030/**
031 * Solvable Groebner Bases abstract class. Implements common left, right and
032 * twosided Groebner bases and left, right and twosided GB tests.
033 * @param <C> coefficient type
034 * @author Heinz Kredel
035 */
036public abstract class SolvableGroebnerBaseAbstract<C extends RingElem<C>> implements SolvableGroebnerBase<C> {
037
038
039    private static final Logger logger = LogManager.getLogger(SolvableGroebnerBaseAbstract.class);
040
041
042    private static final boolean debug = logger.isDebugEnabled();
043
044
045    /**
046     * Solvable reduction engine.
047     */
048    public SolvableReduction<C> sred;
049
050
051    /**
052     * Reduction engine.
053     */
054    public final Reduction<C> red;
055
056
057    /**
058     * Strategy for pair selection.
059     */
060    public final PairList<C> strategy;
061
062
063    /**
064     * Linear algebra engine.
065     */
066    protected final BasicLinAlg<GenPolynomial<C>> blas;
067
068
069    /**
070     * Commutative Groebner bases engine.
071     */
072    public final GroebnerBaseAbstract<C> cbb;
073
074
075    /**
076     * Constructor.
077     */
078    public SolvableGroebnerBaseAbstract() {
079        this(new SolvableReductionSeq<C>());
080    }
081
082
083    /**
084     * Constructor.
085     * @param sred Solvable reduction engine
086     */
087    public SolvableGroebnerBaseAbstract(SolvableReduction<C> sred) {
088        this(sred, new OrderedPairlist<C>());
089    }
090
091
092    /**
093     * Constructor.
094     * @param pl pair selection strategy
095     */
096    public SolvableGroebnerBaseAbstract(PairList<C> pl) {
097        this(new SolvableReductionSeq<C>(), pl);
098    }
099
100
101    /**
102     * Constructor.
103     * @param sred Solvable reduction engine
104     * @param pl pair selection strategy
105     */
106    public SolvableGroebnerBaseAbstract(SolvableReduction<C> sred, PairList<C> pl) {
107        this.red = new ReductionSeq<C>();
108        this.sred = sred;
109        this.strategy = pl;
110        blas = new BasicLinAlg<GenPolynomial<C>>();
111        cbb = new GroebnerBaseSeq<C>();
112    }
113
114
115    /**
116     * Normalize polynomial list.
117     * @param A list of polynomials.
118     * @return list of polynomials with zeros removed and ones/units reduced.
119     */
120    public List<GenSolvablePolynomial<C>> normalizeZerosOnes(List<GenSolvablePolynomial<C>> A) {
121        //List<GenPolynomial<C>> a = PolynomialList.<C> castToList(A);
122        //List<GenPolynomial<C>> n = cbb.normalizeZeroOnes(a);
123        //List<GenSolvablePolynomial<C>> N = PolynomialList.<C> castToSolvableList(n);
124        if (A == null) {
125            return A;
126        }
127        List<GenSolvablePolynomial<C>> N = new ArrayList<GenSolvablePolynomial<C>>(A.size());
128        if (A.isEmpty()) {
129            return N;
130        }
131        for (GenSolvablePolynomial<C> p : A) {
132            if (p == null || p.isZERO()) {
133                continue;
134            }
135            if (p.isUnit()) {
136                N.clear();
137                N.add(p.ring.getONE());
138                return N;
139            }
140            N.add((GenSolvablePolynomial<C>) p.abs());
141        }
142        //N.trimToSize();
143        return N;
144    }
145
146
147    /**
148     * Left Groebner base test.
149     * @param F solvable polynomial list.
150     * @return true, if F is a left Groebner base, else false.
151     */
152    public boolean isLeftGB(List<GenSolvablePolynomial<C>> F) {
153        return isLeftGB(0, F, true);
154    }
155
156
157    /**
158     * Left Groebner base test.
159     * @param F solvable polynomial list.
160     * @param b true for simple test, false for GB test.
161     * @return true, if F is a Groebner base, else false.
162     */
163    public boolean isLeftGB(List<GenSolvablePolynomial<C>> F, boolean b) {
164        return isLeftGB(0, F, b);
165    }
166
167
168    /**
169     * Left Groebner base test.
170     * @param modv module variable number.
171     * @param F solvable polynomial list.
172     * @return true, if F is a Groebner base, else false.
173     */
174    public boolean isLeftGB(int modv, List<GenSolvablePolynomial<C>> F) {
175        return isLeftGB(modv, F, true);
176    }
177
178
179    /**
180     * Left Groebner base test.
181     * @param modv module variable number.
182     * @param F solvable polynomial list.
183     * @param b true for simple test, false for GB test.
184     * @return true, if F is a Groebner base, else false.
185     */
186    public boolean isLeftGB(int modv, List<GenSolvablePolynomial<C>> F, boolean b) {
187        if (b) {
188            return isLeftGBsimple(modv, F);
189        }
190        return isLeftGBidem(modv, F);
191    }
192
193
194    /**
195     * Left Groebner base test.
196     * @param modv number of module variables.
197     * @param F solvable polynomial list.
198     * @return true, if F is a left Groebner base, else false.
199     */
200    public boolean isLeftGBsimple(int modv, List<GenSolvablePolynomial<C>> F) {
201        GenSolvablePolynomial<C> pi, pj, s, h;
202        for (int i = 0; i < F.size(); i++) {
203            pi = F.get(i);
204            for (int j = i + 1; j < F.size(); j++) {
205                pj = F.get(j);
206                if (!red.moduleCriterion(modv, pi, pj)) {
207                    continue;
208                }
209                // if ( ! red.criterion4( pi, pj ) ) { continue; }
210                s = sred.leftSPolynomial(pi, pj);
211                if (s.isZERO()) {
212                    continue;
213                }
214                h = sred.leftNormalform(F, s);
215                if (!h.isZERO()) {
216                    logger.info("no left GB: pi = {}, pj = {}", pi, pj);
217                    logger.info("s  = {}, h = {}", s, h);
218                    return false;
219                }
220            }
221        }
222        return true;
223    }
224
225
226    /**
227     * Left Groebner base idempotence test.
228     * @param modv module variable number.
229     * @param F solvable polynomial list.
230     * @return true, if F is equal to GB(F), else false.
231     */
232    public boolean isLeftGBidem(int modv, List<GenSolvablePolynomial<C>> F) {
233        if (F == null || F.isEmpty()) {
234            return true;
235        }
236        GenSolvablePolynomialRing<C> pring = F.get(0).ring;
237        List<GenSolvablePolynomial<C>> G = leftGB(modv, F);
238        PolynomialList<C> Fp = new PolynomialList<C>(pring, F);
239        PolynomialList<C> Gp = new PolynomialList<C>(pring, G);
240        return Fp.compareTo(Gp) == 0;
241    }
242
243
244    /**
245     * Twosided Groebner base test.
246     * @param Fp solvable polynomial list.
247     * @return true, if Fp is a two-sided Groebner base, else false.
248     */
249    public boolean isTwosidedGB(List<GenSolvablePolynomial<C>> Fp) {
250        return isTwosidedGB(0, Fp);
251    }
252
253
254    /**
255     * Twosided Groebner base test.
256     * @param modv number of module variables.
257     * @param Fp solvable polynomial list.
258     * @return true, if Fp is a two-sided Groebner base, else false.
259     */
260    public boolean isTwosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) {
261        if (Fp == null || Fp.size() == 0) { // 0 not 1
262            return true;
263        }
264        if (Fp.size() == 1 && Fp.get(0).isONE()) { 
265            return true;
266        }
267        GenSolvablePolynomialRing<C> ring = Fp.get(0).ring; // assert != null
268        // add also coefficient generators
269        List<GenSolvablePolynomial<C>> X;
270        X = PolynomialList.castToSolvableList(ring.generators(modv)); 
271        logger.info("right multipliers = {}", X);
272        List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(Fp.size() * (1 + X.size()));
273        F.addAll(Fp);
274        GenSolvablePolynomial<C> p, q, x, pi, pj, s, h;
275        for (int i = 0; i < Fp.size(); i++) {
276            p = Fp.get(i);
277            for (int j = 0; j < X.size(); j++) {
278                x = X.get(j);
279                if (x.isONE()) {
280                    continue;
281                }
282                q = p.multiply(x);
283                q = sred.leftNormalform(F, q);
284                if (!q.isZERO()) {
285                    //System.out.println("is: q generated = " + q + ", p = " + p + ", x = " + x);
286                    return false;
287                    //F.add(q);
288                }
289            }
290        }
291        //System.out.println("F to check = " + F);
292        for (int i = 0; i < F.size(); i++) {
293            pi = F.get(i);
294            for (int j = i + 1; j < F.size(); j++) {
295                pj = F.get(j);
296                if (!red.moduleCriterion(modv, pi, pj)) {
297                    continue;
298                }
299                // if ( ! red.criterion4( pi, pj ) ) { continue; }
300                s = sred.leftSPolynomial(pi, pj);
301                if (s.isZERO()) {
302                    continue;
303                }
304                h = sred.leftNormalform(F, s);
305                if (!h.isZERO()) {
306                    logger.info("is not TwosidedGB: {}", h);
307                    //System.out.println("is: h = " + h + ", s = " + s);
308                    return false;
309                }
310            }
311        }
312        return true;
313    }
314
315
316    /**
317     * Twosided Groebner base idempotence test.
318     * @param F solvable polynomial list.
319     * @return true, if F is equal to GB(F), else false.
320     */
321    public boolean isTwosidedGBidem(List<GenSolvablePolynomial<C>> F) {
322        return isTwosidedGBidem(0, F);
323    }
324
325
326    /**
327     * Twosided Groebner base idempotence test.
328     * @param modv module variable number.
329     * @param F solvable polynomial list.
330     * @return true, if F is equal to GB(F), else false.
331     */
332    public boolean isTwosidedGBidem(int modv, List<GenSolvablePolynomial<C>> F) {
333        if (F == null || F.isEmpty()) {
334            return true;
335        }
336        GenSolvablePolynomialRing<C> pring = F.get(0).ring;
337        List<GenSolvablePolynomial<C>> G = twosidedGB(modv, F);
338        PolynomialList<C> Fp = new PolynomialList<C>(pring, F);
339        PolynomialList<C> Gp = new PolynomialList<C>(pring, G);
340        return Fp.compareTo(Gp) == 0;
341    }
342
343
344    /**
345     * Right Groebner base test.
346     * @param F solvable polynomial list.
347     * @return true, if F is a right Groebner base, else false.
348     */
349    public boolean isRightGB(List<GenSolvablePolynomial<C>> F) {
350        return isRightGB(0, F);
351    }
352
353
354    /**
355     * Right Groebner base test.
356     * @param modv number of module variables.
357     * @param F solvable polynomial list.
358     * @return true, if F is a right Groebner base, else false.
359     */
360    public boolean isRightGB(int modv, List<GenSolvablePolynomial<C>> F) {
361        GenSolvablePolynomial<C> pi, pj, s, h;
362        for (int i = 0; i < F.size(); i++) {
363            pi = F.get(i);
364            //System.out.println("pi right = " + pi);
365            for (int j = i + 1; j < F.size(); j++) {
366                pj = F.get(j);
367                //System.out.println("pj right = " + pj);
368                if (!red.moduleCriterion(modv, pi, pj)) {
369                    continue;
370                }
371                // if ( ! red.criterion4( pi, pj ) ) { continue; }
372                s = sred.rightSPolynomial(pi, pj);
373                if (s.isZERO()) {
374                    continue;
375                }
376                //System.out.println("s right = " + s);
377                h = sred.rightNormalform(F, s);
378                if (!h.isZERO()) {
379                    logger.info("isRightGB non zero h = {} :: {}, rspol = {}", h, h.ring.toScript(), s);
380                    logger.info("p{} = {}, p{} = {}", i, pi, j, pj);
381                    return false;
382                }
383            }
384        }
385        return true;
386    }
387
388
389    /**
390     * Right Groebner base idempotence test.
391     * @param F solvable polynomial list.
392     * @return true, if F is equal to GB(F), else false.
393     */
394    public boolean isRightGBidem(List<GenSolvablePolynomial<C>> F) {
395        return isRightGBidem(0, F);
396    }
397
398
399    /**
400     * Right Groebner base idempotence test.
401     * @param modv module variable number.
402     * @param F solvable polynomial list.
403     * @return true, if F is equal to GB(F), else false.
404     */
405    public boolean isRightGBidem(int modv, List<GenSolvablePolynomial<C>> F) {
406        if (F == null || F.isEmpty()) {
407            return true;
408        }
409        GenSolvablePolynomialRing<C> pring = F.get(0).ring;
410        List<GenSolvablePolynomial<C>> G = rightGB(modv, F);
411        PolynomialList<C> Fp = new PolynomialList<C>(pring, F);
412        PolynomialList<C> Gp = new PolynomialList<C>(pring, G);
413        return Fp.compareTo(Gp) == 0;
414    }
415
416
417    /**
418     * Left Groebner base using pairlist class.
419     * @param F solvable polynomial list.
420     * @return leftGB(F) a left Groebner base of F.
421     */
422    public List<GenSolvablePolynomial<C>> leftGB(List<GenSolvablePolynomial<C>> F) {
423        return leftGB(0, F);
424    }
425
426
427    /**
428     * Solvable Extended Groebner base using critical pair class.
429     * @param F solvable polynomial list.
430     * @return a container for an extended left Groebner base of F.
431     */
432    public SolvableExtendedGB<C> extLeftGB(List<GenSolvablePolynomial<C>> F) {
433        return extLeftGB(0, F);
434    }
435
436
437    /**
438     * Solvable Extended Groebner base using critical pair class.
439     * @param modv module variable number.
440     * @param F polynomial list.
441     * @return a container for an extended left Groebner base G of F together
442     *         with back-and-forth transformations.
443     */
444    public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) {
445        throw new UnsupportedOperationException("extLeftGB not implemented in "
446                        + this.getClass().getSimpleName());
447    }
448
449
450    /**
451     * Left minimal ordered groebner basis.
452     * @param Gp a left Groebner base.
453     * @return leftGBmi(F) a minimal left Groebner base of Gp.
454     */
455    public List<GenSolvablePolynomial<C>> leftMinimalGB(List<GenSolvablePolynomial<C>> Gp) {
456        ArrayList<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>();
457        ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator();
458        for (GenSolvablePolynomial<C> a : Gp) {
459            // a = (SolvablePolynomial) it.next();
460            if (a.length() != 0) { // always true
461                // already monic a = a.monic();
462                G.add(a);
463            }
464        }
465        if (G.size() <= 1) {
466            return G;
467        }
468
469        ExpVector e;
470        ExpVector f;
471        GenSolvablePolynomial<C> a, p;
472        ArrayList<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>();
473        boolean mt;
474
475        while (G.size() > 0) {
476            a = G.remove(0);
477            e = a.leadingExpVector();
478
479            it = G.listIterator();
480            mt = false;
481            while (it.hasNext() && !mt) {
482                p = it.next();
483                f = p.leadingExpVector();
484                mt = e.multipleOf(f);
485            }
486            it = F.listIterator();
487            while (it.hasNext() && !mt) {
488                p = it.next();
489                f = p.leadingExpVector();
490                mt = e.multipleOf(f);
491            }
492            if (!mt) {
493                F.add(a);
494            } else {
495                // System.out.println("dropped " + a.length());
496            }
497        }
498        G = F;
499        if (G.size() <= 1) {
500            return G;
501        }
502
503        F = new ArrayList<GenSolvablePolynomial<C>>();
504        while (G.size() > 0) {
505            a = G.remove(0);
506            // System.out.println("doing " + a.length());
507            a = sred.leftNormalform(G, a);
508            a = sred.leftNormalform(F, a);
509            F.add(a);
510        }
511        return F;
512    }
513
514
515    /**
516     * Right minimal ordered groebner basis.
517     * @param Gp a right Groebner base.
518     * @return rightGBmi(F) a minimal right Groebner base of Gp.
519     */
520    public List<GenSolvablePolynomial<C>> rightMinimalGB(List<GenSolvablePolynomial<C>> Gp) {
521        ArrayList<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>();
522        ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator();
523        for (GenSolvablePolynomial<C> a : Gp) {
524            if (a.length() != 0) { // always true
525                G.add(a);
526            }
527        }
528        if (G.size() <= 1) {
529            return G;
530        }
531
532        ExpVector e;
533        ExpVector f;
534        GenSolvablePolynomial<C> a, p;
535        ArrayList<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>();
536        boolean mt;
537
538        while (G.size() > 0) {
539            a = G.remove(0);
540            e = a.leadingExpVector();
541
542            it = G.listIterator();
543            mt = false;
544            while (it.hasNext() && !mt) {
545                p = it.next();
546                f = p.leadingExpVector();
547                mt = e.multipleOf(f);
548            }
549            it = F.listIterator();
550            while (it.hasNext() && !mt) {
551                p = it.next();
552                f = p.leadingExpVector();
553                mt = e.multipleOf(f);
554            }
555            if (!mt) {
556                F.add(a);
557            } else {
558                // System.out.println("dropped " + a.length());
559            }
560        }
561        G = F;
562        if (G.size() <= 1) {
563            return G;
564        }
565
566        F = new ArrayList<GenSolvablePolynomial<C>>();
567        while (G.size() > 0) {
568            a = G.remove(0);
569            // System.out.println("doing " + a.length());
570            a = sred.rightNormalform(G, a);
571            a = sred.rightNormalform(F, a);
572            F.add(a);
573        }
574        return F;
575    }
576
577
578    /**
579     * Twosided Groebner base using pairlist class.
580     * @param Fp solvable polynomial list.
581     * @return tsGB(Fp) a twosided Groebner base of Fp.
582     */
583    public List<GenSolvablePolynomial<C>> twosidedGB(List<GenSolvablePolynomial<C>> Fp) {
584        return twosidedGB(0, Fp);
585    }
586
587
588    /**
589     * Right Groebner base using opposite ring left GB.
590     * @param F solvable polynomial list.
591     * @return rightGB(F) a right Groebner base of F.
592     */
593    public List<GenSolvablePolynomial<C>> rightGB(List<GenSolvablePolynomial<C>> F) {
594        return rightGB(0, F);
595    }
596
597
598    /**
599     * Right Groebner base using opposite ring left GB.
600     * @param modv number of module variables.
601     * @param F solvable polynomial list.
602     * @return rightGB(F) a right Groebner base of F.
603     */
604    @SuppressWarnings("unchecked")
605    public List<GenSolvablePolynomial<C>> rightGB(int modv, List<GenSolvablePolynomial<C>> F) {
606        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F);
607        if (G.size() <= 1) {
608            return G;
609        }
610        GenSolvablePolynomialRing<C> ring = G.get(0).ring; // assert != null
611        GenSolvablePolynomialRing<C> rring = ring.reverse(true); //true
612        //System.out.println("rightGB: ring = " + ring.toScript() + ", reversed ring = " + rring.toScript());
613        GenSolvablePolynomial<C> q;
614        List<GenSolvablePolynomial<C>> rF;
615        rF = new ArrayList<GenSolvablePolynomial<C>>(F.size());
616        for (GenSolvablePolynomial<C> p : F) {
617            if (p != null) {
618                q = (GenSolvablePolynomial<C>) p.reverse(rring);
619                rF.add(q);
620            }
621        }
622        if (logger.isInfoEnabled()) {
623            PolynomialList<C> pl = new PolynomialList<C>(rring, rF);
624            logger.info("reversed problem = {}", pl.toScript());
625        }
626        List<GenSolvablePolynomial<C>> rG = leftGB(modv, rF);
627        if (debug) {
628            //PolynomialList<C> pl = new PolynomialList<C>(rring,rG);
629            //logger.info("reversed GB = {}", pl);
630            long t = System.currentTimeMillis();
631            boolean isit = isLeftGB(rG);
632            t = System.currentTimeMillis() - t;
633            logger.info("is left GB = {}, in {} milliseconds", isit, t);
634        }
635        //System.out.println("reversed left GB = " + rG);
636        ring = rring.reverse(true); // true
637        G = new ArrayList<GenSolvablePolynomial<C>>(rG.size());
638        for (GenSolvablePolynomial<C> p : rG) {
639            if (p != null) {
640                q = (GenSolvablePolynomial<C>) p.reverse(ring);
641                G.add(q);
642            }
643        }
644        if (debug) {
645            //PolynomialList<C> pl = new PolynomialList<C>(ring,G);
646            //logger.info("GB = {}", pl);
647            long t = System.currentTimeMillis();
648            boolean isit = isRightGB(G);
649            t = System.currentTimeMillis() - t;
650            logger.info("is right GB = {}, in {} milliseconds", isit, t);
651        }
652        return G;
653    }
654
655
656    /**
657     * Solvable Extended Groebner base using critical pair class.
658     * @param F solvable polynomial list.
659     * @return a container for an extended right Groebner base of F.
660     */
661    public SolvableExtendedGB<C> extRightGB(List<GenSolvablePolynomial<C>> F) {
662        return extRightGB(0, F);
663    }
664
665
666    /**
667     * Solvable Extended Groebner base using critical pair class.
668     * @param modv module variable number.
669     * @param F polynomial list.
670     * @return a container for an extended right Groebner base G of F together
671     *         with back-and-forth transformations.
672     */
673    public SolvableExtendedGB<C> extRightGB(int modv, List<GenSolvablePolynomial<C>> F) {
674        throw new UnsupportedOperationException("extRightGB not implemented in "
675                        + this.getClass().getSimpleName());
676    }
677
678
679    /**
680     * Module left Groebner base test.
681     * @param M a module basis.
682     * @return true, if M is a left Groebner base, else false.
683     */
684    public boolean isLeftGB(ModuleList<C> M) {
685        return isLeftGB(M,false);
686    }
687
688
689    /**
690     * Module left Groebner base test.
691     * @param M a module basis.
692     * @param top true for TOP term order, false for POT term order.
693     * @return true, if M is a left Groebner base, else false.
694     */
695    public boolean isLeftGB(ModuleList<C> M, boolean top) {
696        if (M == null || M.list == null) {
697            return true;
698        }
699        if (M.rows == 0 || M.cols == 0) {
700            return true;
701        }
702        int modv = M.cols; // > 0  
703        PolynomialList<C> F = M.getPolynomialList(top);
704        return isLeftGB(modv, F.castToSolvableList());
705    }
706
707
708    /**
709     * Left Groebner base using pairlist class.
710     * @param M a module basis.
711     * @return leftGB(M) a left Groebner base for M.
712     */
713    public ModuleList<C> leftGB(ModuleList<C> M) {
714        return leftGB(M,false);
715    }
716
717
718    /**
719     * Left Groebner base using pairlist class.
720     * @param M a module basis.
721     * @param top true for TOP term order, false for POT term order.
722     * @return leftGB(M) a left Groebner base for M.
723     */
724    @SuppressWarnings("unchecked")
725    public ModuleList<C> leftGB(ModuleList<C> M, boolean top) {
726        ModuleList<C> N = M;
727        if (M == null || M.list == null) {
728            return N;
729        }
730        if (M.rows == 0 || M.cols == 0) {
731            return N;
732        }
733        PolynomialList<C> F = M.getPolynomialList(top);
734        if (debug) {
735            logger.info("F left +++++++++++++++++++ \n{}", F);
736        }
737        GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) F.ring;
738        int modv = M.cols;
739        List<GenSolvablePolynomial<C>> G = leftGB(modv, F.castToSolvableList());
740        F = new PolynomialList<C>(sring, G);
741        if (debug) {
742            logger.info("G left +++++++++++++++++++ \n{}", F);
743        }
744        N = F.getModuleList(modv);
745        return N;
746    }
747
748
749    /**
750     * Module twosided Groebner base test.
751     * @param M a module basis.
752     * @return true, if M is a twosided Groebner base, else false.
753     */
754    public boolean isTwosidedGB(ModuleList<C> M) {
755        return isTwosidedGB(M,false);
756    }
757
758
759    /**
760     * Module twosided Groebner base test.
761     * @param M a module basis.
762     * @param top true for TOP term order, false for POT term order.
763     * @return true, if M is a twosided Groebner base, else false.
764     */
765    public boolean isTwosidedGB(ModuleList<C> M, boolean top) {
766        if (M == null || M.list == null) {
767            return true;
768        }
769        if (M.rows == 0 || M.cols == 0) {
770            return true;
771        }
772        PolynomialList<C> F = M.getPolynomialList(top);
773        int modv = M.cols; // > 0  
774        return isTwosidedGB(modv, F.castToSolvableList());
775    }
776
777
778    /**
779     * Twosided Groebner base using pairlist class.
780     * @param M a module basis.
781     * @return twosidedGB(M) a twosided Groebner base for M.
782     */
783    public ModuleList<C> twosidedGB(ModuleList<C> M) {
784        return twosidedGB(M,false);
785    }
786
787
788    /**
789     * Twosided Groebner base using pairlist class.
790     * @param M a module basis.
791     * @param top true for TOP term order, false for POT term order.
792     * @return tsGB(M) a twosided Groebner base for M.
793     */
794    @SuppressWarnings("unchecked")
795    public ModuleList<C> twosidedGB(ModuleList<C> M, boolean top) {
796        ModuleList<C> N = M;
797        if (M == null || M.list == null) {
798            return N;
799        }
800        if (M.rows == 0 || M.cols == 0) {
801            return N;
802        }
803        PolynomialList<C> F = M.getPolynomialList(top);
804        GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) F.ring;
805        int modv = M.cols;
806        List<GenSolvablePolynomial<C>> G = twosidedGB(modv, F.castToSolvableList());
807        F = new PolynomialList<C>(sring, G);
808        N = F.getModuleList(modv);
809        return N;
810    }
811
812
813    /**
814     * Module right Groebner base test.
815     * @param M a module basis.
816     * @return true, if M is a right Groebner base, else false.
817     */
818    public boolean isRightGB(ModuleList<C> M) {
819        return isRightGB(M,false);
820    }
821
822
823    /**
824     * Module right Groebner base test.
825     * @param M a module basis.
826     * @param top true for TOP term order, false for POT term order.
827     * @return true, if M is a right Groebner base, else false.
828     */
829    public boolean isRightGB(ModuleList<C> M, boolean top) {
830        if (M == null || M.list == null) {
831            return true;
832        }
833        if (M.rows == 0 || M.cols == 0) {
834            return true;
835        }
836        if (top) {
837            logger.warn("computation of rightGB with TOP not possible");
838        }
839        int modv = M.cols; // > 0  
840        PolynomialList<C> F = M.getPolynomialList(top);
841        //System.out.println("F test = " + F);
842        return isRightGB(modv, F.castToSolvableList());
843    }
844
845
846    /**
847     * Right Groebner base using pairlist class.
848     * @param M a module basis.
849     * @return rightGB(M) a right Groebner base for M.
850     */
851    @SuppressWarnings("unchecked")
852    public ModuleList<C> rightGB(ModuleList<C> M) { // boolean top
853        ModuleList<C> N = M;
854        if (M == null || M.list == null) {
855            return N;
856        }
857        if (M.rows == 0 || M.cols == 0) {
858            return N;
859        }
860        if (debug) {
861            logger.info("M ====================== \n{}", M);
862        }
863        TermOrder to = M.ring.tord;
864        if (to.getSplit() <= M.ring.nvar) {
865            throw new IllegalArgumentException("extended TermOrders not supported for rightGBs: " + to);
866        }
867        List<List<GenSolvablePolynomial<C>>> mlist = M.castToSolvableList();
868        GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) M.ring;
869        GenSolvablePolynomialRing<C> rring = sring.reverse(true); //true
870        sring = rring.reverse(true); // true
871
872        List<List<GenSolvablePolynomial<C>>> nlist = new ArrayList<List<GenSolvablePolynomial<C>>>(M.rows);
873        for (List<GenSolvablePolynomial<C>> row : mlist) {
874            List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row.size());
875            for (GenSolvablePolynomial<C> elem : row) {
876                GenSolvablePolynomial<C> nelem = (GenSolvablePolynomial<C>) elem.reverse(rring);
877                nrow.add(nelem);
878            }
879            nlist.add(nrow);
880        }
881        ModuleList<C> rM = new ModuleList<C>(rring, nlist);
882        if (debug) {
883            logger.info("rM -------------------- \n{}", rM);
884        }
885        ModuleList<C> rMg = leftGB(rM); // top ?
886        if (debug) {
887            logger.info("rMg -------------------- \n{}", rMg);
888            logger.info("isLeftGB(rMg) ---------- {}", isLeftGB(rMg));
889        }
890        mlist = rMg.castToSolvableList();
891        nlist = new ArrayList<List<GenSolvablePolynomial<C>>>(rMg.rows);
892        for (List<GenSolvablePolynomial<C>> row : mlist) {
893            List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row.size());
894            for (GenSolvablePolynomial<C> elem : row) {
895                GenSolvablePolynomial<C> nelem = (GenSolvablePolynomial<C>) elem.reverse(sring);
896                nrow.add(nelem);
897            }
898            nlist.add(nrow);
899        }
900        ModuleList<C> Mg = new ModuleList<C>(sring, nlist);
901        if (debug) {
902            logger.info("Mg -------------------- \n{}", Mg);
903            logger.info("isRightGB(Mg) --------- {}", isRightGB(Mg));
904        }
905        return Mg;
906    }
907
908
909    /**
910     * Test if left reduction matrix.
911     * @param exgb an SolvableExtendedGB container.
912     * @return true, if exgb contains a left reduction matrix, else false.
913     */
914    public boolean isLeftReductionMatrix(SolvableExtendedGB<C> exgb) {
915        if (exgb == null) {
916            return true;
917        }
918        return isLeftReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F);
919    }
920
921
922    /**
923     * Test if left reduction matrix.
924     * @param F a solvable polynomial list.
925     * @param G a left Groebner base.
926     * @param Mf a possible left reduction matrix.
927     * @param Mg a possible left reduction matrix.
928     * @return true, if Mg and Mf are left reduction matrices, else false.
929     */
930    public boolean isLeftReductionMatrix(List<GenSolvablePolynomial<C>> F, List<GenSolvablePolynomial<C>> G,
931                    List<List<GenSolvablePolynomial<C>>> Mf, List<List<GenSolvablePolynomial<C>>> Mg) {
932        // no more check G and Mg: G * Mg[i] == 0
933        // check F and Mg: F * Mg[i] == G[i]
934        int k = 0;
935        for (List<GenSolvablePolynomial<C>> row : Mg) {
936            boolean t = sred.isLeftReductionNF(row, F, G.get(k), null);
937            if (!t) {
938                System.out.println("row = " + row);
939                System.out.println("F   = " + F);
940                System.out.println("G[" + k + "] = " + G.get(k));
941                logger.info("F isLeftReductionMatrix s, k = {}, {}", F.size(), k);
942                System.out.println("F*row == G[k]: " + sred.isLeftReductionNF(F, row, G.get(k), null));
943                return false;
944            }
945            k++;
946        }
947        // check G and Mf: G * Mf[i] == F[i]
948        k = 0;
949        for (List<GenSolvablePolynomial<C>> row : Mf) {
950            boolean t = sred.isLeftReductionNF(row, G, F.get(k), null);
951            if (!t) {
952                System.out.println("row = " + row);
953                System.out.println("G   = " + G);
954                System.out.println("F[" + k + "] = " + F.get(k));
955                logger.info("G isLeftReductionMatrix s, k = {}, {}", G.size(), k);
956                return false;
957            }
958            k++;
959        }
960        return true;
961    }
962
963
964    /**
965     * Ideal common zero test.
966     * @return -1, 0 or 1 if dimension(this) &eq; -1, 0 or &ge; 1.
967     */
968    public int commonZeroTest(List<GenSolvablePolynomial<C>> A) {
969        List<GenPolynomial<C>> cA = PolynomialList.<C> castToList(A);
970        return cbb.commonZeroTest(cA);
971    }
972
973
974    /**
975     * Univariate head term degrees.
976     * @param A list of solvable polynomials.
977     * @return a list of the degrees of univariate head terms.
978     */
979    public List<Long> univariateDegrees(List<GenSolvablePolynomial<C>> A) {
980        List<GenPolynomial<C>> cA = PolynomialList.<C> castToList(A);
981        return cbb.univariateDegrees(cA);
982    }
983
984
985    /**
986     * Construct univariate solvable polynomial of minimal degree in variable i
987     * of a zero dimensional ideal(G).
988     * @param i variable index.
989     * @param G list of solvable polynomials, a monic reduced left Gr&ouml;bner
990     *            base of a zero dimensional ideal.
991     * @return univariate solvable polynomial of minimal degree in variable i in
992     *         ideal_left(G)
993     */
994    public GenSolvablePolynomial<C> constructUnivariate(int i, List<GenSolvablePolynomial<C>> G) {
995        if (G == null || G.size() == 0) {
996            throw new IllegalArgumentException("G may not be null or empty");
997        }
998        List<Long> ud = univariateDegrees(G);
999        if (ud.size() <= i) {
1000            //logger.info("univ pol, ud = {}", ud);
1001            throw new IllegalArgumentException("ideal(G) not zero dimensional " + ud);
1002        }
1003        int ll = 0;
1004        Long di = ud.get(i);
1005        if (di != null) {
1006            ll = (int) (long) di;
1007        } else {
1008            throw new IllegalArgumentException("ideal(G) not zero dimensional");
1009        }
1010        long vsdim = 1;
1011        for (Long d : ud) {
1012            if (d != null) {
1013                vsdim *= d;
1014            }
1015        }
1016        logger.info("univariate construction, deg = {}, vsdim = {}", ll, vsdim);
1017        GenSolvablePolynomialRing<C> pfac = G.get(0).ring;
1018        RingFactory<C> cfac = pfac.coFac;
1019
1020        GenPolynomialRing<C> cpfac = new GenPolynomialRing<C>(cfac, ll, new TermOrder(TermOrder.INVLEX));
1021        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = new GenSolvablePolynomialRing<GenPolynomial<C>>(
1022                        cpfac, pfac); // relations
1023        GenSolvablePolynomial<GenPolynomial<C>> P = rfac.getZERO();
1024        for (int k = 0; k < ll; k++) {
1025            GenSolvablePolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, k);
1026            GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - k);
1027            Pp = Pp.multiply(cp);
1028            P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(Pp);
1029        }
1030        if (debug) {
1031            logger.info("univariate construction, P = {}", P);
1032            logger.info("univariate construction, deg_*(G) = {}", ud);
1033            //throw new RuntimeException("check");
1034        }
1035        GroebnerBaseAbstract<C> bbc = new GroebnerBaseSeq<C>();
1036        GenSolvablePolynomial<C> X;
1037        GenSolvablePolynomial<C> XP;
1038        // solve system of linear equations for the coefficients of the univariate polynomial
1039        List<GenPolynomial<C>> ls;
1040        int z = -1;
1041        do {
1042            //System.out.println("ll  = " + ll);
1043            GenSolvablePolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, ll);
1044            GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - ll);
1045            Pp = Pp.multiply(cp);
1046            P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(Pp);
1047            X = pfac.univariate(i, ll);
1048            XP = sred.leftNormalform(G, X);
1049            //System.out.println("XP = " + XP);
1050            GenSolvablePolynomial<GenPolynomial<C>> XPp = PolyUtil.<C> toRecursive(rfac, XP);
1051            GenSolvablePolynomial<GenPolynomial<C>> XPs = (GenSolvablePolynomial<GenPolynomial<C>>) XPp
1052                            .sum(P);
1053            ls = new ArrayList<GenPolynomial<C>>(XPs.getMap().values());
1054            //System.out.println("ls,1 = " + ls);
1055            ls = red.irreducibleSet(ls);
1056            z = bbc.commonZeroTest(ls);
1057            if (z != 0) {
1058                ll++;
1059                if (ll > vsdim) {
1060                    logger.info("univariate construction, P = {}", P);
1061                    logger.info("univariate construction, nf(P) = {}", XP);
1062                    logger.info("G = {}", G);
1063                    throw new ArithmeticException(
1064                                    "univariate polynomial degree greater than vector space dimansion");
1065                }
1066                cpfac = cpfac.extend(1);
1067                rfac = new GenSolvablePolynomialRing<GenPolynomial<C>>(cpfac, pfac);
1068                P = PolyUtil.<C> extendCoefficients(rfac, P, 0, 0L);
1069                XPp = PolyUtil.<C> extendCoefficients(rfac, XPp, 0, 1L);
1070                P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(XPp);
1071            }
1072        } while (z != 0); // && ll <= 5 && !XP.isZERO()
1073        // construct result polynomial
1074        String var = pfac.getVars()[pfac.nvar - 1 - i];
1075        GenSolvablePolynomialRing<C> ufac = new GenSolvablePolynomialRing<C>(cfac, 1, new TermOrder(
1076                        TermOrder.INVLEX), new String[] { var });
1077        GenSolvablePolynomial<C> pol = ufac.univariate(0, ll);
1078        for (GenPolynomial<C> pc : ls) {
1079            ExpVector e = pc.leadingExpVector();
1080            if (e == null) {
1081                continue;
1082            }
1083            int[] v = e.dependencyOnVariables();
1084            if (v == null || v.length == 0) {
1085                continue;
1086            }
1087            int vi = v[0];
1088            C tc = pc.trailingBaseCoefficient();
1089            tc = tc.negate();
1090            GenSolvablePolynomial<C> pi = ufac.univariate(0, ll - 1 - vi);
1091            pi = pi.multiply(tc);
1092            pol = (GenSolvablePolynomial<C>) pol.sum(pi);
1093        }
1094        if (logger.isInfoEnabled()) {
1095            logger.info("univariate construction, pol = {}", pol);
1096        }
1097        return pol;
1098    }
1099
1100
1101    /**
1102     * Construct univariate solvable polynomials of minimal degree in all
1103     * variables in zero dimensional left ideal(G).
1104     * @return list of univariate polynomial of minimal degree in each variable
1105     *         in ideal_left(G)
1106     */
1107    public List<GenSolvablePolynomial<C>> constructUnivariate(List<GenSolvablePolynomial<C>> G) {
1108        List<GenSolvablePolynomial<C>> univs = new ArrayList<GenSolvablePolynomial<C>>();
1109        if (G == null || G.isEmpty()) {
1110            return univs;
1111        }
1112        for (int i = G.get(0).ring.nvar - 1; i >= 0; i--) {
1113            GenSolvablePolynomial<C> u = constructUnivariate(i, G);
1114            univs.add(u);
1115        }
1116        return univs;
1117    }
1118
1119
1120    /**
1121     * Cleanup and terminate ThreadPool.
1122     */
1123    public void terminate() {
1124        logger.info("terminate not implemented");
1125        //throw new RuntimeException("get a stack trace");
1126    }
1127
1128
1129    /**
1130     * Cancel ThreadPool.
1131     */
1132    public int cancel() {
1133        logger.info("cancel not implemented");
1134        return 0;
1135    }
1136
1137}