Source code

001/*
002 * $Id: SolvableGroebnerBaseSeq.java 5294 2015-08-06 20:51:47Z 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.GenSolvablePolynomial;
017import edu.jas.poly.GenSolvablePolynomialRing;
018import edu.jas.poly.QLRSolvablePolynomialRing;
019import edu.jas.poly.PolyUtil;
020import edu.jas.poly.PolynomialList;
021import edu.jas.structure.RingElem;
022
023
024/**
025 * Solvable Groebner bases sequential algorithms. Implements common left, right
026 * and twosided Groebner bases and left, right and twosided GB tests.
027 * @param <C> coefficient type
028 * @author Heinz Kredel.
029 */
030
031public class SolvableGroebnerBaseSeq<C extends RingElem<C>> extends SolvableGroebnerBaseAbstract<C> {
032
033
034    private static final Logger logger = Logger.getLogger(SolvableGroebnerBaseSeq.class);
035
036
037    private final boolean debug = logger.isDebugEnabled();
038
039
040    /**
041     * Constructor.
042     */
043    public SolvableGroebnerBaseSeq() {
044        super();
045    }
046
047
048    /**
049     * Constructor.
050     * @param sred Solvable reduction engine
051     */
052    public SolvableGroebnerBaseSeq(SolvableReduction<C> sred) {
053        super(sred);
054    }
055
056
057    /**
058     * Constructor.
059     * @param pl pair selection strategy
060     */
061    public SolvableGroebnerBaseSeq(PairList<C> pl) {
062        super(pl);
063    }
064
065
066    /**
067     * Constructor.
068     * @param sred Solvable reduction engine
069     * @param pl pair selection strategy
070     */
071    public SolvableGroebnerBaseSeq(SolvableReduction<C> sred, PairList<C> pl) {
072        super(sred, pl);
073    }
074
075
076    /**
077     * Left Groebner base using pairlist class.
078     * @param modv number of module variables.
079     * @param F solvable polynomial list.
080     * @return leftGB(F) a left Groebner base of F.
081     */
082    @SuppressWarnings("unchecked")
083    public List<GenSolvablePolynomial<C>> leftGB(int modv, List<GenSolvablePolynomial<C>> F) {
084        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F);
085        G = PolynomialList.castToSolvableList(PolyUtil.<C> monic(PolynomialList.castToList(G)));
086        if (G.size() <= 1) {
087            return G;
088        }
089        GenSolvablePolynomialRing<C> ring = G.get(0).ring;
090        if (!ring.coFac.isField() && ring.coFac.isCommutative()) {
091            throw new IllegalArgumentException("coefficients not from a field: " + ring.coFac.toScript());
092        }
093        PairList<C> pairlist = strategy.create(modv, ring);
094        pairlist.put(PolynomialList.castToList(G));
095        logger.info("start " + pairlist);
096
097        GenSolvablePolynomial<C> pi, pj, S, H;
098        Pair<C> pair;
099        while (pairlist.hasNext()) {
100            pair = pairlist.removeNext();
101            if (pair == null) {
102                continue;
103            }
104            pi = (GenSolvablePolynomial<C>) pair.pi;
105            pj = (GenSolvablePolynomial<C>) pair.pj;
106            if (debug) {
107                logger.info("pi    = " + pi.leadingExpVector());
108                logger.info("pj    = " + pj.leadingExpVector());
109            }
110
111            S = sred.leftSPolynomial(pi, pj);
112            if (S.isZERO()) {
113                pair.setZero();
114                continue;
115            }
116            if (debug) {
117                logger.info("ht(S) = " + S.leadingExpVector());
118            }
119
120            H = sred.leftNormalform(G, S);
121            if (H.isZERO()) {
122                pair.setZero();
123                continue;
124            }
125            if (debug) {
126                logger.info("ht(H) = " + H.leadingExpVector());
127                //logger.info("ht(H) = " + H.leadingExpVector() + ", lc(H) = " + H.leadingBaseCoefficient().toScript());
128            }
129
130            H = H.monic();
131            if (H.isONE()) {
132                G.clear();
133                G.add(H);
134                return G; // since no threads are activated
135            }
136            if (debug) {
137                // logger.info("H = " + H);
138                logger.info("#monic(H) = " + H.length());
139            }
140            if (H.length() > 0) {
141                //l++;
142                G.add(H);
143                pairlist.put(H);
144            }
145        }
146        logger.debug("#sequential list = " + G.size());
147        G = leftMinimalGB(G);
148        logger.info("end " + pairlist);
149        return G;
150    }
151
152
153    /**
154     * Solvable Extended Groebner base using critical pair class.
155     * @param modv module variable number.
156     * @param F solvable polynomial list.
157     * @return a container for an extended left Groebner base of F.
158     */
159    @Override
160    @SuppressWarnings("unchecked")
161    public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) {
162        if (F == null || F.isEmpty()) {
163            throw new IllegalArgumentException("null or empty F not allowed");
164        }
165        List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>();
166        List<List<GenSolvablePolynomial<C>>> F2G = new ArrayList<List<GenSolvablePolynomial<C>>>();
167        List<List<GenSolvablePolynomial<C>>> G2F = new ArrayList<List<GenSolvablePolynomial<C>>>();
168        PairList<C> pairlist = null;
169        boolean oneInGB = false;
170        int len = F.size();
171
172        List<GenSolvablePolynomial<C>> row = null;
173        List<GenSolvablePolynomial<C>> rows = null;
174        List<GenSolvablePolynomial<C>> rowh = null;
175        GenSolvablePolynomialRing<C> ring = null;
176        GenSolvablePolynomial<C> p, H;
177
178        int nzlen = 0;
179        for (GenSolvablePolynomial<C> f : F) {
180            if (f.length() > 0) {
181                nzlen++;
182            }
183            if (ring == null) {
184                ring = f.ring;
185            }
186        }
187        GenSolvablePolynomial<C> mone = ring.getONE(); //.negate();
188        int k = 0;
189        ListIterator<GenSolvablePolynomial<C>> it = F.listIterator();
190        while (it.hasNext()) {
191            p = it.next();
192            if (p.length() > 0) {
193                row = new ArrayList<GenSolvablePolynomial<C>>(nzlen);
194                for (int j = 0; j < nzlen; j++) {
195                    row.add(null);
196                }
197                //C c = p.leadingBaseCoefficient();
198                //c = c.inverse();
199                //p = p.multiply( c );
200                row.set(k, mone); //.multiply(c) );
201                k++;
202                if (p.isUnit()) {
203                    G.clear();
204                    G.add(p);
205                    G2F.clear();
206                    G2F.add(row);
207                    oneInGB = true;
208                    break;
209                }
210                G.add(p);
211                G2F.add(row);
212                if (pairlist == null) {
213                    //pairlist = new CriticalPairList<C>( modv, p.ring );
214                    pairlist = strategy.create(modv, p.ring);
215                }
216                // putOne not required
217                pairlist.put(p);
218            } else {
219                len--;
220            }
221        }
222        SolvableExtendedGB<C> exgb;
223        if (len <= 1 || oneInGB) {
224            // adjust F2G
225            for (GenSolvablePolynomial<C> f : F) {
226                row = new ArrayList<GenSolvablePolynomial<C>>(G.size());
227                for (int j = 0; j < G.size(); j++) {
228                    row.add(null);
229                }
230                H = sred.leftNormalform(row, G, f);
231                if (!H.isZERO()) {
232                    logger.error("nonzero H = " + H);
233                }
234                F2G.add(row);
235            }
236            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
237            //System.out.println("exgb 1 = " + exgb);
238            return exgb;
239        }
240        logger.info("start " + pairlist);
241
242        Pair<C> pair;
243        int i, j;
244        GenSolvablePolynomial<C> pi, pj, S, x, y;
245        //GenPolynomial<C> z;
246        while (pairlist.hasNext() && !oneInGB) {
247            pair = pairlist.removeNext();
248            if (pair == null) {
249                //pairlist.update(); // ?
250                continue;
251            }
252            i = pair.i;
253            j = pair.j;
254            pi = (GenSolvablePolynomial<C>) pair.pi;
255            pj = (GenSolvablePolynomial<C>) pair.pj;
256            if (debug) {
257                logger.info("i, pi    = " + i + ", " + pi);
258                logger.info("j, pj    = " + j + ", " + pj);
259            }
260
261            rows = new ArrayList<GenSolvablePolynomial<C>>(G.size());
262            for (int m = 0; m < G.size(); m++) {
263                rows.add(null);
264            }
265            S = sred.leftSPolynomial(rows, i, pi, j, pj);
266            if (debug) {
267                logger.debug("is reduction S = " + sred.isLeftReductionNF(rows, G, ring.getZERO(), S));
268            }
269            if (S.isZERO()) {
270                pair.setZero();
271                //pairlist.update( pair, S );
272                // do not add to G2F
273                continue;
274            }
275            if (debug) {
276                logger.debug("ht(S) = " + S.leadingExpVector());
277            }
278
279            rowh = new ArrayList<GenSolvablePolynomial<C>>(G.size());
280            for (int m = 0; m < G.size(); m++) {
281                rowh.add(null);
282            }
283            H = sred.leftNormalform(rowh, G, S);
284            if (debug) {
285                //System.out.println("H = " + H);
286                logger.debug("is reduction H = " + sred.isLeftReductionNF(rowh, G, S, H));
287            }
288            if (H.isZERO()) {
289                pair.setZero();
290                //pairlist.update( pair, H );
291                // do not add to G2F
292                continue;
293            }
294            if (debug) {
295                logger.debug("ht(H) = " + H.leadingExpVector());
296            }
297
298            row = new ArrayList<GenSolvablePolynomial<C>>(G.size() + 1);
299            for (int m = 0; m < G.size(); m++) {
300                x = rows.get(m);
301                if (x != null) {
302                    //System.out.println("ms = " + m + " " + x);
303                    x = (GenSolvablePolynomial<C>) x.negate();
304                }
305                y = rowh.get(m);
306                if (y != null) {
307                    y = (GenSolvablePolynomial<C>) y.negate();
308                    //System.out.println("mh = " + m + " " + y);
309                }
310                if (x == null) {
311                    x = y;
312                } else {
313                    x = (GenSolvablePolynomial<C>) x.sum(y);
314                }
315                //System.out.println("mx = " + m + " " + x);
316                row.add(x);
317            }
318            if (debug) {
319                logger.debug("is reduction 0+sum(row,G) == H : "
320                                + sred.isLeftReductionNF(row, G, H, ring.getZERO()));
321            }
322            row.add(null);
323
324            //  H = H.monic();
325            C c = H.leadingBaseCoefficient();
326            c = c.inverse();
327            H = H.multiply(c);
328            // 1*c*row, leads to wrong method dispatch:
329            row = PolynomialList.<C> castToSolvableList(blas.scalarProduct(mone.multiply(c),
330                            PolynomialList.<C> castToList(row)));
331            row.set(G.size(), mone);
332            if (H.isONE()) {
333                // pairlist.record( pair, H );
334                // G.clear(); 
335                G.add(H);
336                G2F.add(row);
337                oneInGB = true;
338                break;
339            }
340            if (debug) {
341                logger.debug("H = " + H);
342            }
343            G.add(H);
344            //pairlist.update( pair, H );
345            pairlist.put(H);
346            G2F.add(row);
347        }
348        if (debug) {
349            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
350            logger.info("exgb unnorm = " + exgb);
351        }
352        G2F = normalizeMatrix(F.size(), G2F);
353        if (debug) {
354            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
355            logger.info("exgb nonmin = " + exgb);
356            boolean t2 = isLeftReductionMatrix(exgb);
357            logger.debug("exgb t2 = " + t2);
358        }
359        exgb = minimalSolvableExtendedGB(F.size(), G, G2F);
360        G = exgb.G;
361        G2F = exgb.G2F;
362        logger.debug("#sequential list = " + G.size());
363        logger.info("end " + pairlist);
364        // setup matrices F and F2G
365        for (GenSolvablePolynomial<C> f : F) {
366            row = new ArrayList<GenSolvablePolynomial<C>>(G.size());
367            for (int m = 0; m < G.size(); m++) {
368                row.add(null);
369            }
370            H = sred.leftNormalform(row, G, f);
371            if (!H.isZERO()) {
372                logger.error("nonzero H = " + H);
373            }
374            F2G.add(row);
375        }
376        logger.info("extGB end");
377        return new SolvableExtendedGB<C>(F, G, F2G, G2F);
378    }
379
380
381    /**
382     * Twosided Groebner base using pairlist class.
383     * @param modv number of module variables.
384     * @param Fp solvable polynomial list.
385     * @return tsGB(Fp) a twosided Groebner base of Fp.
386     */
387    @SuppressWarnings("unchecked")
388    public List<GenSolvablePolynomial<C>> twosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) {
389        List<GenSolvablePolynomial<C>> F = normalizeZerosOnes(Fp);
390        F = PolynomialList.castToSolvableList(PolyUtil.<C> monic(PolynomialList.castToList(F)));
391        if (F.size() < 1) { // 0 not 1
392            return F;
393        }
394        if (F.size() == 1 && F.get(0).isONE()) {
395            return F;
396        }
397        GenSolvablePolynomialRing<C> ring = F.get(0).ring;
398        if (!ring.coFac.isField() && ring.coFac.isCommutative()) {
399            throw new IllegalArgumentException("coefficients not from a field");
400        }
401        // add also coefficient generators
402        List<GenSolvablePolynomial<C>> X;
403        X = PolynomialList.castToSolvableList(ring.generators(modv)); 
404        logger.info("right multipliers = " + X);
405        List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(F.size() * (1 + X.size()));
406        G.addAll(F);
407        logger.info("right multipy: G = " + G);
408        GenSolvablePolynomial<C> p, q;
409        for (int i = 0; i < G.size(); i++) { // G changes
410            p = G.get(i);
411            for (GenSolvablePolynomial<C> x : X) {
412                //x = X.get(j);
413                if (x.isONE()) {
414                    continue;
415                }
416                q = p.multiply(x);
417                logger.info("right multipy: p = " + p + ", x = " + x + ", q = " + q);
418                q = sred.leftNormalform(G, q);
419                q = q.monic();
420                logger.info("right multipy: red(q) = " + q);
421                if (!q.isZERO()) {
422                    //System.out.println("q generating: = " + q + ", p = " + p + ", x = " + x);
423                    if (q.isONE()) {
424                        //System.out.println("G generated so far: " + G);
425                        G.clear();
426                        G.add(q);
427                        return G; // since no threads are activated
428                    }
429                    if (!G.contains(q)) { // why?
430                       G.add(q);
431                    } else {
432                       logger.info("right multipy contained: q = " + q);
433                    } 
434                }
435            }
436        }
437        //System.out.println("G generated = " + G);
438        PairList<C> pairlist = strategy.create(modv, ring);
439        pairlist.put(PolynomialList.castToList(G));
440
441        if (G.size() <= 1) { // 1 ok
442            return G; // since no threads are activated
443        }
444        logger.info("twosided start " + pairlist);
445
446        Pair<C> pair;
447        GenSolvablePolynomial<C> pi, pj, S, H;
448        while (pairlist.hasNext()) {
449            pair = pairlist.removeNext();
450            if (pair == null) {
451                continue;
452            }
453
454            pi = (GenSolvablePolynomial<C>) pair.pi;
455            pj = (GenSolvablePolynomial<C>) pair.pj;
456            if (debug) {
457                logger.debug("pi    = " + pi);
458                logger.debug("pj    = " + pj);
459            }
460
461            S = sred.leftSPolynomial(pi, pj);
462            if (S.isZERO()) {
463                pair.setZero();
464                continue;
465            }
466            if (debug) {
467                logger.debug("ht(S) = " + S.leadingExpVector());
468            }
469
470            H = sred.leftNormalform(G, S);
471            if (H.isZERO()) {
472                pair.setZero();
473                continue;
474            }
475            if (debug) {
476                logger.debug("ht(H) = " + H.leadingExpVector());
477            }
478
479            H = H.monic();
480            if (H.isONE()) {
481                G.clear();
482                G.add(H);
483                return G; // since no threads are activated
484            }
485            if (debug) {
486                logger.debug("H = " + H);
487            }
488            if (H.length() > 0) {
489                G.add(H);
490                pairlist.put(H);
491                //System.out.println("H generated = " + H);
492                for (GenSolvablePolynomial<C> x : X) {
493                    //x = X.get(j);
494                    if (x.isONE()) {
495                        continue;
496                    }
497                    q = H.multiply(x);
498                    p = sred.leftNormalform(G, q);
499                    if (!p.isZERO()) {
500                        //System.out.println("p generated = " + p + ", x = " + x);
501                        p = p.monic();
502                        if (p.isONE()) {
503                            G.clear();
504                            G.add(p);
505                            return G; // since no threads are activated
506                        }
507                        G.add(p);
508                        pairlist.put(p);
509                    }
510                }
511                //System.out.println("G generated = " + G);
512            }
513        }
514        logger.debug("#sequential list = " + G.size());
515        G = leftMinimalGB(G);
516        logger.info("twosided end " + pairlist);
517        return G;
518    }
519
520
521    /**
522     * Normalize M. Make all rows the same size and make certain column elements
523     * zero.
524     * @param M a reduction matrix.
525     * @return normalized M.
526     */
527    public List<List<GenSolvablePolynomial<C>>> normalizeMatrix(int flen,
528                    List<List<GenSolvablePolynomial<C>>> M) {
529        if (M == null) {
530            return M;
531        }
532        if (M.size() == 0) {
533            return M;
534        }
535        List<List<GenSolvablePolynomial<C>>> N = new ArrayList<List<GenSolvablePolynomial<C>>>();
536        List<List<GenSolvablePolynomial<C>>> K = new ArrayList<List<GenSolvablePolynomial<C>>>();
537        int len = M.get(M.size() - 1).size(); // longest row
538        // pad / extend rows
539        for (List<GenSolvablePolynomial<C>> row : M) {
540            List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row);
541            for (int i = row.size(); i < len; i++) {
542                nrow.add(null);
543            }
544            N.add(nrow);
545        }
546        // System.out.println("norm N fill = " + N);
547        // make zero columns
548        int k = flen;
549        for (int i = 0; i < N.size(); i++) { // 0
550            List<GenSolvablePolynomial<C>> row = N.get(i);
551            if (debug) {
552                logger.info("row = " + row);
553            }
554            K.add(row);
555            if (i < flen) { // skip identity part
556                continue;
557            }
558            List<GenSolvablePolynomial<C>> xrow;
559            GenSolvablePolynomial<C> a;
560            //System.out.println("norm i = " + i);
561            for (int j = i + 1; j < N.size(); j++) {
562                List<GenSolvablePolynomial<C>> nrow = N.get(j);
563                //System.out.println("nrow j = " +j + ", " + nrow);
564                if (k < nrow.size()) { // always true
565                    a = nrow.get(k);
566                    //System.out.println("k, a = " + k + ", " + a);
567                    if (a != null && !a.isZERO()) { // a*row + nrow, leads to wrong method dispatch
568                        List<GenPolynomial<C>> yrow = blas.scalarProduct(a,
569                                        PolynomialList.<C> castToList(row));
570                        yrow = blas.vectorAdd(yrow, PolynomialList.<C> castToList(nrow));
571                        xrow = PolynomialList.<C> castToSolvableList(yrow);
572                        N.set(j, xrow);
573                    }
574                }
575            }
576            k++;
577        }
578        //System.out.println("norm K reduc = " + K);
579        // truncate 
580        N.clear();
581        for (List<GenSolvablePolynomial<C>> row : K) {
582            List<GenSolvablePolynomial<C>> tr = new ArrayList<GenSolvablePolynomial<C>>();
583            for (int i = 0; i < flen; i++) {
584                tr.add(row.get(i));
585            }
586            N.add(tr);
587        }
588        K = N;
589        //System.out.println("norm K trunc = " + K);
590        return K;
591    }
592
593
594    /**
595     * Test if M is a left reduction matrix.
596     * @param exgb an SolvableExtendedGB container.
597     * @return true, if exgb contains a left reduction matrix, else false.
598     */
599    @Override
600    public boolean isLeftReductionMatrix(SolvableExtendedGB<C> exgb) {
601        if (exgb == null) {
602            return true;
603        }
604        return isLeftReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F);
605    }
606
607
608    /**
609     * Minimal solvable extended groebner basis.
610     * @param Gp a left Groebner base.
611     * @param M a left reduction matrix, is modified.
612     * @return a (partially) reduced left Groebner base of Gp in a container.
613     */
614    public SolvableExtendedGB<C> minimalSolvableExtendedGB(int flen, List<GenSolvablePolynomial<C>> Gp,
615                    List<List<GenSolvablePolynomial<C>>> M) {
616        if (Gp == null) {
617            return null; //new SolvableExtendedGB<C>(null,Gp,null,M);
618        }
619        if (Gp.size() <= 1) {
620            return new SolvableExtendedGB<C>(null, Gp, null, M);
621        }
622        List<GenSolvablePolynomial<C>> G;
623        List<GenSolvablePolynomial<C>> F;
624        G = new ArrayList<GenSolvablePolynomial<C>>(Gp);
625        F = new ArrayList<GenSolvablePolynomial<C>>(Gp.size());
626
627        List<List<GenSolvablePolynomial<C>>> Mg;
628        List<List<GenSolvablePolynomial<C>>> Mf;
629        Mg = new ArrayList<List<GenSolvablePolynomial<C>>>(M.size());
630        Mf = new ArrayList<List<GenSolvablePolynomial<C>>>(M.size());
631        List<GenSolvablePolynomial<C>> row;
632        for (List<GenSolvablePolynomial<C>> r : M) {
633            // must be copied also
634            row = new ArrayList<GenSolvablePolynomial<C>>(r);
635            Mg.add(row);
636        }
637        row = null;
638
639        GenSolvablePolynomial<C> a;
640        ExpVector e;
641        ExpVector f;
642        GenSolvablePolynomial<C> p;
643        boolean mt;
644        ListIterator<GenSolvablePolynomial<C>> it;
645        ArrayList<Integer> ix = new ArrayList<Integer>();
646        ArrayList<Integer> jx = new ArrayList<Integer>();
647        int k = 0;
648        //System.out.println("flen, Gp, M = " + flen + ", " + Gp.size() + ", " + M.size() );
649        while (G.size() > 0) {
650            a = G.remove(0);
651            e = a.leadingExpVector();
652
653            it = G.listIterator();
654            mt = false;
655            while (it.hasNext() && !mt) {
656                p = it.next();
657                f = p.leadingExpVector();
658                mt = e.multipleOf(f);
659            }
660            it = F.listIterator();
661            while (it.hasNext() && !mt) {
662                p = it.next();
663                f = p.leadingExpVector();
664                mt = e.multipleOf(f);
665            }
666            //System.out.println("k, mt = " + k + ", " + mt);
667            if (!mt) {
668                F.add(a);
669                ix.add(k);
670            } else { // drop polynomial and corresponding row and column
671                // F.add( a.ring.getZERO() );
672                jx.add(k);
673            }
674            k++;
675        }
676        if (debug) {
677            logger.debug("ix, #M, jx = " + ix + ", " + Mg.size() + ", " + jx);
678        }
679        int fix = -1; // copied polys
680        // copy Mg to Mf as indicated by ix
681        for (int i = 0; i < ix.size(); i++) {
682            int u = ix.get(i);
683            if (u >= flen && fix == -1) {
684                fix = Mf.size();
685            }
686            //System.out.println("copy u, fix = " + u + ", " + fix);
687            if (u >= 0) {
688                row = Mg.get(u);
689                Mf.add(row);
690            }
691        }
692        if (F.size() <= 1 || fix == -1) {
693            return new SolvableExtendedGB<C>(null, F, null, Mf);
694        }
695        // must return, since extended normalform has not correct order of polys
696        /*
697        G = F;
698        F = new ArrayList<GenSolvablePolynomial<C>>( G.size() );
699        List<GenSolvablePolynomial<C>> temp;
700        k = 0;
701        final int len = G.size();
702        while ( G.size() > 0 ) {
703            a = G.remove(0);
704            if ( k >= fix ) { // dont touch copied polys
705               row = Mf.get( k );
706               //System.out.println("doing k = " + k + ", " + a);
707               // must keep order, but removed polys missing
708               temp = new ArrayList<GenPolynomial<C>>( len );
709               temp.addAll( F );
710               temp.add( a.ring.getZERO() ); // ??
711               temp.addAll( G );
712               //System.out.println("row before = " + row);
713               a = sred.leftNormalform( row, temp, a );
714               //System.out.println("row after  = " + row);
715            }
716            F.add( a );
717            k++;
718        }
719        // does Mf need renormalization?
720        */
721        return new SolvableExtendedGB<C>(null, F, null, Mf);
722    }
723
724
725    /**
726     * Right Groebner base using pairlist class. Overides rightGB() via opposite
727     * ring.
728     * @param modv number of module variables.
729     * @param F solvable polynomial list.
730     * @return rightGB(F) a right Groebner base of F.
731     */
732    @Override
733    @SuppressWarnings("unchecked")
734    public List<GenSolvablePolynomial<C>> rightGB(int modv, List<GenSolvablePolynomial<C>> F) {
735        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F);
736        G = PolynomialList.castToSolvableList(PolyUtil.<C> monic(PolynomialList.castToList(G)));
737        if (G.size() <= 1) {
738            return G;
739        }
740        GenSolvablePolynomialRing<C> ring = G.get(0).ring;
741        if (!ring.coFac.isField() && ring.coFac.isCommutative()) {
742            throw new IllegalArgumentException("coefficients not from a field");
743        }
744        PairList<C> pairlist = strategy.create(modv, ring);
745        pairlist.put(PolynomialList.castToList(G));
746        logger.info("start " + pairlist);
747
748        GenSolvablePolynomial<C> pi, pj, S, H;
749        Pair<C> pair;
750        while (pairlist.hasNext()) {
751            pair = pairlist.removeNext();
752            if (pair == null) {
753                continue;
754            }
755            pi = (GenSolvablePolynomial<C>) pair.pi;
756            pj = (GenSolvablePolynomial<C>) pair.pj;
757            if (debug) {
758                logger.info("pi    = " + pi);
759                logger.info("pj    = " + pj);
760            }
761
762            S = sred.rightSPolynomial(pi, pj);
763            if (S.isZERO()) {
764                pair.setZero();
765                continue;
766            }
767            if (debug) {
768                logger.info("ht(S) = " + S.leadingExpVector());
769            }
770
771            H = sred.rightNormalform(G, S);
772            if (H.isZERO()) {
773                pair.setZero();
774                continue;
775            }
776            if (debug) {
777                logger.info("ht(H) = " + H.leadingExpVector());
778            }
779
780            H = H.monic();
781            if (H.isONE()) {
782                G.clear();
783                G.add(H);
784                return G; // since no threads are activated
785            }
786            if (debug) {
787                logger.info("H = " + H);
788            }
789            if (H.length() > 0) {
790                //l++;
791                G.add(H);
792                pairlist.put(H);
793            }
794        }
795        logger.debug("#sequential list = " + G.size());
796        G = rightMinimalGB(G);
797        logger.info("end " + pairlist);
798        return G;
799    }
800
801}