Source code

001/*
002 * $Id$
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.LogManager;
013import org.apache.logging.log4j.Logger;
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.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 = LogManager.getLogger(SolvableGroebnerBaseSeq.class);
035
036
037    private static 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) = {}, lc(H) = {}", H.leadingExpVector(), 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 = PolynomialList.<C> castToSolvableList(blas.genVector(nzlen, null));
194                //C c = p.leadingBaseCoefficient();
195                //c = c.inverse();
196                //p = p.multiply( c );
197                row.set(k, mone); //.multiply(c) );
198                k++;
199                if (p.isUnit()) {
200                    G.clear();
201                    G.add(p);
202                    G2F.clear();
203                    G2F.add(row);
204                    oneInGB = true;
205                    break;
206                }
207                G.add(p);
208                G2F.add(row);
209                if (pairlist == null) {
210                    //pairlist = new CriticalPairList<C>( modv, p.ring );
211                    pairlist = strategy.create(modv, p.ring);
212                }
213                // putOne not required
214                pairlist.put(p);
215            } else {
216                len--;
217            }
218        }
219        SolvableExtendedGB<C> exgb;
220        if (len <= 1 || oneInGB) {
221            // adjust F2G
222            for (GenSolvablePolynomial<C> f : F) {
223                row = PolynomialList.<C> castToSolvableList(blas.genVector(G.size(), null));
224                H = sred.leftNormalform(row, G, f);
225                if (!H.isZERO()) {
226                    logger.error("nonzero_1 H = {}, G = {}, f = {}, row = {}", H, G, f, row);
227                }
228                F2G.add(row);
229            }
230            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
231            //System.out.println("exgb 1 = " + exgb);
232            return exgb;
233        }
234        logger.info("start {}", pairlist);
235
236        Pair<C> pair;
237        int i, j;
238        GenSolvablePolynomial<C> pi, pj, S; // x, y;
239        //GenPolynomial<C> z;
240        while (pairlist.hasNext() && !oneInGB) {
241            pair = pairlist.removeNext();
242            if (pair == null) {
243                //pairlist.update(); // ?
244                continue;
245            }
246            i = pair.i;
247            j = pair.j;
248            pi = (GenSolvablePolynomial<C>) pair.pi;
249            pj = (GenSolvablePolynomial<C>) pair.pj;
250            if (debug) {
251                logger.info("i, pi    = {}, {}", i, pi);
252                logger.info("j, pj    = {}, {}", j, pj);
253            }
254
255            rows = PolynomialList.<C> castToSolvableList(blas.genVector(G.size(), null));
256            S = sred.leftSPolynomial(rows, i, pi, j, pj);
257            if (debug) {
258                logger.debug("is reduction S = {}", sred.isLeftReductionNF(rows, G, ring.getZERO(), S));
259            }
260            if (S.isZERO()) {
261                pair.setZero();
262                //pairlist.update( pair, S );
263                // do not add to G2F
264                continue;
265            }
266            if (debug) {
267                logger.debug("ht(S) = {}", S.leadingExpVector());
268            }
269
270            rowh = PolynomialList.<C> castToSolvableList(blas.genVector(G.size(), null));
271            H = sred.leftNormalform(rowh, G, S);
272            if (debug) {
273                //System.out.println("H = " + H);
274                logger.debug("is reduction H = {}", sred.isLeftReductionNF(rowh, G, S, H));
275            }
276            if (H.isZERO()) {
277                pair.setZero();
278                //pairlist.update( pair, H );
279                // do not add to G2F
280                continue;
281            }
282            if (debug) {
283                logger.debug("ht(H) = {}", H.leadingExpVector());
284            }
285
286            row = PolynomialList.<C> castToSolvableList(blas.vectorCombineOld(
287                            PolynomialList.<C> castToList(rows), PolynomialList.<C> castToList(rowh)));
288            // if (debug) {
289            //     logger.debug("is reduction 0+sum(row,G) == H : "
290            //                     + sred.isLeftReductionNF(row, G, H, ring.getZERO()));
291            // }
292
293            //H = H.leftMonic(); //left
294            C c = H.leadingBaseCoefficient();
295            c = c.inverse();
296            H = H.multiplyLeft(c);
297            // 1*c*row, leads to wrong method dispatch:
298            row = PolynomialList.<C> castToSolvableList(
299                            blas.scalarProduct(mone.multiply(c), PolynomialList.<C> castToList(row)));
300            row.set(G.size(), mone);
301            if (H.isONE()) {
302                // pairlist.record( pair, H );
303                // G.clear(); 
304                G.add(H);
305                G2F.add(row);
306                oneInGB = true;
307                break;
308            }
309            if (debug) {
310                logger.debug("H = {}", H);
311            }
312            G.add(H);
313            //pairlist.update( pair, H );
314            pairlist.put(H);
315            G2F.add(row);
316        }
317        if (debug) {
318            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
319            logger.info("exgb unnorm = {}", exgb);
320        }
321        G2F = normalizeMatrix(F.size(), G2F);
322        if (debug) {
323            exgb = new SolvableExtendedGB<C>(F, G, F2G, G2F);
324            logger.info("exgb nonmin = {}", exgb);
325            boolean t2 = isLeftReductionMatrix(exgb);
326            logger.debug("exgb t2 = {}", t2);
327        }
328        exgb = minimalSolvableExtendedGB(F.size(), G, G2F);
329        G = exgb.G;
330        G2F = exgb.G2F;
331        logger.debug("#sequential list = {}", G.size());
332        logger.info("end {}", pairlist);
333        // setup matrices F and F2G
334        for (GenSolvablePolynomial<C> f : F) {
335            row = PolynomialList.<C> castToSolvableList(blas.genVector(G.size(), null));
336            H = sred.leftNormalform(row, G, f);
337            if (!H.isZERO()) {
338                logger.error("nonzero_end H = {}, G = {}, f = {}, row = {}", H, G, f, row);
339                logger.error("nonzero_end ring = {}", H.ring.toScript());
340                //throw new RuntimeException("nonzero_end H = " + H);
341            }
342            F2G.add(row);
343        }
344        logger.info("extLeftGB end");
345        return new SolvableExtendedGB<C>(F, G, F2G, G2F);
346    }
347
348
349    /**
350     * Twosided Groebner base using pairlist class.
351     * @param modv number of module variables.
352     * @param Fp solvable polynomial list.
353     * @return tsGB(Fp) a twosided Groebner base of Fp.
354     */
355    @SuppressWarnings("unchecked")
356    public List<GenSolvablePolynomial<C>> twosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) {
357        List<GenSolvablePolynomial<C>> F = normalizeZerosOnes(Fp);
358        F = PolynomialList.castToSolvableList(PolyUtil.<C> monic(PolynomialList.castToList(F)));
359        if (F.size() < 1) { // 0 not 1
360            return F;
361        }
362        if (F.size() == 1 && F.get(0).isONE()) {
363            return F;
364        }
365        GenSolvablePolynomialRing<C> ring = F.get(0).ring;
366        if (!ring.coFac.isField() && ring.coFac.isCommutative()) {
367            throw new IllegalArgumentException("coefficients not from a field");
368        }
369        // add also coefficient generators
370        List<GenSolvablePolynomial<C>> X;
371        X = PolynomialList.castToSolvableList(ring.generators(modv));
372        logger.info("right multipliers = {}", X);
373        List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(F.size() * (1 + X.size()));
374        G.addAll(F);
375        logger.info("right multiply: G = {}", G);
376        GenSolvablePolynomial<C> p, q;
377        for (int i = 0; i < G.size(); i++) { // G changes
378            p = G.get(i);
379            for (GenSolvablePolynomial<C> x : X) {
380                //x = X.get(j);
381                if (x.isONE()) {
382                    continue;
383                }
384                q = p.multiply(x);
385                logger.info("right multiply: p = {}, x = {}, q = {}", p, x, q);
386                q = sred.leftNormalform(G, q);
387                q = q.monic();
388                logger.info("right multiply: red(q) = {}", q);
389                if (!q.isZERO()) {
390                    //System.out.println("q generating: = " + q + ", p = " + p + ", x = " + x);
391                    if (q.isONE()) {
392                        //System.out.println("G generated so far: " + G);
393                        G.clear();
394                        G.add(q);
395                        return G; // since no threads are activated
396                    }
397                    if (!G.contains(q)) { // why?
398                        G.add(q);
399                    } else {
400                        logger.info("right multiply contained: q = {}", q);
401                    }
402                }
403            }
404        }
405        if (G.size() <= 1) { // 1 ok
406            return G; // since no threads are activated
407        }
408        //System.out.println("G generated = " + G);
409        PairList<C> pairlist = strategy.create(modv, ring);
410        pairlist.put(PolynomialList.castToList(G));
411        logger.info("twosided start {}", pairlist);
412
413        Pair<C> pair;
414        GenSolvablePolynomial<C> pi, pj, S, H;
415        while (pairlist.hasNext()) {
416            pair = pairlist.removeNext();
417            if (pair == null) {
418                continue;
419            }
420
421            pi = (GenSolvablePolynomial<C>) pair.pi;
422            pj = (GenSolvablePolynomial<C>) pair.pj;
423            if (debug) {
424                logger.debug("pi    = {}", pi);
425                logger.debug("pj    = {}", pj);
426            }
427
428            S = sred.leftSPolynomial(pi, pj);
429            if (S.isZERO()) {
430                pair.setZero();
431                continue;
432            }
433            if (debug) {
434                logger.debug("ht(S) = {}", S.leadingExpVector());
435            }
436
437            H = sred.leftNormalform(G, S);
438            if (H.isZERO()) {
439                pair.setZero();
440                continue;
441            }
442            if (debug) {
443                logger.debug("ht(H) = {}", H.leadingExpVector());
444            }
445
446            H = H.monic();
447            if (H.isONE()) {
448                G.clear();
449                G.add(H);
450                return G; // since no threads are activated
451            }
452            if (debug) {
453                logger.debug("H = {}", H);
454            }
455            if (H.length() > 0) {
456                G.add(H);
457                pairlist.put(H);
458                //System.out.println("H generated = " + H);
459                for (GenSolvablePolynomial<C> x : X) {
460                    //x = X.get(j);
461                    if (x.isONE()) {
462                        continue;
463                    }
464                    q = H.multiply(x);
465                    p = sred.leftNormalform(G, q);
466                    if (!p.isZERO()) {
467                        //System.out.println("p generated = " + p + ", x = " + x);
468                        p = p.monic();
469                        if (p.isONE()) {
470                            G.clear();
471                            G.add(p);
472                            return G; // since no threads are activated
473                        }
474                        G.add(p);
475                        pairlist.put(p);
476                    }
477                }
478                //System.out.println("G generated = " + G);
479            }
480        }
481        logger.debug("#sequential list = {}", G.size());
482        G = leftMinimalGB(G);
483        logger.info("twosided end {}", pairlist);
484        return G;
485    }
486
487
488    /**
489     * Normalize M. Make all rows the same size and make certain column elements
490     * zero.
491     * @param M a reduction matrix.
492     * @return normalized M.
493     */
494    public List<List<GenSolvablePolynomial<C>>> normalizeMatrix(int flen,
495                    List<List<GenSolvablePolynomial<C>>> M) {
496        if (M == null) {
497            return M;
498        }
499        if (M.size() == 0) {
500            return M;
501        }
502        List<List<GenSolvablePolynomial<C>>> N = new ArrayList<List<GenSolvablePolynomial<C>>>();
503        List<List<GenSolvablePolynomial<C>>> K = new ArrayList<List<GenSolvablePolynomial<C>>>();
504        int len = M.get(M.size() - 1).size(); // longest row
505        // pad / extend rows
506        for (List<GenSolvablePolynomial<C>> row : M) {
507            List<GenSolvablePolynomial<C>> nrow = new ArrayList<GenSolvablePolynomial<C>>(row);
508            for (int i = row.size(); i < len; i++) {
509                nrow.add(null);
510            }
511            N.add(nrow);
512        }
513        // System.out.println("norm N fill = " + N);
514        // make zero columns
515        int k = flen;
516        for (int i = 0; i < N.size(); i++) { // 0
517            List<GenSolvablePolynomial<C>> row = N.get(i);
518            if (debug) {
519                logger.info("row = {}", row);
520            }
521            K.add(row);
522            if (i < flen) { // skip identity part
523                continue;
524            }
525            List<GenSolvablePolynomial<C>> xrow;
526            GenSolvablePolynomial<C> a;
527            //System.out.println("norm i = " + i);
528            for (int j = i + 1; j < N.size(); j++) {
529                List<GenSolvablePolynomial<C>> nrow = N.get(j);
530                //System.out.println("nrow j = " +j + ", " + nrow);
531                if (k < nrow.size()) { // always true
532                    a = nrow.get(k);
533                    //System.out.println("k, a = " + k + ", " + a);
534                    if (a != null && !a.isZERO()) { // a*row + nrow, leads to wrong method dispatch
535                        List<GenPolynomial<C>> yrow = blas.scalarProduct(a,
536                                        PolynomialList.<C> castToList(row));
537                        yrow = blas.vectorAdd(yrow, PolynomialList.<C> castToList(nrow));
538                        xrow = PolynomialList.<C> castToSolvableList(yrow);
539                        N.set(j, xrow);
540                    }
541                }
542            }
543            k++;
544        }
545        //System.out.println("norm K reduc = {}", K);
546        // truncate 
547        N.clear();
548        for (List<GenSolvablePolynomial<C>> row : K) {
549            List<GenSolvablePolynomial<C>> tr = new ArrayList<GenSolvablePolynomial<C>>();
550            for (int i = 0; i < flen; i++) {
551                tr.add(row.get(i));
552            }
553            N.add(tr);
554        }
555        K = N;
556        //System.out.println("norm K trunc = " + K);
557        return K;
558    }
559
560
561    /**
562     * Test if M is a left reduction matrix.
563     * @param exgb an SolvableExtendedGB container.
564     * @return true, if exgb contains a left reduction matrix, else false.
565     */
566    @Override
567    public boolean isLeftReductionMatrix(SolvableExtendedGB<C> exgb) {
568        if (exgb == null) {
569            return true;
570        }
571        return isLeftReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F);
572    }
573
574
575    /**
576     * Minimal solvable extended groebner basis.
577     * @param Gp a left Groebner base.
578     * @param M a left reduction matrix, is modified.
579     * @return a (partially) reduced left Groebner base of Gp in a container.
580     */
581    public SolvableExtendedGB<C> minimalSolvableExtendedGB(int flen, List<GenSolvablePolynomial<C>> Gp,
582                    List<List<GenSolvablePolynomial<C>>> M) {
583        if (Gp == null) {
584            return null; //new SolvableExtendedGB<C>(null,Gp,null,M);
585        }
586        if (Gp.size() <= 1) {
587            return new SolvableExtendedGB<C>(null, Gp, null, M);
588        }
589        List<GenSolvablePolynomial<C>> G;
590        List<GenSolvablePolynomial<C>> F;
591        G = new ArrayList<GenSolvablePolynomial<C>>(Gp);
592        F = new ArrayList<GenSolvablePolynomial<C>>(Gp.size());
593
594        List<List<GenSolvablePolynomial<C>>> Mg;
595        List<List<GenSolvablePolynomial<C>>> Mf;
596        Mg = new ArrayList<List<GenSolvablePolynomial<C>>>(M.size());
597        Mf = new ArrayList<List<GenSolvablePolynomial<C>>>(M.size());
598        List<GenSolvablePolynomial<C>> row;
599        for (List<GenSolvablePolynomial<C>> r : M) {
600            // must be copied also
601            row = new ArrayList<GenSolvablePolynomial<C>>(r);
602            Mg.add(row);
603        }
604        row = null;
605
606        GenSolvablePolynomial<C> a;
607        ExpVector e;
608        ExpVector f;
609        GenSolvablePolynomial<C> p;
610        boolean mt;
611        ListIterator<GenSolvablePolynomial<C>> it;
612        ArrayList<Integer> ix = new ArrayList<Integer>();
613        ArrayList<Integer> jx = new ArrayList<Integer>();
614        int k = 0;
615        //System.out.println("flen, Gp, M = " + flen + ", " + Gp.size() + ", " + M.size() );
616        while (G.size() > 0) {
617            a = G.remove(0);
618            e = a.leadingExpVector();
619
620            it = G.listIterator();
621            mt = false;
622            while (it.hasNext() && !mt) {
623                p = it.next();
624                f = p.leadingExpVector();
625                mt = e.multipleOf(f);
626            }
627            it = F.listIterator();
628            while (it.hasNext() && !mt) {
629                p = it.next();
630                f = p.leadingExpVector();
631                mt = e.multipleOf(f);
632            }
633            //System.out.println("k, mt = " + k + ", " + mt);
634            if (!mt) {
635                F.add(a);
636                ix.add(k);
637            } else { // drop polynomial and corresponding row and column
638                // F.add( a.ring.getZERO() );
639                jx.add(k);
640            }
641            k++;
642        }
643        if (debug) {
644            logger.debug("ix, #M, jx = {}, {}, {}", ix, Mg.size(), jx);
645        }
646        int fix = -1; // copied polys
647        // copy Mg to Mf as indicated by ix
648        for (int i = 0; i < ix.size(); i++) {
649            int u = ix.get(i);
650            if (u >= flen && fix == -1) {
651                fix = Mf.size();
652            }
653            //System.out.println("copy u, fix = " + u + ", " + fix);
654            if (u >= 0) {
655                row = Mg.get(u);
656                Mf.add(row);
657            }
658        }
659        if (F.size() <= 1 || fix == -1) {
660            return new SolvableExtendedGB<C>(null, F, null, Mf);
661        }
662        // must return, since extended normalform has not correct order of polys
663        /*
664        G = F;
665        F = new ArrayList<GenSolvablePolynomial<C>>( G.size() );
666        List<GenSolvablePolynomial<C>> temp;
667        k = 0;
668        final int len = G.size();
669        while ( G.size() > 0 ) {
670            a = G.remove(0);
671            if ( k >= fix ) { // dont touch copied polys
672               row = Mf.get( k );
673               //System.out.println("doing k = " + k + ", " + a);
674               // must keep order, but removed polys missing
675               temp = new ArrayList<GenPolynomial<C>>( len );
676               temp.addAll( F );
677               temp.add( a.ring.getZERO() ); // ??
678               temp.addAll( G );
679               //System.out.println("row before = " + row);
680               a = sred.leftNormalform( row, temp, a );
681               //System.out.println("row after  = " + row);
682            }
683            F.add( a );
684            k++;
685        }
686        // does Mf need renormalization?
687        */
688        return new SolvableExtendedGB<C>(null, F, null, Mf);
689    }
690
691
692    /**
693     * Right Groebner base via right reduction using pairlist class. Overrides
694     * rightGB() via opposite ring.
695     * @param modv number of module variables.
696     * @param F solvable polynomial list.
697     * @return rightGB(F) a right Groebner base of F.
698     */
699    @Override
700    @SuppressWarnings("unchecked")
701    public List<GenSolvablePolynomial<C>> rightGB(int modv, List<GenSolvablePolynomial<C>> F) {
702        List<GenSolvablePolynomial<C>> G = normalizeZerosOnes(F);
703        G = PolynomialList.castToSolvableList(PolyUtil.<C> rightMonic(PolynomialList.castToList(G)));
704        //G = PolyUtil.<C> rightMonic(G);
705        if (G.size() <= 1) {
706            return G;
707        }
708        GenSolvablePolynomialRing<C> ring = G.get(0).ring;
709        if (!ring.coFac.isField() && ring.coFac.isCommutative()) {
710            throw new IllegalArgumentException("coefficients not from a field");
711        }
712        PairList<C> pairlist = strategy.create(modv, ring);
713        pairlist.put(PolynomialList.castToList(G));
714        logger.info("start {}", pairlist);
715
716        GenSolvablePolynomial<C> pi, pj, S, H;
717        Pair<C> pair;
718        while (pairlist.hasNext()) {
719            pair = pairlist.removeNext();
720            if (pair == null) {
721                continue;
722            }
723            pi = (GenSolvablePolynomial<C>) pair.pi;
724            pj = (GenSolvablePolynomial<C>) pair.pj;
725            if (debug) {
726                logger.info("pi    = {}", pi);
727                logger.info("pj    = {}", pj);
728            }
729
730            S = sred.rightSPolynomial(pi, pj);
731            if (S.isZERO()) {
732                pair.setZero();
733                continue;
734            }
735            if (debug) {
736                logger.info("ht(S) = {}", S.leadingExpVector());
737                //logger.info("S = {}", S);
738            }
739
740            H = sred.rightNormalform(G, S);
741            if (H.isZERO()) {
742                pair.setZero();
743                continue;
744            }
745            if (debug) {
746                logger.info("ht(H) = {}", H.leadingExpVector());
747            }
748
749            H = H.rightMonic();
750            if (H.isONE()) {
751                G.clear();
752                G.add(H);
753                return G; // since no threads are activated
754            }
755            if (debug) {
756                logger.info("H = {}", H);
757            }
758            if (H.length() > 0) {
759                //l++;
760                G.add(H);
761                pairlist.put(H);
762            }
763        }
764        logger.debug("#sequential list = {}", G.size());
765        //G = rightMinimalGB(G);
766        logger.info("end {}", pairlist);
767        return G;
768    }
769
770}