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