001/*
002 * $Id: SolvableGroebnerBaseAbstract.java 5280 2015-07-30 16:18:15Z 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.log4j.Logger;
013
014import edu.jas.poly.ExpVector;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.poly.GenSolvablePolynomial;
018import edu.jas.poly.GenSolvablePolynomialRing;
019import edu.jas.poly.QLRSolvablePolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.poly.PolynomialList;
022import edu.jas.poly.ModuleList;
023import edu.jas.poly.TermOrder;
024import edu.jas.structure.RingElem;
025import edu.jas.structure.RingFactory;
026import edu.jas.vector.BasicLinAlg;
027
028
029/**
030 * Solvable Groebner Bases abstract class. Implements common left, right and
031 * twosided Groebner bases and left, right and twosided GB tests.
032 * @param <C> coefficient type
033 * @author Heinz Kredel.
034 */
035
036public abstract class SolvableGroebnerBaseAbstract<C extends RingElem<C>> implements SolvableGroebnerBase<C> {
037
038
039    private static final Logger logger = Logger.getLogger(SolvableGroebnerBaseAbstract.class);
040
041
042    private 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 = " + pi + ", pj = " + pj);
217                    logger.info("s  = " + s + ", h = " + 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                //System.out.println("is: q generated = " + q + ", p = " + p + ", x = " + x);
285                if (!q.isZERO()) {
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                    return false;
308                }
309            }
310        }
311        return true;
312    }
313
314
315    /**
316     * Twosided Groebner base idempotence test.
317     * @param F solvable polynomial list.
318     * @return true, if F is equal to GB(F), else false.
319     */
320    public boolean isTwosidedGBidem(List<GenSolvablePolynomial<C>> F) {
321        return isTwosidedGBidem(0, F);
322    }
323
324
325    /**
326     * Twosided Groebner base idempotence test.
327     * @param modv module variable number.
328     * @param F solvable polynomial list.
329     * @return true, if F is equal to GB(F), else false.
330     */
331    public boolean isTwosidedGBidem(int modv, List<GenSolvablePolynomial<C>> F) {
332        if (F == null || F.isEmpty()) {
333            return true;
334        }
335        GenSolvablePolynomialRing<C> pring = F.get(0).ring;
336        List<GenSolvablePolynomial<C>> G = twosidedGB(modv, F);
337        PolynomialList<C> Fp = new PolynomialList<C>(pring, F);
338        PolynomialList<C> Gp = new PolynomialList<C>(pring, G);
339        return Fp.compareTo(Gp) == 0;
340    }
341
342
343    /**
344     * Right Groebner base test.
345     * @param F solvable polynomial list.
346     * @return true, if F is a right Groebner base, else false.
347     */
348    public boolean isRightGB(List<GenSolvablePolynomial<C>> F) {
349        return isRightGB(0, F);
350    }
351
352
353    /**
354     * Right Groebner base test.
355     * @param modv number of module variables.
356     * @param F solvable polynomial list.
357     * @return true, if F is a right Groebner base, else false.
358     */
359    public boolean isRightGB(int modv, List<GenSolvablePolynomial<C>> F) {
360        GenSolvablePolynomial<C> pi, pj, s, h;
361        for (int i = 0; i < F.size(); i++) {
362            pi = F.get(i);
363            //System.out.println("pi right = " + pi);
364            for (int j = i + 1; j < F.size(); j++) {
365                pj = F.get(j);
366                //System.out.println("pj right = " + pj);
367                if (!red.moduleCriterion(modv, pi, pj)) {
368                    continue;
369                }
370                // if ( ! red.criterion4( pi, pj ) ) { continue; }
371                s = sred.rightSPolynomial(pi, pj);
372                if (s.isZERO()) {
373                    continue;
374                }
375                //System.out.println("s right = " + s);
376                h = sred.rightNormalform(F, s);
377                if (!h.isZERO()) {
378                    logger.info("isRightGB non zero h = " + h + " :: " + h.ring);
379                    logger.info("p" + i + " = " + pi + ", p" + j + " = " + pj);
380                    return false;
381                    //} else {
382                    //logger.info("isRightGB zero h = " + h);
383                }
384            }
385        }
386        return true;
387    }
388
389
390    /**
391     * Right Groebner base idempotence test.
392     * @param F solvable polynomial list.
393     * @return true, if F is equal to GB(F), else false.
394     */
395    public boolean isRightGBidem(List<GenSolvablePolynomial<C>> F) {
396        return isRightGBidem(0, F);
397    }
398
399
400    /**
401     * Right Groebner base idempotence test.
402     * @param modv module variable number.
403     * @param F solvable polynomial list.
404     * @return true, if F is equal to GB(F), else false.
405     */
406    public boolean isRightGBidem(int modv, List<GenSolvablePolynomial<C>> F) {
407        if (F == null || F.isEmpty()) {
408            return true;
409        }
410        GenSolvablePolynomialRing<C> pring = F.get(0).ring;
411        List<GenSolvablePolynomial<C>> G = rightGB(modv, F);
412        PolynomialList<C> Fp = new PolynomialList<C>(pring, F);
413        PolynomialList<C> Gp = new PolynomialList<C>(pring, G);
414        return Fp.compareTo(Gp) == 0;
415    }
416
417
418    /**
419     * Left Groebner base using pairlist class.
420     * @param F solvable polynomial list.
421     * @return leftGB(F) a left Groebner base of F.
422     */
423    public List<GenSolvablePolynomial<C>> leftGB(List<GenSolvablePolynomial<C>> F) {
424        return leftGB(0, F);
425    }
426
427
428    /**
429     * Solvable Extended Groebner base using critical pair class.
430     * @param F solvable polynomial list.
431     * @return a container for an extended left Groebner base of F.
432     */
433    public SolvableExtendedGB<C> extLeftGB(List<GenSolvablePolynomial<C>> F) {
434        return extLeftGB(0, F);
435    }
436
437
438    /**
439     * Solvable Extended Groebner base using critical pair class.
440     * @param modv module variable number.
441     * @param F polynomial list.
442     * @return a container for an extended left Groebner base G of F together
443     *         with back-and-forth transformations.
444     */
445    public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) {
446        throw new UnsupportedOperationException("extLeftGB not implemented in "
447                        + this.getClass().getSimpleName());
448    }
449
450
451    /**
452     * Left minimal ordered groebner basis.
453     * @param Gp a left Groebner base.
454     * @return leftGBmi(F) a minimal left Groebner base of Gp.
455     */
456    public List<GenSolvablePolynomial<C>> leftMinimalGB(List<GenSolvablePolynomial<C>> Gp) {
457        ArrayList<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>();
458        ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator();
459        for (GenSolvablePolynomial<C> a : Gp) {
460            // a = (SolvablePolynomial) it.next();
461            if (a.length() != 0) { // always true
462                // already monic a = a.monic();
463                G.add(a);
464            }
465        }
466        if (G.size() <= 1) {
467            return G;
468        }
469
470        ExpVector e;
471        ExpVector f;
472        GenSolvablePolynomial<C> a, p;
473        ArrayList<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>();
474        boolean mt;
475
476        while (G.size() > 0) {
477            a = G.remove(0);
478            e = a.leadingExpVector();
479
480            it = G.listIterator();
481            mt = false;
482            while (it.hasNext() && !mt) {
483                p = it.next();
484                f = p.leadingExpVector();
485                mt = e.multipleOf(f);
486            }
487            it = F.listIterator();
488            while (it.hasNext() && !mt) {
489                p = it.next();
490                f = p.leadingExpVector();
491                mt = e.multipleOf(f);
492            }
493            if (!mt) {
494                F.add(a);
495            } else {
496                // System.out.println("dropped " + a.length());
497            }
498        }
499        G = F;
500        if (G.size() <= 1) {
501            return G;
502        }
503
504        F = new ArrayList<GenSolvablePolynomial<C>>();
505        while (G.size() > 0) {
506            a = G.remove(0);
507            // System.out.println("doing " + a.length());
508            a = sred.leftNormalform(G, a);
509            a = sred.leftNormalform(F, a);
510            F.add(a);
511        }
512        return F;
513    }
514
515
516    /**
517     * Right minimal ordered groebner basis.
518     * @param Gp a right Groebner base.
519     * @return rightGBmi(F) a minimal right Groebner base of Gp.
520     */
521    public List<GenSolvablePolynomial<C>> rightMinimalGB(List<GenSolvablePolynomial<C>> Gp) {
522        ArrayList<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>();
523        ListIterator<GenSolvablePolynomial<C>> it = Gp.listIterator();
524        for (GenSolvablePolynomial<C> a : Gp) {
525            if (a.length() != 0) { // always true
526                G.add(a);
527            }
528        }
529        if (G.size() <= 1) {
530            return G;
531        }
532
533        ExpVector e;
534        ExpVector f;
535        GenSolvablePolynomial<C> a, p;
536        ArrayList<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>();
537        boolean mt;
538
539        while (G.size() > 0) {
540            a = G.remove(0);
541            e = a.leadingExpVector();
542
543            it = G.listIterator();
544            mt = false;
545            while (it.hasNext() && !mt) {
546                p = it.next();
547                f = p.leadingExpVector();
548                mt = e.multipleOf(f);
549            }
550            it = F.listIterator();
551            while (it.hasNext() && !mt) {
552                p = it.next();
553                f = p.leadingExpVector();
554                mt = e.multipleOf(f);
555            }
556            if (!mt) {
557                F.add(a);
558            } else {
559                // System.out.println("dropped " + a.length());
560            }
561        }
562        G = F;
563        if (G.size() <= 1) {
564            return G;
565        }
566
567        F = new ArrayList<GenSolvablePolynomial<C>>();
568        while (G.size() > 0) {
569            a = G.remove(0);
570            // System.out.println("doing " + a.length());
571            a = sred.rightNormalform(G, a);
572            a = sred.rightNormalform(F, a);
573            F.add(a);
574        }
575        return F;
576    }
577
578
579    /**
580     * Twosided Groebner base using pairlist class.
581     * @param Fp solvable polynomial list.
582     * @return tsGB(Fp) a twosided Groebner base of Fp.
583     */
584    public List<GenSolvablePolynomial<C>> twosidedGB(List<GenSolvablePolynomial<C>> Fp) {
585        return twosidedGB(0, Fp);
586    }
587
588
589    /**
590     * Right Groebner base using opposite ring left GB.
591     * @param F solvable polynomial list.
592     * @return rightGB(F) a right Groebner base of F.
593     */
594    public List<GenSolvablePolynomial<C>> rightGB(List<GenSolvablePolynomial<C>> F) {
595        return rightGB(0, F);
596    }
597
598
599    /**
600     * Right Groebner base using opposite ring left GB.
601     * @param modv number of module variables.
602     * @param F solvable polynomial list.
603     * @return rightGB(F) a right Groebner base of F.
604     */
605    @SuppressWarnings("unchecked")
606    public List<GenSolvablePolynomial<C>> rightGB(int modv, List<GenSolvablePolynomial<C>> F) {
607        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F);
608        if (G.size() <= 1) {
609            return G;
610        }
611        GenSolvablePolynomialRing<C> ring = G.get(0).ring; // assert != null
612        GenSolvablePolynomialRing<C> rring = ring.reverse(true); //true
613        //System.out.println("reversed ring = " + rring);
614        GenSolvablePolynomial<C> q;
615        List<GenSolvablePolynomial<C>> rF;
616        rF = new ArrayList<GenSolvablePolynomial<C>>(F.size());
617        for (GenSolvablePolynomial<C> p : F) {
618            if (p != null) {
619                q = (GenSolvablePolynomial<C>) p.reverse(rring);
620                rF.add(q);
621            }
622        }
623        if (logger.isInfoEnabled()) {
624            PolynomialList<C> pl = new PolynomialList<C>(rring, rF);
625            logger.info("reversed problem = " + pl.toScript());
626        }
627        List<GenSolvablePolynomial<C>> rG = leftGB(modv, rF);
628        if (debug) {
629            //PolynomialList<C> pl = new PolynomialList<C>(rring,rG);
630            //logger.info("reversed GB = " + pl);
631            long t = System.currentTimeMillis();
632            boolean isit = isLeftGB(rG);
633            t = System.currentTimeMillis() - t;
634            logger.info("is left GB = " + isit + ", in " + t + " milliseconds");
635        }
636        //System.out.println("reversed left GB = " + rG);
637        ring = rring.reverse(true); // true
638        G = new ArrayList<GenSolvablePolynomial<C>>(rG.size());
639        for (GenSolvablePolynomial<C> p : rG) {
640            if (p != null) {
641                q = (GenSolvablePolynomial<C>) p.reverse(ring);
642                G.add(q);
643            }
644        }
645        if (debug) {
646            //PolynomialList<C> pl = new PolynomialList<C>(ring,G);
647            //logger.info("GB = " + pl);
648            long t = System.currentTimeMillis();
649            boolean isit = isRightGB(G);
650            t = System.currentTimeMillis() - t;
651            logger.info("is right GB = " + isit + ", in " + t + " milliseconds");
652        }
653        return G;
654    }
655
656
657    /**
658     * Module left Groebner base test.
659     * @param M a module basis.
660     * @return true, if M is a left Groebner base, else false.
661     */
662    public boolean isLeftGB(ModuleList<C> M) {
663        if (M == null || M.list == null) {
664            return true;
665        }
666        if (M.rows == 0 || M.cols == 0) {
667            return true;
668        }
669        int modv = M.cols; // > 0  
670        PolynomialList<C> F = M.getPolynomialList();
671        return isLeftGB(modv, F.castToSolvableList());
672    }
673
674
675    /**
676     * Left Groebner base using pairlist class.
677     * @param M a module basis.
678     * @return leftGB(M) a left Groebner base for M.
679     */
680    @SuppressWarnings("unchecked")
681    public ModuleList<C> leftGB(ModuleList<C> M) {
682        ModuleList<C> N = M;
683        if (M == null || M.list == null) {
684            return N;
685        }
686        if (M.rows == 0 || M.cols == 0) {
687            return N;
688        }
689        PolynomialList<C> F = M.getPolynomialList();
690        if (debug) {
691            logger.info("F left +++++++++++++++++++ \n" + F);
692        }
693        GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) F.ring;
694        int modv = M.cols;
695        List<GenSolvablePolynomial<C>> G = leftGB(modv, F.castToSolvableList());
696        F = new PolynomialList<C>(sring, G);
697        if (debug) {
698            logger.info("G left +++++++++++++++++++ \n" + F);
699        }
700        N = F.getModuleList(modv);
701        return N;
702    }
703
704
705    /**
706     * Module twosided Groebner base test.
707     * @param M a module basis.
708     * @return true, if M is a twosided Groebner base, else false.
709     */
710    public boolean isTwosidedGB(ModuleList<C> M) {
711        if (M == null || M.list == null) {
712            return true;
713        }
714        if (M.rows == 0 || M.cols == 0) {
715            return true;
716        }
717        PolynomialList<C> F = M.getPolynomialList();
718        int modv = M.cols; // > 0  
719        return isTwosidedGB(modv, F.castToSolvableList());
720    }
721
722
723    /**
724     * Twosided Groebner base using pairlist class.
725     * @param M a module basis.
726     * @return tsGB(M) a twosided Groebner base for M.
727     */
728    @SuppressWarnings("unchecked")
729    public ModuleList<C> twosidedGB(ModuleList<C> M) {
730        ModuleList<C> N = M;
731        if (M == null || M.list == null) {
732            return N;
733        }
734        if (M.rows == 0 || M.cols == 0) {
735            return N;
736        }
737        PolynomialList<C> F = M.getPolynomialList();
738        GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) F.ring;
739        int modv = M.cols;
740        List<GenSolvablePolynomial<C>> G = twosidedGB(modv, F.castToSolvableList());
741        F = new PolynomialList<C>(sring, G);
742        N = F.getModuleList(modv);
743        return N;
744    }
745
746
747    /**
748     * Module right Groebner base test.
749     * @param M a module basis.
750     * @return true, if M is a right Groebner base, else false.
751     */
752    public boolean isRightGB(ModuleList<C> M) {
753        if (M == null || M.list == null) {
754            return true;
755        }
756        if (M.rows == 0 || M.cols == 0) {
757            return true;
758        }
759        int modv = M.cols; // > 0  
760        PolynomialList<C> F = M.getPolynomialList();
761        //System.out.println("F test = " + F);
762        return isRightGB(modv, F.castToSolvableList());
763    }
764
765
766    /**
767     * Right Groebner base using pairlist class.
768     * @param M a module basis.
769     * @return rightGB(M) a right Groebner base for M.
770     */
771    @SuppressWarnings("unchecked")
772    public ModuleList<C> rightGB(ModuleList<C> M) {
773        ModuleList<C> N = M;
774        if (M == null || M.list == null) {
775            return N;
776        }
777        if (M.rows == 0 || M.cols == 0) {
778            return N;
779        }
780        if (debug) {
781            logger.info("M ====================== \n" + M);
782        }
783        TermOrder to = M.ring.tord;
784        if (to.getSplit() <= M.ring.nvar) {
785            throw new IllegalArgumentException("extended TermOrders not supported for rightGBs: " + to);
786        }
787        List<List<GenSolvablePolynomial<C>>> mlist = M.castToSolvableList();
788        GenSolvablePolynomialRing<C> sring = (GenSolvablePolynomialRing<C>) M.ring;
789        GenSolvablePolynomialRing<C> rring = sring.reverse(true); //true
790        sring = rring.reverse(true); // true
791
792        List<List<GenSolvablePolynomial<C>>> nlist = new ArrayList<List<GenSolvablePolynomial<C>>>(M.rows);
793        for (List<GenSolvablePolynomial<C>> row : mlist) {
794            List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row.size());
795            for (GenSolvablePolynomial<C> elem : row) {
796                GenSolvablePolynomial<C> nelem = (GenSolvablePolynomial<C>) elem.reverse(rring);
797                nrow.add(nelem);
798            }
799            nlist.add(nrow);
800        }
801        ModuleList<C> rM = new ModuleList<C>(rring, nlist);
802        if (debug) {
803            logger.info("rM -------------------- \n" + rM);
804        }
805        ModuleList<C> rMg = leftGB(rM);
806        if (debug) {
807            logger.info("rMg -------------------- \n" + rMg);
808            logger.info("isLeftGB(rMg) ---------- " + isLeftGB(rMg));
809        }
810        mlist = rMg.castToSolvableList();
811        nlist = new ArrayList<List<GenSolvablePolynomial<C>>>(rMg.rows);
812        for (List<GenSolvablePolynomial<C>> row : mlist) {
813            List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row.size());
814            for (GenSolvablePolynomial<C> elem : row) {
815                GenSolvablePolynomial<C> nelem = (GenSolvablePolynomial<C>) elem.reverse(sring);
816                nrow.add(nelem);
817            }
818            nlist.add(nrow);
819        }
820        ModuleList<C> Mg = new ModuleList<C>(sring, nlist);
821        if (debug) {
822            logger.info("Mg -------------------- \n" + Mg);
823            logger.info("isRightGB(Mg) --------- " + isRightGB(Mg));
824        }
825        return Mg;
826    }
827
828
829    /**
830     * Test if left reduction matrix.
831     * @param exgb an SolvableExtendedGB container.
832     * @return true, if exgb contains a left reduction matrix, else false.
833     */
834    public boolean isLeftReductionMatrix(SolvableExtendedGB<C> exgb) {
835        if (exgb == null) {
836            return true;
837        }
838        return isLeftReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F);
839    }
840
841
842    /**
843     * Test if left reduction matrix.
844     * @param F a solvable polynomial list.
845     * @param G a left Groebner base.
846     * @param Mf a possible left reduction matrix.
847     * @param Mg a possible left reduction matrix.
848     * @return true, if Mg and Mf are left reduction matrices, else false.
849     */
850    public boolean isLeftReductionMatrix(List<GenSolvablePolynomial<C>> F, List<GenSolvablePolynomial<C>> G,
851                    List<List<GenSolvablePolynomial<C>>> Mf, List<List<GenSolvablePolynomial<C>>> Mg) {
852        // no more check G and Mg: G * Mg[i] == 0
853        // check F and Mg: F * Mg[i] == G[i]
854        int k = 0;
855        for (List<GenSolvablePolynomial<C>> row : Mg) {
856            boolean t = sred.isLeftReductionNF(row, F, G.get(k), null);
857            if (!t) {
858                System.out.println("row = " + row);
859                System.out.println("F   = " + F);
860                System.out.println("Gk  = " + G.get(k));
861                logger.info("F isLeftReductionMatrix s, k = " + F.size() + ", " + k);
862                return false;
863            }
864            k++;
865        }
866        // check G and Mf: G * Mf[i] == F[i]
867        k = 0;
868        for (List<GenSolvablePolynomial<C>> row : Mf) {
869            boolean t = sred.isLeftReductionNF(row, G, F.get(k), null);
870            if (!t) {
871                logger.error("G isLeftReductionMatrix s, k = " + G.size() + ", " + k);
872                return false;
873            }
874            k++;
875        }
876        return true;
877    }
878
879
880    /**
881     * Ideal common zero test.
882     * @return -1, 0 or 1 if dimension(this) &eq; -1, 0 or &ge; 1.
883     */
884    public int commonZeroTest(List<GenSolvablePolynomial<C>> A) {
885        List<GenPolynomial<C>> cA = PolynomialList.<C> castToList(A);
886        return cbb.commonZeroTest(cA);
887    }
888
889
890    /**
891     * Univariate head term degrees.
892     * @param A list of solvable polynomials.
893     * @return a list of the degrees of univariate head terms.
894     */
895    public List<Long> univariateDegrees(List<GenSolvablePolynomial<C>> A) {
896        List<GenPolynomial<C>> cA = PolynomialList.<C> castToList(A);
897        return cbb.univariateDegrees(cA);
898    }
899
900
901    /**
902     * Construct univariate solvable polynomial of minimal degree in variable i
903     * of a zero dimensional ideal(G).
904     * @param i variable index.
905     * @param G list of solvable polynomials, a monic reduced left Gr&ouml;bner
906     *            base of a zero dimensional ideal.
907     * @return univariate solvable polynomial of minimal degree in variable i in
908     *         ideal_left(G)
909     */
910    public GenSolvablePolynomial<C> constructUnivariate(int i, List<GenSolvablePolynomial<C>> G) {
911        if (G == null || G.size() == 0) {
912            throw new IllegalArgumentException("G may not be null or empty");
913        }
914        List<Long> ud = univariateDegrees(G);
915        if (ud.size() <= i) {
916            //logger.info("univ pol, ud = " + ud);
917            throw new IllegalArgumentException("ideal(G) not zero dimensional " + ud);
918        }
919        int ll = 0;
920        Long di = ud.get(i);
921        if (di != null) {
922            ll = (int) (long) di;
923        } else {
924            throw new IllegalArgumentException("ideal(G) not zero dimensional");
925        }
926        long vsdim = 1;
927        for (Long d : ud) {
928            if (d != null) {
929                vsdim *= d;
930            }
931        }
932        logger.info("univariate construction, deg = " + ll + ", vsdim = " + vsdim);
933        GenSolvablePolynomialRing<C> pfac = G.get(0).ring;
934        RingFactory<C> cfac = pfac.coFac;
935
936        GenPolynomialRing<C> cpfac = new GenPolynomialRing<C>(cfac, ll, new TermOrder(TermOrder.INVLEX));
937        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = new GenSolvablePolynomialRing<GenPolynomial<C>>(
938                        cpfac, pfac); // relations
939        GenSolvablePolynomial<GenPolynomial<C>> P = rfac.getZERO();
940        for (int k = 0; k < ll; k++) {
941            GenSolvablePolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, k);
942            GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - k);
943            Pp = Pp.multiply(cp);
944            P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(Pp);
945        }
946        if (debug) {
947            logger.info("univariate construction, P = " + P);
948            logger.info("univariate construction, deg_*(G) = " + ud);
949            //throw new RuntimeException("check");
950        }
951        GroebnerBaseAbstract<C> bbc = new GroebnerBaseSeq<C>();
952        GenSolvablePolynomial<C> X;
953        GenSolvablePolynomial<C> XP;
954        // solve system of linear equations for the coefficients of the univariate polynomial
955        List<GenPolynomial<C>> ls;
956        int z = -1;
957        do {
958            //System.out.println("ll  = " + ll);
959            GenSolvablePolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, ll);
960            GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - ll);
961            Pp = Pp.multiply(cp);
962            P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(Pp);
963            X = pfac.univariate(i, ll);
964            XP = sred.leftNormalform(G, X);
965            //System.out.println("XP = " + XP);
966            GenSolvablePolynomial<GenPolynomial<C>> XPp = PolyUtil.<C> toRecursive(rfac, XP);
967            GenSolvablePolynomial<GenPolynomial<C>> XPs = (GenSolvablePolynomial<GenPolynomial<C>>) XPp
968                            .sum(P);
969            ls = new ArrayList<GenPolynomial<C>>(XPs.getMap().values());
970            //System.out.println("ls,1 = " + ls);
971            ls = red.irreducibleSet(ls);
972            z = bbc.commonZeroTest(ls);
973            if (z != 0) {
974                ll++;
975                if (ll > vsdim) {
976                    logger.info("univariate construction, P = " + P);
977                    logger.info("univariate construction, nf(P) = " + XP);
978                    logger.info("G = " + G);
979                    throw new ArithmeticException(
980                                    "univariate polynomial degree greater than vector space dimansion");
981                }
982                cpfac = cpfac.extend(1);
983                rfac = new GenSolvablePolynomialRing<GenPolynomial<C>>(cpfac, pfac);
984                P = PolyUtil.<C> extendCoefficients(rfac, P, 0, 0L);
985                XPp = PolyUtil.<C> extendCoefficients(rfac, XPp, 0, 1L);
986                P = (GenSolvablePolynomial<GenPolynomial<C>>) P.sum(XPp);
987            }
988        } while (z != 0); // && ll <= 5 && !XP.isZERO()
989        // construct result polynomial
990        String var = pfac.getVars()[pfac.nvar - 1 - i];
991        GenSolvablePolynomialRing<C> ufac = new GenSolvablePolynomialRing<C>(cfac, 1, new TermOrder(
992                        TermOrder.INVLEX), new String[] { var });
993        GenSolvablePolynomial<C> pol = ufac.univariate(0, ll);
994        for (GenPolynomial<C> pc : ls) {
995            ExpVector e = pc.leadingExpVector();
996            if (e == null) {
997                continue;
998            }
999            int[] v = e.dependencyOnVariables();
1000            if (v == null || v.length == 0) {
1001                continue;
1002            }
1003            int vi = v[0];
1004            C tc = pc.trailingBaseCoefficient();
1005            tc = tc.negate();
1006            GenSolvablePolynomial<C> pi = ufac.univariate(0, ll - 1 - vi);
1007            pi = pi.multiply(tc);
1008            pol = (GenSolvablePolynomial<C>) pol.sum(pi);
1009        }
1010        if (logger.isInfoEnabled()) {
1011            logger.info("univariate construction, pol = " + pol);
1012        }
1013        return pol;
1014    }
1015
1016
1017    /**
1018     * Construct univariate solvable polynomials of minimal degree in all
1019     * variables in zero dimensional left ideal(G).
1020     * @return list of univariate polynomial of minimal degree in each variable
1021     *         in ideal_left(G)
1022     */
1023    public List<GenSolvablePolynomial<C>> constructUnivariate(List<GenSolvablePolynomial<C>> G) {
1024        List<GenSolvablePolynomial<C>> univs = new ArrayList<GenSolvablePolynomial<C>>();
1025        if (G == null || G.isEmpty()) {
1026            return univs;
1027        }
1028        for (int i = G.get(0).ring.nvar - 1; i >= 0; i--) {
1029            GenSolvablePolynomial<C> u = constructUnivariate(i, G);
1030            univs.add(u);
1031        }
1032        return univs;
1033    }
1034
1035
1036    /**
1037     * Cleanup and terminate ThreadPool.
1038     */
1039    public void terminate() {
1040        logger.info("terminate not implemented");
1041        //throw new RuntimeException("get a stack trace");
1042    }
1043
1044
1045    /**
1046     * Cancel ThreadPool.
1047     */
1048    public int cancel() {
1049        logger.info("cancel not implemented");
1050        return 0;
1051    }
1052
1053}