Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.HashSet;
011import java.util.List;
012import java.util.ListIterator;
013import java.util.Map;
014import java.util.Set;
015import java.util.TreeMap;
016
017import org.apache.logging.log4j.LogManager;
018import org.apache.logging.log4j.Logger;
019
020import edu.jas.poly.ExpVector;
021import edu.jas.poly.GenPolynomial;
022import edu.jas.poly.GenPolynomialRing;
023import edu.jas.poly.ModuleList;
024import edu.jas.poly.OrderedPolynomialList;
025import edu.jas.poly.PolyUtil;
026import edu.jas.poly.PolynomialList;
027import edu.jas.poly.TermOrder;
028import edu.jas.structure.RingElem;
029import edu.jas.structure.RingFactory;
030import edu.jas.vector.BasicLinAlg;
031
032
033/**
034 * Groebner Bases abstract class. Implements common Groebner bases and GB test
035 * methods.
036 * @param <C> coefficient type
037 * @author Heinz Kredel
038 * 
039 * @see edu.jas.application.GBAlgorithmBuilder
040 * @see edu.jas.gbufd.GBFactory
041 */
042
043public abstract class GroebnerBaseAbstract<C extends RingElem<C>> implements GroebnerBase<C> {
044
045
046    private static final Logger logger = LogManager.getLogger(GroebnerBaseAbstract.class);
047
048
049    private static final boolean debug = logger.isDebugEnabled();
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    public final BasicLinAlg<GenPolynomial<C>> blas;
068
069
070    /**
071     * Constructor.
072     */
073    public GroebnerBaseAbstract() {
074        this(new ReductionSeq<C>());
075    }
076
077
078    /**
079     * Constructor.
080     * @param red Reduction engine
081     */
082    public GroebnerBaseAbstract(Reduction<C> red) {
083        this(red, new OrderedPairlist<C>());
084    }
085
086
087    /**
088     * Constructor.
089     * @param pl pair selection strategy
090     */
091    public GroebnerBaseAbstract(PairList<C> pl) {
092        this(new ReductionSeq<C>(), pl);
093    }
094
095
096    /**
097     * Constructor.
098     * @param red Reduction engine
099     * @param pl pair selection strategy
100     */
101    public GroebnerBaseAbstract(Reduction<C> red, PairList<C> pl) {
102        if (red == null) {
103            red = new ReductionSeq<C>();
104        }
105        this.red = red;
106        if (pl == null) {
107            pl = new OrderedPairlist<C>();
108        }
109        this.strategy = pl;
110        blas = new BasicLinAlg<GenPolynomial<C>>();
111    }
112
113
114    /**
115     * Get the String representation with GB engines.
116     * @see java.lang.Object#toString()
117     */
118    @Override
119    public String toString() {
120        return this.getClass().getSimpleName();
121    }
122
123
124    /**
125     * Normalize polynomial list.
126     * @param A list of polynomials.
127     * @return list of polynomials with zeros removed and ones/units reduced.
128     */
129    public List<GenPolynomial<C>> normalizeZerosOnes(List<GenPolynomial<C>> A) {
130        if (A == null) {
131            return A;
132        }
133        List<GenPolynomial<C>> N = new ArrayList<GenPolynomial<C>>(A.size());
134        if (A.isEmpty()) {
135            return N;
136        }
137        for (GenPolynomial<C> p : A) {
138            if (p == null || p.isZERO()) {
139                continue;
140            }
141            if (p.isUnit()) {
142                N.clear();
143                N.add(p.ring.getONE());
144                return N;
145            }
146            N.add(p.abs());
147        }
148        //N.trimToSize();
149        return N;
150    }
151
152
153    /**
154     * Groebner base test.
155     * @param F polynomial list.
156     * @return true, if F is a Groebner base, else false.
157     */
158    public boolean isGB(List<GenPolynomial<C>> F) {
159        return isGB(0, F);
160    }
161
162
163    /**
164     * Groebner base test.
165     * @param modv module variable number.
166     * @param F polynomial list.
167     * @return true, if F is a Groebner base, else false.
168     */
169    public boolean isGB(int modv, List<GenPolynomial<C>> F) {
170        return isGB(modv, F, true);
171    }
172
173
174    /**
175     * Groebner base test.
176     * @param F polynomial list.
177     * @param b true for simple test, false for GB test.
178     * @return true, if F is a Groebner base, else false.
179     */
180    public boolean isGB(List<GenPolynomial<C>> F, boolean b) {
181        return isGB(0, F, b);
182    }
183
184
185    /**
186     * Groebner base test.
187     * @param modv module variable number.
188     * @param F polynomial list.
189     * @param b true for simple test, false for GB test.
190     * @return true, if F is a Groebner base, else false.
191     */
192    public boolean isGB(int modv, List<GenPolynomial<C>> F, boolean b) {
193        if (b) {
194            return isGBsimple(modv, F);
195        }
196        return isGBidem(modv, F);
197    }
198
199
200    /**
201     * Groebner base simple test.
202     * @param modv module variable number.
203     * @param F polynomial list.
204     * @return true, if F is a Groebner base, else false.
205     */
206    public boolean isGBsimple(int modv, List<GenPolynomial<C>> F) {
207        if (F == null || F.isEmpty()) {
208            return true;
209        }
210        GenPolynomial<C> pi, pj, s, h;
211        ExpVector ei, ej, eij;
212        for (int i = 0; i < F.size(); i++) {
213            pi = F.get(i);
214            ei = pi.leadingExpVector();
215            for (int j = i + 1; j < F.size(); j++) {
216                pj = F.get(j);
217                ej = pj.leadingExpVector();
218                if (!red.moduleCriterion(modv, ei, ej)) {
219                    continue;
220                }
221                eij = ei.lcm(ej);
222                if (!red.criterion4(ei, ej, eij)) {
223                    continue;
224                }
225                if (!criterion3(i, j, eij, F)) {
226                    continue;
227                }
228                s = red.SPolynomial(pi, pj);
229                if (s.isZERO()) {
230                    continue;
231                }
232                //System.out.println("i, j = " + i + ", " + j); 
233                h = red.normalform(F, s);
234                if (!h.isZERO()) {
235                    logger.info("no GB: pi = {}, pj = {}", pi, pj);
236                    logger.info("s  = {}, h = {}", s, h);
237                    return false;
238                }
239            }
240        }
241        return true;
242    }
243
244
245    /**
246     * GB criterium 3.
247     * @return true if the S-polynomial(i,j) is required.
248     */
249    boolean criterion3(int i, int j, ExpVector eij, List<GenPolynomial<C>> P) {
250        assert i < j;
251        //for ( int k = 0; k < P.size(); k++ ) {
252        // not of much use
253        for (int k = 0; k < i; k++) {
254            GenPolynomial<C> A = P.get(k);
255            ExpVector ek = A.leadingExpVector();
256            if (eij.multipleOf(ek)) {
257                return false;
258            }
259        }
260        return true;
261    }
262
263
264    /**
265     * Groebner base idempotence test.
266     * @param modv module variable number.
267     * @param F polynomial list.
268     * @return true, if F is equal to GB(F), else false.
269     */
270    public boolean isGBidem(int modv, List<GenPolynomial<C>> F) {
271        if (F == null || F.isEmpty()) {
272            return true;
273        }
274        GenPolynomialRing<C> pring = F.get(0).ring;
275        List<GenPolynomial<C>> G = GB(modv, F);
276        PolynomialList<C> Fp = new PolynomialList<C>(pring, F);
277        PolynomialList<C> Gp = new PolynomialList<C>(pring, G);
278        return Fp.compareTo(Gp) == 0;
279    }
280
281
282    /**
283     * Common zero test.
284     * @param F polynomial list.
285     * @return -1, 0 or 1 if dimension(ideal(F)) &eq; -1, 0 or &ge; 1.
286     */
287    public int commonZeroTest(List<GenPolynomial<C>> F) {
288        if (F == null || F.isEmpty()) {
289            return 1;
290        }
291        GenPolynomialRing<C> pfac = F.get(0).ring;
292        if (pfac.nvar <= 0) {
293            return -1;
294        }
295        //int uht = 0;
296        Set<Integer> v = new HashSet<Integer>(); // for non reduced GBs
297        for (GenPolynomial<C> p : F) {
298            if (p.isZERO()) {
299                continue;
300            }
301            if (p.isConstant()) { // for non-monic lists
302                return -1;
303            }
304            ExpVector e = p.leadingExpVector();
305            if (e == null) {
306                continue;
307            }
308            int[] u = e.dependencyOnVariables();
309            if (u == null) {
310                continue;
311            }
312            if (u.length == 1) {
313                //uht++;
314                v.add(u[0]);
315            }
316        }
317        if (pfac.nvar == v.size()) {
318            return 0;
319        }
320        return 1;
321    }
322
323
324    /**
325     * Groebner base using pairlist class.
326     * @param F polynomial list.
327     * @return GB(F) a Groebner base of F.
328     */
329    public List<GenPolynomial<C>> GB(List<GenPolynomial<C>> F) {
330        return GB(0, F);
331    }
332
333
334    /**
335     * isGB.
336     * @param M a module basis.
337     * @return true, if M is a Groebner base, else false.
338     */
339    public boolean isGB(ModuleList<C> M) {
340        return isGB(M, false);
341    }
342
343
344    /**
345     * isGB.
346     * @param M a module basis.
347     * @param top true for TOP term order, false for POT term order.
348     * @return true, if M is a Groebner base, else false.
349     */
350    public boolean isGB(ModuleList<C> M, boolean top) {
351        if (M == null || M.list == null) {
352            return true;
353        }
354        if (M.rows == 0 || M.cols == 0) {
355            return true;
356        }
357        PolynomialList<C> F = M.getPolynomialList(top);
358        int modv = M.cols; // > 0  
359        return isGB(modv, F.list);
360    }
361
362
363    /**
364     * GB.
365     * @param M a module basis.
366     * @return GB(M), a Groebner base of M.
367     */
368    public ModuleList<C> GB(ModuleList<C> M) {
369        return GB(M, false);
370    }
371
372
373    /**
374     * GB.
375     * @param M a module basis.
376     * @param top true for TOP term order, false for POT term order.
377     * @return GB(M), a Groebner base of M wrt. TOP or POT.
378     */
379    public ModuleList<C> GB(ModuleList<C> M, boolean top) {
380        ModuleList<C> N = M;
381        if (M == null || M.list == null) {
382            return N;
383        }
384        if (M.rows == 0 || M.cols == 0) {
385            return N;
386        }
387        PolynomialList<C> F = M.getPolynomialList(top);
388        int modv = M.cols;
389        List<GenPolynomial<C>> G = GB(modv, F.list);
390        F = new PolynomialList<C>(F.ring, G);
391        N = F.getModuleList(modv);
392        return N;
393    }
394
395
396    /**
397     * Extended Groebner base using critical pair class.
398     * @param F polynomial list.
399     * @return a container for a Groebner base G of F together with
400     *         back-and-forth transformations.
401     */
402    public ExtendedGB<C> extGB(List<GenPolynomial<C>> F) {
403        return extGB(0, F);
404    }
405
406
407    /**
408     * Extended Groebner base using critical pair class.
409     * @param modv module variable number.
410     * @param F polynomial list.
411     * @return a container for a Groebner base G of F together with
412     *         back-and-forth transformations.
413     */
414    public ExtendedGB<C> extGB(int modv, List<GenPolynomial<C>> F) {
415        throw new UnsupportedOperationException(
416                        "extGB not implemented in " + this.getClass().getSimpleName());
417    }
418
419
420    /**
421     * Minimal ordered Groebner basis.
422     * @param Gp a Groebner base.
423     * @return a reduced Groebner base of Gp.
424     */
425    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
426        if (Gp == null || Gp.size() <= 1) {
427            return Gp;
428        }
429        // remove zero polynomials
430        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
431        for (GenPolynomial<C> a : Gp) {
432            if (a != null && !a.isZERO()) { // always true in GB()
433                // already positive a = a.abs();
434                G.add(a);
435            }
436        }
437        if (G.size() <= 1) {
438            return G;
439        }
440        // remove top reducible polynomials
441        GenPolynomial<C> a;
442        List<GenPolynomial<C>> F;
443        F = new ArrayList<GenPolynomial<C>>(G.size());
444        while (G.size() > 0) {
445            a = G.remove(0);
446            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
447                // drop polynomial 
448                if (debug) {
449                    System.out.println("dropped " + a);
450                    List<GenPolynomial<C>> ff;
451                    ff = new ArrayList<GenPolynomial<C>>(G);
452                    ff.addAll(F);
453                    a = red.normalform(ff, a);
454                    if (!a.isZERO()) {
455                        System.out.println("error, nf(a) " + a);
456                    }
457                }
458            } else {
459                F.add(a);
460            }
461        }
462        G = F;
463        if (G.size() <= 1) {
464            return G;
465        }
466        // reduce remaining polynomials
467        Collections.reverse(G); // important for lex GB
468        int len = G.size();
469        if (debug) {
470            System.out.println("#G " + len);
471            for (GenPolynomial<C> aa : G) {
472                System.out.println("aa = " + aa.length() + ", lt = " + aa.getMap().keySet());
473            }
474        }
475        int i = 0;
476        while (i < len) {
477            a = G.remove(0);
478            if (debug) {
479                System.out.println("doing " + a.length() + ", lt = " + a.leadingExpVector());
480            }
481            a = red.normalform(G, a);
482            G.add(a); // adds as last
483            i++;
484        }
485        Collections.reverse(G); // undo reverse
486        return G;
487    }
488
489
490    /**
491     * Test for minimal ordered Groebner basis.
492     * @param Gp an ideal base.
493     * @return true, if Gp is a reduced minimal Groebner base.
494     */
495    public boolean isMinimalGB(List<GenPolynomial<C>> Gp) {
496        if (Gp == null || Gp.size() == 0) {
497            return true;
498        }
499        // test for zero polynomials
500        for (GenPolynomial<C> a : Gp) {
501            if (a == null || a.isZERO()) {
502                if (debug) {
503                    logger.debug("zero polynomial {}", a);
504                }
505                return false;
506            }
507        }
508        // test for top reducible polynomials
509        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp);
510        List<GenPolynomial<C>> F = new ArrayList<GenPolynomial<C>>(G.size());
511        while (G.size() > 0) {
512            GenPolynomial<C> a = G.remove(0);
513            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
514                if (debug) {
515                    logger.debug("top reducible polynomial {}", a);
516                }
517                return false;
518            }
519            F.add(a);
520        }
521        G = F;
522        if (G.size() <= 1) {
523            return true;
524        }
525        // test reducibility of polynomials
526        int len = G.size();
527        int i = 0;
528        while (i < len) {
529            GenPolynomial<C> a = G.remove(0);
530            if (!red.isNormalform(G, a)) {
531                if (debug) {
532                    logger.debug("reducible polynomial {}", a);
533                }
534                return false;
535            }
536            G.add(a); // re-adds as last
537            i++;
538        }
539        return true;
540    }
541
542
543    /**
544     * Test if reduction matrix.
545     * @param exgb an ExtendedGB container.
546     * @return true, if exgb contains a reduction matrix, else false.
547     */
548    public boolean isReductionMatrix(ExtendedGB<C> exgb) {
549        if (exgb == null) {
550            return true;
551        }
552        return isReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F);
553    }
554
555
556    /**
557     * Test if minimal reduction matrix.
558     * @param exgb an ExtendedGB container.
559     * @return true, if exgb contains a minimal reduction matrix, else false.
560     */
561    public boolean isMinReductionMatrix(ExtendedGB<C> exgb) {
562        if (exgb == null) {
563            return true;
564        }
565        return isMinReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F);
566    }
567
568
569    /**
570     * Test if reduction matrix.
571     * @param F a polynomial list.
572     * @param G a Groebner base, G starting with +/- elements of F.
573     * @param Mf a possible reduction matrix.
574     * @param Mg a possible reduction matrix.
575     * @return true, if Mg and Mf are reduction matrices, else false.
576     */
577    public boolean isReductionMatrix(List<GenPolynomial<C>> F, List<GenPolynomial<C>> G,
578                    List<List<GenPolynomial<C>>> Mf, List<List<GenPolynomial<C>>> Mg) {
579        final int flen;
580        if (F == null) {
581            flen = -1;
582        } else {
583            flen = F.size();
584        }
585        // no more check G and Mg: G * Mg[i] == 0
586        // i < #F:  check F and Mg: Mg[i] * F == G[i]
587        // i >= #F: check G and Mg: Mg[i] * G == G[i]
588        int k = 0;
589        for (List<GenPolynomial<C>> row : Mg) {
590            boolean t;
591            if (k < flen) {
592                t = red.isReductionNF(row, F, G.get(k), null);
593                //logger.info("{} isReductionMatrix row, F, G(k), k = {}, {}, {}, {}", t, row, F, G.get(k), k);
594            } else {
595                t = red.isReductionNF(row, G, G.get(k), null);
596                //logger.info("{} isReductionMatrix row, G, G(k), k = {}, {}, {}, {}", t, row, G, G.get(k), k);
597            }
598            if (!t) {
599                logger.warn("isReductionMatrix row, F, G, k = {}, {}, {}, {}", row, F, G, k);
600                return false;
601            }
602            k++;
603        }
604        // check G and Mf: Mf[i] * G == F[i]
605        k = 0;
606        for (List<GenPolynomial<C>> row : Mf) {
607            boolean t = red.isReductionNF(row, G, F.get(k), null);
608            //logger.info("{} isMinReductionMatrix row, G, F(k), k = {}, {}, {}, {}", t, row, G, F.get(k), k);
609            if (!t) {
610                logger.warn("G isReductionMatrix row, G, F(k), k = {}, {}, {}, {}", row, G, F.get(k), k);
611                return false;
612            }
613            k++;
614        }
615        return true;
616    }
617
618
619    /**
620     * Test if minimal reduction matrix.
621     * @param F a polynomial list.
622     * @param G a minimal Groebner base of F.
623     * @param Mf a possible reduction matrix.
624     * @param Mg a possible reduction matrix.
625     * @return true, if Mg and Mf are reduction matrices, else false.
626     */
627    public boolean isMinReductionMatrix(List<GenPolynomial<C>> F, List<GenPolynomial<C>> G,
628                    List<List<GenPolynomial<C>>> Mf, List<List<GenPolynomial<C>>> Mg) {
629        if (F == null || G == null) {
630            throw new IllegalArgumentException("F or G may not be null or empty");
631        }
632        //final int flen = F.size();
633        // no more check G and Mg: G * Mg[i] == 0
634        // check F and Mg: Mg[i] * F == G[i]
635        int k = 0;
636        for (List<GenPolynomial<C>> row : Mg) {
637            boolean t = red.isReductionNF(row, F, G.get(k), null);
638            //logger.info("{} isMinReductionMatrix row, F, G(k), k = {}, {}, {}, {}", t, row, F, G.get(k), k);
639            if (!t) {
640                logger.warn("isMinReductionMatrix row, F, G, k = {}, {}, {}, {}", row, F, G, k);
641                return false;
642            }
643            k++;
644        }
645        // check G and Mf: Mf[i] * G == F[i]
646        k = 0;
647        for (List<GenPolynomial<C>> row : Mf) {
648            boolean t = red.isReductionNF(row, G, F.get(k), null);
649            //logger.info("{} isMinReductionMatrix row, G, F(k), k = {}, {}, {}, {}", t, row, G, F.get(k), k);
650            if (!t) {
651                logger.warn("G isMinReductionMatrix row, G, F(k), k = {}, {}, {}, {}", row, G, F.get(k), k);
652                return false;
653            }
654            k++;
655        }
656        return true;
657    }
658
659
660    /**
661     * Normalize M. Scale and shift right triangular matrix (new G elements) to
662     * left and make all right column elements zero. Then truncate all rows to
663     * the size of F.
664     * @param flen length of rows.
665     * @param M a reduction matrix.
666     * @return normalized M.
667     */
668    public List<List<GenPolynomial<C>>> normalizeMatrix(int flen, List<List<GenPolynomial<C>>> M) {
669        if (M == null) {
670            return M;
671        }
672        if (M.size() == 0) {
673            return M;
674        }
675        List<List<GenPolynomial<C>>> N = new ArrayList<List<GenPolynomial<C>>>();
676        List<List<GenPolynomial<C>>> K = new ArrayList<List<GenPolynomial<C>>>();
677        int mlen = M.get(M.size() - 1).size(); // longest row
678        //System.out.println("norm M pre reduc = " + M);
679        // pad / extend rows
680        for (List<GenPolynomial<C>> row : M) {
681            List<GenPolynomial<C>> nrow = blas.genVector(mlen, null, row);
682            N.add(nrow);
683        }
684        // System.out.println("norm N fill = " + N);
685        // make zero right columns
686        int k = flen; // right part
687        for (int i = 0; i < N.size(); i++) { // 0
688            List<GenPolynomial<C>> row = N.get(i);
689            if (debug) {
690                logger.info("row = {}", row);
691            }
692            K.add(row);
693            if (i < flen) { // skip identity part??
694                continue; // what with -1 ?
695            }
696            //System.out.println("norm i = " + i + ", row = " + row);
697            for (int j = i + 1; j < N.size(); j++) {
698                List<GenPolynomial<C>> nrow = N.get(j);
699                //System.out.println("nrow j = " + j + ", nrow = " + nrow);
700                if (k < nrow.size()) { // always true
701                    GenPolynomial<C> a = nrow.get(k); // right matrix k ~ flen+i
702                    //System.out.println("k, a = " + k + ", " + a);
703                    if (a != null && !a.isZERO()) {
704                        List<GenPolynomial<C>> xrow = blas.scalarProduct(a, row);
705                        xrow = blas.vectorAdd(xrow, nrow);
706                        //System.out.println("xrow = " + xrow);
707                        N.set(j, xrow);
708                    }
709                }
710            }
711            k++;
712        }
713        //System.out.println("norm K reduc = " + K);
714        // truncate 
715        N.clear();
716        for (List<GenPolynomial<C>> row : K) {
717            List<GenPolynomial<C>> tr = blas.genVector(flen, null, row);
718            N.add(tr);
719        }
720        K = N;
721        //System.out.println("norm K trunc = " + K);
722        return K;
723    }
724
725
726    /**
727     * Minimal extended groebner basis.
728     * @param flen length of rows.
729     * @param Gp a Groebner base.
730     * @param M a reduction matrix, is modified.
731     * @return a (partially) reduced Groebner base of Gp in a (fake) container.
732     */
733    public ExtendedGB<C> minimalExtendedGB(int flen, List<GenPolynomial<C>> Gp,
734                    List<List<GenPolynomial<C>>> M) {
735        if (Gp == null) {
736            return null; //new ExtendedGB<C>(null,Gp,null,M);
737        }
738        //if (Gp.size() <= 1) {
739        //    return new ExtendedGB<C>(null, Gp, null, M);
740        //}
741        List<GenPolynomial<C>> G, F;
742        G = new ArrayList<GenPolynomial<C>>(Gp);
743        F = new ArrayList<GenPolynomial<C>>(Gp.size());
744
745        List<List<GenPolynomial<C>>> Mg, Mf;
746        Mg = new ArrayList<List<GenPolynomial<C>>>(M.size());
747        Mf = new ArrayList<List<GenPolynomial<C>>>(M.size());
748        for (List<GenPolynomial<C>> r : M) {
749            // must be copied also
750            List<GenPolynomial<C>> row = new ArrayList<GenPolynomial<C>>(r);
751            Mg.add(row);
752        }
753
754        GenPolynomial<C> a, p;
755        ExpVector e, f;
756        boolean mt;
757        ListIterator<GenPolynomial<C>> it;
758        ArrayList<Integer> ix = new ArrayList<Integer>();
759        //??ArrayList<Integer> jx = new ArrayList<Integer>();
760        int k = 0;
761        //System.out.println("flen, Gp, M = " + flen + ", " + Gp.size() + ", " + M.size() );
762        while (G.size() > 0) {
763            a = G.remove(0);
764            e = a.leadingExpVector();
765
766            it = G.listIterator();
767            mt = false;
768            while (it.hasNext() && !mt) {
769                p = it.next();
770                f = p.leadingExpVector();
771                mt = e.multipleOf(f);
772            }
773            it = F.listIterator();
774            while (it.hasNext() && !mt) {
775                p = it.next();
776                f = p.leadingExpVector();
777                mt = e.multipleOf(f);
778            }
779            //System.out.println("k, mt = " + k + ", " + mt);
780            if (!mt) {
781                F.add(a);
782                ix.add(k);
783                //} else { // drop polynomial and corresponding row and column
784                // F.add( a.ring.getZERO() );
785                //??jx.add(k);
786            }
787            k++;
788        }
789        if (debug) {
790            logger.debug("ix, #M = {}, {}", ix, Mg.size()); //??, jx);
791        }
792        int fix = -1; // copied polys
793        // copy Mg to Mf as indicated by ix
794        for (int i = 0; i < ix.size(); i++) {
795            int u = ix.get(i);
796            if (u >= flen && fix == -1) {
797                fix = Mf.size();
798            }
799            //System.out.println("copy u, fix = " + u + ", " + fix);
800            if (u >= 0) {
801                List<GenPolynomial<C>> row = Mg.get(u);
802                Mf.add(row);
803            }
804        }
805        if (F.size() <= 1 || fix == -1) {
806            return new ExtendedGB<C>(null, F, null, Mf);
807        }
808        // must return, since extended normalform has not correct order of polys
809        /*
810        G = F;
811        F = new ArrayList<GenPolynomial<C>>( G.size() );
812        List<GenPolynomial<C>> temp;
813        k = 0;
814        final int len = G.size();
815        while ( G.size() > 0 ) {
816            a = G.remove(0);
817            if ( k >= fix ) { // dont touch copied polys
818               row = Mf.get( k );
819               //System.out.println("doing k = " + k + ", " + a);
820               // must keep order, but removed polys missing
821               temp = new ArrayList<GenPolynomial<C>>( len );
822               temp.addAll( F );
823               temp.add( a.ring.getZERO() ); // ??
824               temp.addAll( G );
825               //System.out.println("row before = " + row);
826               a = red.normalform( row, temp, a );
827               //System.out.println("row after  = " + row);
828            }
829            F.add( a );
830            k++;
831        }
832        // does Mf need renormalization?
833        */
834        return new ExtendedGB<C>(null, F, null, Mf);
835    }
836
837
838    /**
839     * Univariate head term degrees.
840     * @param A list of polynomials.
841     * @return a list of the degrees of univariate head terms.
842     */
843    public List<Long> univariateDegrees(List<GenPolynomial<C>> A) {
844        List<Long> ud = new ArrayList<Long>();
845        if (A == null || A.size() == 0) {
846            return ud;
847        }
848        GenPolynomialRing<C> pfac = A.get(0).ring;
849        if (pfac.nvar <= 0) {
850            return ud;
851        }
852        //int uht = 0;
853        Map<Integer, Long> v = new TreeMap<Integer, Long>(); // for non reduced GBs
854        for (GenPolynomial<C> p : A) {
855            ExpVector e = p.leadingExpVector();
856            if (e == null) {
857                continue;
858            }
859            int[] u = e.dependencyOnVariables();
860            if (u == null) {
861                continue;
862            }
863            if (u.length == 1) {
864                //uht++;
865                Long d = v.get(u[0]);
866                if (d == null) {
867                    v.put(u[0], e.getVal(u[0]));
868                }
869            }
870        }
871        for (int i = 0; i < pfac.nvar; i++) {
872            Long d = v.get(i);
873            ud.add(d);
874        }
875        //Collections.reverse(ud);
876        return ud;
877    }
878
879
880    /**
881     * Construct univariate polynomial of minimal degree in variable i of a zero
882     * dimensional ideal(G).
883     * @param i variable index.
884     * @param G list of polynomials, a monic reduced Gr&ouml;bner base of a zero
885     *            dimensional ideal.
886     * @return univariate polynomial of minimal degree in variable i in ideal(G)
887     */
888    public GenPolynomial<C> constructUnivariate(int i, List<GenPolynomial<C>> G) {
889        if (G == null || G.size() == 0) {
890            throw new IllegalArgumentException("G may not be null or empty");
891        }
892        //logger.info("G in  = {}", G);
893        //Collections.reverse(G); // test
894        G = OrderedPolynomialList.<C> sort(G); // better performance
895        List<Long> ud = univariateDegrees(G);
896        if (ud.size() <= i) {
897            //logger.info("univ pol, ud = {}", ud);
898            throw new IllegalArgumentException("ideal(G) not zero dimensional " + ud);
899        }
900        int ll = 0;
901        Long di = ud.get(i);
902        if (di != null) {
903            ll = (int) (long) di;
904        } else {
905            throw new IllegalArgumentException("ideal(G) not zero dimensional");
906        }
907        long vsdim = 1;
908        for (Long d : ud) {
909            if (d != null) {
910                vsdim *= d;
911            }
912        }
913        logger.info("univariate construction, deg = {}, vsdim = {}", ll, vsdim);
914        GenPolynomialRing<C> pfac = G.get(0).ring;
915        RingFactory<C> cfac = pfac.coFac;
916        String var = pfac.getVars()[pfac.nvar - 1 - i];
917        GenPolynomialRing<C> ufac = new GenPolynomialRing<C>(cfac, 1, new TermOrder(TermOrder.INVLEX),
918                        new String[] { var });
919
920        GenPolynomialRing<C> cpfac = new GenPolynomialRing<C>(cfac, ll, new TermOrder(TermOrder.INVLEX));
921        GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cpfac, pfac);
922        GenPolynomial<GenPolynomial<C>> P = rfac.getZERO();
923        for (int k = 0; k < ll; k++) {
924            GenPolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, k);
925            GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - k);
926            Pp = Pp.multiply(cp);
927            P = P.sum(Pp);
928        }
929        if (debug) {
930            logger.info("univariate construction, P = {}", P);
931            logger.info("univariate construction, deg_*(G) = {}", ud);
932            //throw new RuntimeException("check");
933        }
934        GenPolynomial<C> X;
935        GenPolynomial<C> XP;
936        // solve system of linear equations for the coefficients of the univariate polynomial
937        List<GenPolynomial<C>> ls;
938        int z = -1;
939        do {
940            //System.out.println("ll  = " + ll);
941            GenPolynomial<GenPolynomial<C>> Pp = rfac.univariate(i, ll);
942            GenPolynomial<C> cp = cpfac.univariate(cpfac.nvar - 1 - ll);
943            Pp = Pp.multiply(cp);
944            P = P.sum(Pp);
945            X = pfac.univariate(i, ll);
946            XP = red.normalform(G, X);
947            if (debug) {
948                logger.info("XP = {}", XP);
949            }
950            GenPolynomial<GenPolynomial<C>> XPp = PolyUtil.<C> toRecursive(rfac, XP);
951            GenPolynomial<GenPolynomial<C>> XPs = XPp.sum(P);
952            ls = new ArrayList<GenPolynomial<C>>(XPs.getMap().values());
953            //System.out.println("ls,1 = " + ls);
954            ls = red.irreducibleSet(ls);
955            z = commonZeroTest(ls);
956            if (z != 0) {
957                ll++;
958                if (ll > vsdim) {
959                    logger.info("univariate construction, P = {}", P);
960                    logger.info("univariate construction, nf(P) = {}", XP);
961                    logger.info("G = {}", G);
962                    throw new ArithmeticException(
963                                    "univariate polynomial degree greater than vector space dimansion");
964                }
965                cpfac = cpfac.extend(1);
966                rfac = new GenPolynomialRing<GenPolynomial<C>>(cpfac, pfac);
967                P = PolyUtil.<C> extendCoefficients(rfac, P, 0, 0L);
968                XPp = PolyUtil.<C> extendCoefficients(rfac, XPp, 0, 1L);
969                P = P.sum(XPp);
970            }
971        } while (z != 0); // && ll <= 5 && !XP.isZERO()
972        // construct result polynomial
973        GenPolynomial<C> pol = ufac.univariate(0, ll);
974        for (GenPolynomial<C> pc : ls) {
975            ExpVector e = pc.leadingExpVector();
976            if (e == null) {
977                continue;
978            }
979            int[] v = e.dependencyOnVariables();
980            if (v == null || v.length == 0) {
981                continue;
982            }
983            int vi = v[0];
984            C lc = pc.leadingBaseCoefficient();
985            C tc = pc.trailingBaseCoefficient();
986            tc = tc.negate();
987            if (!lc.isONE()) {
988                tc = tc.divide(lc);
989            }
990            GenPolynomial<C> pi = ufac.univariate(0, ll - 1 - vi);
991            pi = pi.multiply(tc);
992            pol = pol.sum(pi);
993        }
994        if (logger.isInfoEnabled()) {
995            logger.info("univariate construction, pol = {}", pol);
996        }
997        return pol;
998    }
999
1000
1001    /**
1002     * Cleanup and terminate ThreadPool.
1003     */
1004    public void terminate() {
1005        logger.info("terminate not implemented");
1006        //throw new RuntimeException("get a stack trace");
1007    }
1008
1009
1010    /**
1011     * Cancel ThreadPool.
1012     */
1013    public int cancel() {
1014        logger.info("cancel not implemented");
1015        return 0;
1016    }
1017
1018}