Source code

001/*
002 * $Id: SolvableGroebnerBaseSeq.java 5869 2018-07-20 15:53:10Z kredel $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.ListIterator;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenSolvablePolynomial;
018import edu.jas.poly.GenSolvablePolynomialRing;
019import edu.jas.poly.QLRSolvablePolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.poly.PolynomialList;
022import edu.jas.structure.RingElem;
023
024
025/**
026 * Solvable Groebner bases sequential algorithms. Implements common left, right
027 * and twosided Groebner bases and left, right and twosided GB tests.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032public class SolvableGroebnerBaseSeq<C extends RingElem<C>> extends SolvableGroebnerBaseAbstract<C> {
033
034
035    private static final Logger logger = LogManager.getLogger(SolvableGroebnerBaseSeq.class);
036
037
038    private static final boolean debug = logger.isDebugEnabled();
039
040
041    /**
042     * Constructor.
043     */
044    public SolvableGroebnerBaseSeq() {
045        super();
046    }
047
048
049    /**
050     * Constructor.
051     * @param sred Solvable reduction engine
052     */
053    public SolvableGroebnerBaseSeq(SolvableReduction<C> sred) {
054        super(sred);
055    }
056
057
058    /**
059     * Constructor.
060     * @param pl pair selection strategy
061     */
062    public SolvableGroebnerBaseSeq(PairList<C> pl) {
063        super(pl);
064    }
065
066
067    /**
068     * Constructor.
069     * @param sred Solvable reduction engine
070     * @param pl pair selection strategy
071     */
072    public SolvableGroebnerBaseSeq(SolvableReduction<C> sred, PairList<C> pl) {
073        super(sred, pl);
074    }
075
076
077    /**
078     * Left Groebner base using pairlist class.
079     * @param modv number of module variables.
080     * @param F solvable polynomial list.
081     * @return leftGB(F) a left Groebner base of F.
082     */
083    @SuppressWarnings("unchecked")
084    public List<GenSolvablePolynomial<C>> leftGB(int modv, List<GenSolvablePolynomial<C>> F) {
085        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F);
086        G = PolynomialList.castToSolvableList(PolyUtil.<C> monic(PolynomialList.castToList(G)));
087        if (G.size() <= 1) {
088            return G;
089        }
090        GenSolvablePolynomialRing<C> ring = G.get(0).ring;
091        if (!ring.coFac.isField() && ring.coFac.isCommutative()) {
092            throw new IllegalArgumentException("coefficients not from a field: " + ring.coFac.toScript());
093        }
094        PairList<C> pairlist = strategy.create(modv, ring);
095        pairlist.put(PolynomialList.castToList(G));
096        logger.info("start " + pairlist);
097
098        GenSolvablePolynomial<C> pi, pj, S, H;
099        Pair<C> pair;
100        while (pairlist.hasNext()) {
101            pair = pairlist.removeNext();
102            if (pair == null) {
103                continue;
104            }
105            pi = (GenSolvablePolynomial<C>) pair.pi;
106            pj = (GenSolvablePolynomial<C>) pair.pj;
107            if (debug) {
108                logger.info("pi    = " + pi.leadingExpVector());
109                logger.info("pj    = " + pj.leadingExpVector());
110            }
111
112            S = sred.leftSPolynomial(pi, pj);
113            if (S.isZERO()) {
114                pair.setZero();
115                continue;
116            }
117            if (debug) {
118                logger.info("ht(S) = " + S.leadingExpVector());
119            }
120
121            H = sred.leftNormalform(G, S);
122            if (H.isZERO()) {
123                pair.setZero();
124                continue;
125            }
126            if (debug) {
127                logger.info("ht(H) = " + H.leadingExpVector());
128                //logger.info("ht(H) = " + H.leadingExpVector() + ", lc(H) = " + H.leadingBaseCoefficient().toScript());
129            }
130
131            H = H.monic();
132            if (H.isONE()) {
133                G.clear();
134                G.add(H);
135                return G; // since no threads are activated
136            }
137            if (debug) {
138                // logger.info("H = " + H);
139                logger.info("#monic(H) = " + H.length());
140            }
141            if (H.length() > 0) {
142                //l++;
143                G.add(H);
144                pairlist.put(H);
145            }
146        }
147        logger.debug("#sequential list = " + G.size());
148        G = leftMinimalGB(G);
149        logger.info("end " + pairlist);
150        return G;
151    }
152
153
154    /**
155     * Solvable Extended Groebner base using critical pair class.
156     * @param modv module variable number.
157     * @param F solvable polynomial list.
158     * @return a container for an extended left Groebner base of F.
159     */
160    @Override
161    @SuppressWarnings("unchecked")
162    public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) {
163        if (F == null || F.isEmpty()) {
164            throw new IllegalArgumentException("null or empty F not allowed");
165        }
166        List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>();
167        List<List<GenSolvablePolynomial<C>>> F2G = new ArrayList<List<GenSolvablePolynomial<C>>>();
168        List<List<GenSolvablePolynomial<C>>> G2F = new ArrayList<List<GenSolvablePolynomial<C>>>();
169        PairList<C> pairlist = null;
170        boolean oneInGB = false;
171        int len = F.size();
172
173        List<GenSolvablePolynomial<C>> row = null;
174        List<GenSolvablePolynomial<C>> rows = null;
175        List<GenSolvablePolynomial<C>> rowh = null;
176        GenSolvablePolynomialRing<C> ring = null;
177        GenSolvablePolynomial<C> p, H;
178
179        int nzlen = 0;
180        for (GenSolvablePolynomial<C> f : F) {
181            if (f.length() > 0) {
182                nzlen++;
183            }
184            if (ring == null) {
185                ring = f.ring;
186            }
187        }
188        GenSolvablePolynomial<C> mone = ring.getONE(); //.negate();
189        int k = 0;
190        ListIterator<GenSolvablePolynomial<C>> it = F.listIterator();
191        while (it.hasNext()) {
192            p = it.next();
193            if (p.length() > 0) {
194                row = new ArrayList<GenSolvablePolynomial<C>>(nzlen);
195                for (int j = 0; j < nzlen; j++) {
196                    row.add(null);
197                }
198                //C c = p.leadingBaseCoefficient();
199                //c = c.inverse();
200                //p = p.multiply( c );
201                row.set(k, mone); //.multiply(c) );
202                k++;
203                if (p.isUnit()) {
204                    G.clear();
205                    G.add(p);
206                    G2F.clear();
207                    G2F.add(row);
208                    oneInGB = true;
209                    break;
210                }
211                G.add(p);
212                G2F.add(row);
213                if (pairlist == null) {
214                    //pairlist = new CriticalPairList<C>( modv, p.ring );
215                    pairlist = strategy.create(modv, p.ring);
216                }
217                // putOne not required
218                pairlist.put(p);
219            } else {
220                len--;
221            }
222        }
223        SolvableExtendedGB<C> exgb;
224        if (len <= 1 || oneInGB) {
225            // adjust F2G
226            for (GenSolvablePolynomial<C> f : F) {
227                row = new ArrayList<GenSolvablePolynomial<C>>(G.size());
228                for (int j = 0; j < G.size(); j++) {
229                    row.add(null);
230                }
231                H = sred.leftNormalform(row, G, f);
232                if (!H.isZERO()) {
233                    logger.error("nonzero H = " + H);
234                }
235                F2G.add(row);
236            }
237            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
238            //System.out.println("exgb 1 = " + exgb);
239            return exgb;
240        }
241        logger.info("start " + pairlist);
242
243        Pair<C> pair;
244        int i, j;
245        GenSolvablePolynomial<C> pi, pj, S, x, y;
246        //GenPolynomial<C> z;
247        while (pairlist.hasNext() && !oneInGB) {
248            pair = pairlist.removeNext();
249            if (pair == null) {
250                //pairlist.update(); // ?
251                continue;
252            }
253            i = pair.i;
254            j = pair.j;
255            pi = (GenSolvablePolynomial<C>) pair.pi;
256            pj = (GenSolvablePolynomial<C>) pair.pj;
257            if (debug) {
258                logger.info("i, pi    = " + i + ", " + pi);
259                logger.info("j, pj    = " + j + ", " + pj);
260            }
261
262            rows = new ArrayList<GenSolvablePolynomial<C>>(G.size());
263            for (int m = 0; m < G.size(); m++) {
264                rows.add(null);
265            }
266            S = sred.leftSPolynomial(rows, i, pi, j, pj);
267            if (debug) {
268                logger.debug("is reduction S = " + sred.isLeftReductionNF(rows, G, ring.getZERO(), S));
269            }
270            if (S.isZERO()) {
271                pair.setZero();
272                //pairlist.update( pair, S );
273                // do not add to G2F
274                continue;
275            }
276            if (debug) {
277                logger.debug("ht(S) = " + S.leadingExpVector());
278            }
279
280            rowh = new ArrayList<GenSolvablePolynomial<C>>(G.size());
281            for (int m = 0; m < G.size(); m++) {
282                rowh.add(null);
283            }
284            H = sred.leftNormalform(rowh, G, S);
285            if (debug) {
286                //System.out.println("H = " + H);
287                logger.debug("is reduction H = " + sred.isLeftReductionNF(rowh, G, S, H));
288            }
289            if (H.isZERO()) {
290                pair.setZero();
291                //pairlist.update( pair, H );
292                // do not add to G2F
293                continue;
294            }
295            if (debug) {
296                logger.debug("ht(H) = " + H.leadingExpVector());
297            }
298
299            row = new ArrayList<GenSolvablePolynomial<C>>(G.size() + 1);
300            for (int m = 0; m < G.size(); m++) {
301                x = rows.get(m);
302                if (x != null) {
303                    //System.out.println("ms = " + m + " " + x);
304                    x = (GenSolvablePolynomial<C>) x.negate();
305                }
306                y = rowh.get(m);
307                if (y != null) {
308                    y = (GenSolvablePolynomial<C>) y.negate();
309                    //System.out.println("mh = " + m + " " + y);
310                }
311                if (x == null) {
312                    x = y;
313                } else {
314                    x = (GenSolvablePolynomial<C>) x.sum(y);
315                }
316                //System.out.println("mx = " + m + " " + x);
317                row.add(x);
318            }
319            if (debug) {
320                logger.debug("is reduction 0+sum(row,G) == H : "
321                                + sred.isLeftReductionNF(row, G, H, ring.getZERO()));
322            }
323            row.add(null);
324
325            //  H = H.monic();
326            C c = H.leadingBaseCoefficient();
327            c = c.inverse();
328            H = H.multiply(c);
329            // 1*c*row, leads to wrong method dispatch:
330            row = PolynomialList.<C> castToSolvableList(blas.scalarProduct(mone.multiply(c),
331                            PolynomialList.<C> castToList(row)));
332            row.set(G.size(), mone);
333            if (H.isONE()) {
334                // pairlist.record( pair, H );
335                // G.clear(); 
336                G.add(H);
337                G2F.add(row);
338                oneInGB = true;
339                break;
340            }
341            if (debug) {
342                logger.debug("H = " + H);
343            }
344            G.add(H);
345            //pairlist.update( pair, H );
346            pairlist.put(H);
347            G2F.add(row);
348        }
349        if (debug) {
350            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
351            logger.info("exgb unnorm = " + exgb);
352        }
353        G2F = normalizeMatrix(F.size(), G2F);
354        if (debug) {
355            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
356            logger.info("exgb nonmin = " + exgb);
357            boolean t2 = isLeftReductionMatrix(exgb);
358            logger.debug("exgb t2 = " + t2);
359        }
360        exgb = minimalSolvableExtendedGB(F.size(), G, G2F);
361        G = exgb.G;
362        G2F = exgb.G2F;
363        logger.debug("#sequential list = " + G.size());
364        logger.info("end " + pairlist);
365        // setup matrices F and F2G
366        for (GenSolvablePolynomial<C> f : F) {
367            row = new ArrayList<GenSolvablePolynomial<C>>(G.size());
368            for (int m = 0; m < G.size(); m++) {
369                row.add(null);
370            }
371            H = sred.leftNormalform(row, G, f);
372            if (!H.isZERO()) {
373                logger.error("nonzero H = " + H);
374            }
375            F2G.add(row);
376        }
377        logger.info("extGB end");
378        return new SolvableExtendedGB<C>(F, G, F2G, G2F);
379    }
380
381
382    /**
383     * Twosided Groebner base using pairlist class.
384     * @param modv number of module variables.
385     * @param Fp solvable polynomial list.
386     * @return tsGB(Fp) a twosided Groebner base of Fp.
387     */
388    @SuppressWarnings("unchecked")
389    public List<GenSolvablePolynomial<C>> twosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) {
390        List<GenSolvablePolynomial<C>> F = normalizeZerosOnes(Fp);
391        F = PolynomialList.castToSolvableList(PolyUtil.<C> monic(PolynomialList.castToList(F)));
392        if (F.size() < 1) { // 0 not 1
393            return F;
394        }
395        if (F.size() == 1 && F.get(0).isONE()) {
396            return F;
397        }
398        GenSolvablePolynomialRing<C> ring = F.get(0).ring;
399        if (!ring.coFac.isField() && ring.coFac.isCommutative()) {
400            throw new IllegalArgumentException("coefficients not from a field");
401        }
402        // add also coefficient generators
403        List<GenSolvablePolynomial<C>> X;
404        X = PolynomialList.castToSolvableList(ring.generators(modv)); 
405        logger.info("right multipliers = " + X);
406        List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(F.size() * (1 + X.size()));
407        G.addAll(F);
408        logger.info("right multipy: G = " + G);
409        GenSolvablePolynomial<C> p, q;
410        for (int i = 0; i < G.size(); i++) { // G changes
411            p = G.get(i);
412            for (GenSolvablePolynomial<C> x : X) {
413                //x = X.get(j);
414                if (x.isONE()) {
415                    continue;
416                }
417                q = p.multiply(x);
418                logger.info("right multipy: p = " + p + ", x = " + x + ", q = " + q);
419                q = sred.leftNormalform(G, q);
420                q = q.monic();
421                logger.info("right multipy: red(q) = " + q);
422                if (!q.isZERO()) {
423                    //System.out.println("q generating: = " + q + ", p = " + p + ", x = " + x);
424                    if (q.isONE()) {
425                        //System.out.println("G generated so far: " + G);
426                        G.clear();
427                        G.add(q);
428                        return G; // since no threads are activated
429                    }
430                    if (!G.contains(q)) { // why?
431                       G.add(q);
432                    } else {
433                       logger.info("right multipy contained: q = " + q);
434                    } 
435                }
436            }
437        }
438        if (G.size() <= 1) { // 1 ok
439            return G; // since no threads are activated
440        }
441        //System.out.println("G generated = " + G);
442        PairList<C> pairlist = strategy.create(modv, ring);
443        pairlist.put(PolynomialList.castToList(G));
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 via right reduction using pairlist
727     * class. Overides rightGB() via opposite 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}