001/*
002 * $Id: SolvableSyzygyAbstract.java 4104 2012-08-18 10:00:59Z kredel $
003 */
004
005package edu.jas.gbmod;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.Iterator;
011import java.util.List;
012import java.util.Map;
013
014import org.apache.log4j.Logger;
015
016import edu.jas.gb.Reduction;
017import edu.jas.gb.ReductionSeq;
018import edu.jas.gb.SolvableExtendedGB;
019import edu.jas.gb.SolvableGroebnerBase;
020import edu.jas.gb.SolvableGroebnerBaseSeq;
021import edu.jas.gb.SolvableReduction;
022import edu.jas.gb.SolvableReductionSeq;
023import edu.jas.poly.ExpVector;
024import edu.jas.poly.GenPolynomial;
025import edu.jas.poly.GenSolvablePolynomial;
026import edu.jas.poly.GenSolvablePolynomialRing;
027import edu.jas.poly.ModuleList;
028import edu.jas.poly.PolynomialList;
029import edu.jas.structure.RingElem;
030import edu.jas.vector.BasicLinAlg;
031
032
033/**
034 * Syzygy class for solvable polynomials. Implements Syzygy computations and
035 * tests.
036 * @param <C> coefficient type
037 * @author Heinz Kredel
038 */
039
040public class SolvableSyzygyAbstract<C extends RingElem<C>> implements SolvableSyzygy<C> {
041
042
043    private static final Logger logger = Logger.getLogger(SolvableSyzygyAbstract.class);
044
045
046    private final boolean debug = logger.isDebugEnabled();
047
048
049    /**
050     * Solvable reduction engine.
051     */
052    protected SolvableReduction<C> sred;
053
054
055    /**
056     * Reduction engine.
057     */
058    protected Reduction<C> red;
059
060
061    /**
062     * Linear algebra engine.
063     */
064    protected BasicLinAlg<GenPolynomial<C>> blas;
065
066
067    /**
068     * Constructor.
069     */
070    public SolvableSyzygyAbstract() {
071        red = new ReductionSeq<C>();
072        sred = new SolvableReductionSeq<C>();
073        blas = new BasicLinAlg<GenPolynomial<C>>();
074    }
075
076
077    /**
078     * Left syzygy for left Groebner base.
079     * @param F a Groebner base.
080     * @return leftSyz(F), a basis for the left module of syzygies for F.
081     */
082    public List<List<GenSolvablePolynomial<C>>> leftZeroRelations(List<GenSolvablePolynomial<C>> F) {
083        return leftZeroRelations(0, F);
084    }
085
086
087    /**
088     * Left syzygy for left Groebner base.
089     * @param modv number of module variables.
090     * @param F a Groebner base.
091     * @return leftSyz(F), a basis for the left module of syzygies for F.
092     */
093    public List<List<GenSolvablePolynomial<C>>> leftZeroRelations(int modv, List<GenSolvablePolynomial<C>> F) {
094        List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>();
095        ArrayList<GenSolvablePolynomial<C>> S = new ArrayList<GenSolvablePolynomial<C>>(F.size());
096        for (int i = 0; i < F.size(); i++) {
097            S.add(null);
098        }
099        GenSolvablePolynomial<C> pi, pj, s, h, zero;
100        zero = null;
101        for (int i = 0; i < F.size(); i++) {
102            pi = F.get(i);
103            if (pi != null && zero == null) {
104                zero = pi.ring.getZERO();
105            }
106            for (int j = i + 1; j < F.size(); j++) {
107                pj = F.get(j);
108                //logger.info("p"+i+", p"+j+" = " + pi + ", " +pj);
109
110                if (!red.moduleCriterion(modv, pi, pj)) {
111                    continue;
112                }
113                // if ( ! red.criterion4( pi, pj ) ) continue;
114                ArrayList<GenSolvablePolynomial<C>> row = (ArrayList<GenSolvablePolynomial<C>>) S.clone();
115
116                s = sred.leftSPolynomial(row, i, pi, j, pj);
117                //logger.info("row = " + row);
118                if (s.isZERO()) {
119                    Z.add(row);
120                    continue;
121                }
122
123                h = sred.leftNormalform(row, F, s);
124                if (!h.isZERO()) {
125                    throw new ArithmeticException("Syzygy no leftGB");
126                }
127                if (logger.isDebugEnabled()) {
128                    logger.info("row = " + row);
129                }
130                Z.add(row);
131            }
132        }
133        // set null to zero
134        for (List<GenSolvablePolynomial<C>> vr : Z) {
135            for (int j = 0; j < vr.size(); j++) {
136                if (vr.get(j) == null) {
137                    vr.set(j, zero);
138                }
139            }
140        }
141        return Z;
142    }
143
144
145    /**
146     * Left syzygy for left module Groebner base.
147     * @param M a Groebner base.
148     * @return leftSyz(M), a basis for the left module of syzygies for M.
149     */
150    @SuppressWarnings("unchecked")
151    public ModuleList<C> leftZeroRelations(ModuleList<C> M) {
152        ModuleList<C> N = null;
153        if (M == null || M.list == null) {
154            return N;
155        }
156        if (M.rows == 0 || M.cols == 0) {
157            return N;
158        }
159        GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO();
160        //logger.info("zero = " + zero);
161
162        //ModuleList<C> Np = null;
163        PolynomialList<C> F = M.getPolynomialList();
164        int modv = M.cols; // > 0  
165        logger.info("modv = " + modv);
166        List<List<GenSolvablePolynomial<C>>> G = leftZeroRelations(modv, F.castToSolvableList());
167        //if (G == null) {
168        //    return N;
169        //}
170        List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>();
171        for (int i = 0; i < G.size(); i++) {
172            List<GenSolvablePolynomial<C>> Gi = G.get(i);
173            List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>();
174            // System.out.println("\nG("+i+") = " + G.get(i));
175            for (int j = 0; j < Gi.size(); j++) {
176                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
177                GenSolvablePolynomial<C> p = Gi.get(j);
178                if (p != null) {
179                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
180                    //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() );
181                    if (r.size() == 0) {
182                        Zi.add(zero);
183                    } else if (r.size() == 1) {
184                        GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0];
185                        Zi.add(vi);
186                    } else { // will not happen
187                        throw new RuntimeException("Map.size() > 1 = " + r.size());
188                    }
189                }
190            }
191            //System.out.println("\nZ("+i+") = " + Zi);
192            Z.add(Zi);
193        }
194        N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z);
195        //System.out.println("\n\nN = " + N);
196        return N;
197    }
198
199
200    /**
201     * Test if left syzygy.
202     * @param Z list of sysygies.
203     * @param F a polynomial list.
204     * @return true, if Z is a list of left syzygies for F, else false.
205     */
206    public boolean isLeftZeroRelation(List<List<GenSolvablePolynomial<C>>> Z, List<GenSolvablePolynomial<C>> F) {
207        List<GenPolynomial<C>> Fp = PolynomialList.<C> castToList(F);
208        for (List<GenSolvablePolynomial<C>> row : Z) {
209            // p has wrong type:
210            GenPolynomial<C> p = blas.scalarProduct(PolynomialList.<C> castToList(row), Fp);
211            if (p == null) {
212                continue;
213            }
214            if (!p.isZERO()) {
215                logger.info("is not ZeroRelation = " + p);
216                return false;
217            }
218        }
219        return true;
220    }
221
222
223    /**
224     * Test if right syzygy.
225     * @param Z list of sysygies.
226     * @param F a polynomial list.
227     * @return true, if Z is a list of right syzygies for F, else false.
228     */
229    public boolean isRightZeroRelation(List<List<GenSolvablePolynomial<C>>> Z,
230                    List<GenSolvablePolynomial<C>> F) {
231        List<GenPolynomial<C>> Fp = PolynomialList.<C> castToList(F);
232        for (List<GenSolvablePolynomial<C>> row : Z) {
233            List<GenPolynomial<C>> yrow = PolynomialList.<C> castToList(row);
234            // p has wrong type:
235            GenPolynomial<C> p = blas.scalarProduct(Fp, yrow); // param order
236            if (p == null) {
237                continue;
238            }
239            if (!p.isZERO()) {
240                logger.info("is not ZeroRelation = " + p);
241                return false;
242            }
243        }
244        return true;
245    }
246
247
248    /**
249     * Test if left sysygy of modules
250     * @param Z list of sysygies.
251     * @param F a module list.
252     * @return true, if Z is a list of left syzygies for F, else false.
253     */
254    public boolean isLeftZeroRelation(ModuleList<C> Z, ModuleList<C> F) {
255        if (Z == null || Z.list == null) {
256            return true;
257        }
258        for (List<GenPolynomial<C>> row : Z.list) {
259            List<GenPolynomial<C>> zr = blas.leftScalarProduct(row, F.list);
260            if (!blas.isZero(zr)) {
261                logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr);
262                return false;
263            }
264        }
265        return true;
266    }
267
268
269    /**
270     * Test if right sysygy of modules
271     * @param Z list of sysygies.
272     * @param F a module list.
273     * @return true, if Z is a list of right syzygies for F, else false.
274     */
275    public boolean isRightZeroRelation(ModuleList<C> Z, ModuleList<C> F) {
276        if (Z == null || Z.list == null) {
277            return true;
278        }
279        for (List<GenPolynomial<C>> row : Z.list) {
280            List<GenPolynomial<C>> zr = blas.rightScalarProduct(row, F.list);
281            //List<GenPolynomial<C>> zr = blas.scalarProduct(row,F.list);
282            if (!blas.isZero(zr)) {
283                logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr);
284                return false;
285            }
286        }
287        return true;
288    }
289
290
291    /**
292     * Resolution of a module. Only with direct GBs.
293     * @param M a module list of a Groebner basis.
294     * @return a resolution of M.
295     */
296    public List<SolvResPart<C>> resolution(ModuleList<C> M) {
297        List<SolvResPart<C>> R = new ArrayList<SolvResPart<C>>();
298        ModuleList<C> MM = M;
299        ModuleList<C> GM;
300        ModuleList<C> Z;
301        ModSolvableGroebnerBase<C> msbb = new ModSolvableGroebnerBaseAbstract<C>();
302        while (true) {
303            GM = msbb.leftGB(MM);
304            Z = leftZeroRelations(GM);
305            R.add(new SolvResPart<C>(MM, GM, Z));
306            if (Z == null || Z.list == null || Z.list.size() == 0) {
307                break;
308            }
309            MM = Z;
310        }
311        return R;
312    }
313
314
315    /**
316     * Resolution of a polynomial list. Only with direct GBs.
317     * @param F a polynomial list of a Groebner basis.
318     * @return a resolution of F.
319     */
320    @SuppressWarnings("unchecked")
321    public List // <SolvResPart<C>|SolvResPolPart<C>> 
322      resolution(PolynomialList<C> F) {
323        List<List<GenSolvablePolynomial<C>>> Z;
324        ModuleList<C> Zm;
325        List<GenSolvablePolynomial<C>> G;
326        PolynomialList<C> Gl;
327        SolvableGroebnerBase<C> sbb = new SolvableGroebnerBaseSeq<C>();
328
329        G = sbb.leftGB(F.castToSolvableList());
330        Z = leftZeroRelations(G);
331        Gl = new PolynomialList<C>((GenSolvablePolynomialRing<C>) F.ring, G);
332        Zm = new ModuleList<C>((GenSolvablePolynomialRing<C>) F.ring, Z);
333
334        List R = resolution(Zm);
335        R.add(0, new SolvResPolPart<C>(F, Gl, Zm));
336        return R;
337    }
338
339
340    /**
341     * Resolution of a module.
342     * @param M a module list of an arbitrary basis.
343     * @return a resolution of M.
344     */
345    public List<SolvResPart<C>> resolutionArbitrary(ModuleList<C> M) {
346        List<SolvResPart<C>> R = new ArrayList<SolvResPart<C>>();
347        ModuleList<C> MM = M;
348        ModuleList<C> GM = null;
349        ModuleList<C> Z;
350        //ModSolvableGroebnerBase<C> msbb = new ModSolvableGroebnerBaseAbstract<C>();
351        while (true) {
352            //GM = msbb.leftGB(MM);
353            Z = leftZeroRelationsArbitrary(MM);
354            R.add(new SolvResPart<C>(MM, GM, Z));
355            if (Z == null || Z.list == null || Z.list.size() == 0) {
356                break;
357            }
358            MM = Z;
359        }
360        return R;
361    }
362
363
364    /**
365     * Resolution of a polynomial list.
366     * @param F a polynomial list of an arbitrary basis.
367     * @return a resolution of F.
368     */
369    @SuppressWarnings("unchecked")
370    public List // <SolvResPart<C>|SolvResPolPart<C>> 
371      resolutionArbitrary(PolynomialList<C> F) {
372        List<List<GenSolvablePolynomial<C>>> Z;
373        ModuleList<C> Zm;
374        //List<GenSolvablePolynomial<C>> G;
375        PolynomialList<C> Gl = null;
376        //SolvableGroebnerBase<C> sbb = new SolvableGroebnerBaseSeq<C>();
377
378        //G = sbb.leftGB( F.castToSolvableList() );
379        Z = leftZeroRelationsArbitrary(F.castToSolvableList());
380        //Gl = new PolynomialList<C>((GenSolvablePolynomialRing<C>)F.ring, G);
381        Zm = new ModuleList<C>((GenSolvablePolynomialRing<C>) F.ring, Z);
382
383        List R = resolutionArbitrary(Zm);
384        R.add(0, new SolvResPolPart<C>(F, Gl, Zm));
385        return R;
386    }
387
388
389    /**
390     * Left syzygy module from arbitrary base.
391     * @param F a solvable polynomial list.
392     * @return syz(F), a basis for the module of left syzygies for F.
393     */
394    public List<List<GenSolvablePolynomial<C>>> leftZeroRelationsArbitrary(List<GenSolvablePolynomial<C>> F) {
395        return leftZeroRelationsArbitrary(0, F);
396    }
397
398
399    /**
400     * Left syzygy module from arbitrary base.
401     * @param modv number of module variables.
402     * @param F a solvable polynomial list.
403     * @return syz(F), a basis for the module of left syzygies for F.
404     */
405     @SuppressWarnings("unchecked")
406     public List<List<GenSolvablePolynomial<C>>> leftZeroRelationsArbitrary(int modv,
407                    List<GenSolvablePolynomial<C>> F) {
408        if (F == null) {
409            return null; //leftZeroRelations( modv, F );
410        }
411        if (F.size() <= 1) {
412            return leftZeroRelations(modv, F);
413        }
414        final int lenf = F.size();
415        SolvableGroebnerBaseSeq<C> sgb = new SolvableGroebnerBaseSeq<C>();
416        SolvableExtendedGB<C> exgb = sgb.extLeftGB(F);
417        if (debug) {
418            logger.info("exgb = " + exgb);
419        }
420        if (!sgb.isLeftReductionMatrix(exgb)) {
421            logger.error("is reduction matrix ? false");
422        }
423        List<GenSolvablePolynomial<C>> G = exgb.G;
424        List<List<GenSolvablePolynomial<C>>> G2F = exgb.G2F;
425        List<List<GenSolvablePolynomial<C>>> F2G = exgb.F2G;
426
427        List<List<GenSolvablePolynomial<C>>> sg = leftZeroRelations(modv, G);
428        GenSolvablePolynomialRing<C> ring = G.get(0).ring;
429        ModuleList<C> S = new ModuleList<C>(ring, sg);
430        if (debug) {
431            logger.info("syz = " + S);
432        }
433        if (!isLeftZeroRelation(sg, G)) {
434            logger.error("is syzygy ? false");
435        }
436
437        List<List<GenSolvablePolynomial<C>>> sf;
438        sf = new ArrayList<List<GenSolvablePolynomial<C>>>(sg.size());
439        //List<GenPolynomial<C>> row;
440
441        for (List<GenSolvablePolynomial<C>> r : sg) {
442            Iterator<GenSolvablePolynomial<C>> it = r.iterator();
443            Iterator<List<GenSolvablePolynomial<C>>> jt = G2F.iterator();
444
445            List<GenSolvablePolynomial<C>> rf;
446            rf = new ArrayList<GenSolvablePolynomial<C>>(lenf);
447            for (int m = 0; m < lenf; m++) {
448                rf.add(ring.getZERO());
449            }
450            while (it.hasNext() && jt.hasNext()) {
451                GenSolvablePolynomial<C> si = it.next();
452                List<GenSolvablePolynomial<C>> ai = jt.next();
453                //System.out.println("si = " + si);
454                //System.out.println("ai = " + ai);
455                if (si == null || ai == null) {
456                    continue;
457                }
458                // pi has wrong type:
459                List<GenPolynomial<C>> pi = blas.scalarProduct(si, PolynomialList.<C> castToList(ai));
460                //System.out.println("pi = " + pi);
461                rf = PolynomialList.<C> castToSolvableList(blas.vectorAdd(PolynomialList.<C> castToList(rf),
462                                pi));
463            }
464            if (it.hasNext() || jt.hasNext()) {
465                logger.error("leftZeroRelationsArbitrary wrong sizes");
466            }
467            //System.out.println("\nrf = " + rf + "\n");
468            sf.add(rf);
469        }
470        if (!isLeftZeroRelation(sf, F)) {
471            logger.error("is partial syz sf ? false");
472        }
473
474        List<List<GenSolvablePolynomial<C>>> M;
475        M = new ArrayList<List<GenSolvablePolynomial<C>>>(lenf);
476        for (List<GenSolvablePolynomial<C>> r : F2G) {
477            Iterator<GenSolvablePolynomial<C>> it = r.iterator();
478            Iterator<List<GenSolvablePolynomial<C>>> jt = G2F.iterator();
479
480            List<GenSolvablePolynomial<C>> rf;
481            rf = new ArrayList<GenSolvablePolynomial<C>>(lenf);
482            for (int m = 0; m < lenf; m++) {
483                rf.add(ring.getZERO());
484            }
485            while (it.hasNext() && jt.hasNext()) {
486                GenSolvablePolynomial<C> si = it.next();
487                List<GenSolvablePolynomial<C>> ai = jt.next();
488                //System.out.println("si = " + si);
489                //System.out.println("ai = " + ai);
490                if (si == null || ai == null) {
491                    continue;
492                }
493                //pi has wrong type, should be: List<GenSolvablePolynomial<C>>
494                List<GenPolynomial<C>> pi = blas.scalarProduct(si, PolynomialList.<C> castToList(ai));
495                //System.out.println("pi = " + pi);
496                rf = PolynomialList.<C> castToSolvableList(blas.vectorAdd(PolynomialList.<C> castToList(rf),
497                                pi));
498            }
499            if (it.hasNext() || jt.hasNext()) {
500                logger.error("zeroRelationsArbitrary wrong sizes");
501            }
502            //System.out.println("\nMg Mf = " + rf + "\n");
503            M.add(rf);
504        }
505        //ModuleList<C> ML = new ModuleList<C>( ring, M );
506        //System.out.println("syz ML = " + ML);
507        // debug only:
508        //List<GenSolvablePolynomial<C>> F2 = new ArrayList<GenSolvablePolynomial<C>>( F.size() );
509        /* not true in general
510        List<GenPolynomial<C>> Fp = PolynomialList.<C>castToList(F);
511        for ( List<GenSolvablePolynomial<C>> rr: M ) {
512            GenSolvablePolynomial<C> rrg = PolynomialList.<C>castToSolvableList(blas.scalarProduct(Fp,PolynomialList.<C>castToList(rr)));
513            F2.add( rrg );
514        }
515        PolynomialList<C> pF = new PolynomialList<C>( ring, F );
516        PolynomialList<C> pF2 = new PolynomialList<C>( ring, F2 );
517        if ( ! pF.equals( pF2 ) ) {
518           logger.error("is FAB = F ? false");
519           //System.out.println("pF  = " + pF.list.size());
520           //System.out.println("pF2 = " + pF2.list.size());
521        }
522        */
523        int sflen = sf.size();
524        List<List<GenSolvablePolynomial<C>>> M2;
525        M2 = new ArrayList<List<GenSolvablePolynomial<C>>>(lenf);
526        int i = 0;
527        for (List<GenSolvablePolynomial<C>> ri : M) {
528            List<GenSolvablePolynomial<C>> r2i;
529            r2i = new ArrayList<GenSolvablePolynomial<C>>(ri.size());
530            int j = 0;
531            for (GenSolvablePolynomial<C> rij : ri) {
532                GenSolvablePolynomial<C> p = null;
533                if (i == j) {
534                    p = (GenSolvablePolynomial<C>) ring.getONE().subtract(rij);
535                } else {
536                    if (rij != null) {
537                        p = (GenSolvablePolynomial<C>) rij.negate();
538                    }
539                }
540                r2i.add(p);
541                j++;
542            }
543            M2.add(r2i);
544            if (!blas.isZero(PolynomialList.<C> castToList(r2i))) {
545                sf.add(r2i);
546            }
547            i++;
548        }
549        ModuleList<C> M2L = new ModuleList<C>(ring, M2);
550        if (debug) {
551            logger.debug("syz M2L = " + M2L);
552        }
553
554        if (debug) {
555            ModuleList<C> SF = new ModuleList<C>(ring, sf);
556            logger.debug("syz sf = " + SF);
557            logger.debug("#syz " + sflen + ", " + sf.size());
558        }
559        if (!isLeftZeroRelation(sf, F)) {
560            logger.error("is syz sf ? false");
561        }
562        return sf;
563    }
564
565
566    /**
567     * Left syzygy for arbitrary left module base.
568     * @param M an arbitrary base.
569     * @return leftSyz(M), a basis for the left module of syzygies for M.
570     */
571    @SuppressWarnings("unchecked")
572    public ModuleList<C> leftZeroRelationsArbitrary(ModuleList<C> M) {
573        ModuleList<C> N = null;
574        if (M == null || M.list == null) {
575            return N;
576        }
577        if (M.rows == 0 || M.cols == 0) {
578            return N;
579        }
580        GenSolvablePolynomial<C> zero = (GenSolvablePolynomial<C>) M.ring.getZERO();
581        //logger.info("zero = " + zero);
582
583        //ModuleList<C> Np = null;
584        PolynomialList<C> F = M.getPolynomialList();
585        int modv = M.cols; // > 0  
586        logger.info("modv = " + modv);
587        List<List<GenSolvablePolynomial<C>>> G = leftZeroRelationsArbitrary(modv, F.castToSolvableList());
588        if (G == null) {
589            return N;
590        }
591        List<List<GenSolvablePolynomial<C>>> Z = new ArrayList<List<GenSolvablePolynomial<C>>>();
592        for (int i = 0; i < G.size(); i++) {
593            List<GenSolvablePolynomial<C>> Gi = G.get(i);
594            List<GenSolvablePolynomial<C>> Zi = new ArrayList<GenSolvablePolynomial<C>>();
595            // System.out.println("\nG("+i+") = " + G.get(i));
596            for (int j = 0; j < Gi.size(); j++) {
597                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
598                GenSolvablePolynomial<C> p = Gi.get(j);
599                if (p != null) {
600                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
601                    //System.out.println("map("+i+","+j+") = " + r + ", size = " + r.size() );
602                    if (r.size() == 0) {
603                        Zi.add(zero);
604                    } else if (r.size() == 1) {
605                        GenSolvablePolynomial<C> vi = (GenSolvablePolynomial<C>) (r.values().toArray())[0];
606                        Zi.add(vi);
607                    } else { // will not happen
608                        throw new RuntimeException("Map.size() > 1 = " + r.size());
609                    }
610                }
611            }
612            //System.out.println("\nZ("+i+") = " + Zi);
613            Z.add(Zi);
614        }
615        N = new ModuleList<C>((GenSolvablePolynomialRing<C>) M.ring, Z);
616        //System.out.println("\n\nN = " + N);
617        return N;
618    }
619
620
621    /**
622     * Right syzygy module from arbitrary base.
623     * @param F a solvable polynomial list.
624     * @return syz(F), a basis for the module of right syzygies for F.
625     */
626    public List<List<GenSolvablePolynomial<C>>> rightZeroRelationsArbitrary(List<GenSolvablePolynomial<C>> F) {
627        return rightZeroRelationsArbitrary(0, F);
628    }
629
630
631    /**
632     * Right syzygy module from arbitrary base.
633     * @param modv number of module variables.
634     * @param F a solvable polynomial list.
635     * @return syz(F), a basis for the module of right syzygies for F.
636     */
637    @SuppressWarnings("unchecked")
638    public List<List<GenSolvablePolynomial<C>>> rightZeroRelationsArbitrary(int modv,
639                    List<GenSolvablePolynomial<C>> F) {
640        GenSolvablePolynomialRing<C> ring = null;
641        for (GenSolvablePolynomial<C> p : F) {
642            if (p != null) {
643                ring = p.ring;
644                break;
645            }
646        }
647        List<List<GenSolvablePolynomial<C>>> Z;
648        if (ring == null) { // all null
649            Z = new ArrayList<List<GenSolvablePolynomial<C>>>(1);
650            Z.add(F);
651            return Z;
652        }
653        GenSolvablePolynomialRing<C> rring = ring.reverse(true);
654        GenSolvablePolynomial<C> q;
655        List<GenSolvablePolynomial<C>> rF;
656        rF = new ArrayList<GenSolvablePolynomial<C>>(F.size());
657        for (GenSolvablePolynomial<C> p : F) {
658            if (p != null) {
659                q = (GenSolvablePolynomial<C>) p.reverse(rring);
660                rF.add(q);
661            }
662        }
663        if (logger.isInfoEnabled()) {
664            PolynomialList<C> pl = new PolynomialList<C>(rring, rF);
665            logger.info("reversed problem = " + pl);
666            //System.out.println("reversed problem = " + pl);
667        }
668        List<List<GenSolvablePolynomial<C>>> rZ = leftZeroRelationsArbitrary(modv, rF);
669        if (debug) {
670            boolean isit = isLeftZeroRelation(rZ, rF);
671            logger.debug("isLeftZeroRelation = " + isit);
672        }
673        GenSolvablePolynomialRing<C> oring = rring.reverse(true);
674        if (debug) {
675            logger.debug("ring == oring: " + ring.equals(oring));
676        }
677        ring = oring;
678        Z = new ArrayList<List<GenSolvablePolynomial<C>>>(rZ.size());
679        for (List<GenSolvablePolynomial<C>> z : rZ) {
680            if (z == null) {
681                continue;
682            }
683            List<GenSolvablePolynomial<C>> s;
684            s = new ArrayList<GenSolvablePolynomial<C>>(z.size());
685            for (GenSolvablePolynomial<C> p : z) {
686                if (p != null) {
687                    q = (GenSolvablePolynomial<C>) p.reverse(ring);
688                    s.add(q);
689                }
690            }
691            Z.add(s);
692        }
693        return Z;
694    }
695
696}
697
698
699/**
700 * Container for module resolution components.
701 * @param <C> coefficient type
702 */
703class SolvResPart<C extends RingElem<C>> implements Serializable {
704
705
706    public final ModuleList<C> module;
707
708
709    public final ModuleList<C> GB;
710
711
712    public final ModuleList<C> syzygy;
713
714
715    /**
716     * SolvResPart.
717     * @param m a module list.
718     * @param g a module list GB.
719     * @param z a syzygy module list.
720     */
721    public SolvResPart(ModuleList<C> m, ModuleList<C> g, ModuleList<C> z) {
722        module = m;
723        GB = g;
724        syzygy = z;
725    }
726
727
728    /**
729     * toString.
730     */
731    @Override
732    public String toString() {
733        StringBuffer s = new StringBuffer("SolvResPart(\n");
734        s.append("module = " + module);
735        s.append("\n GB = " + GB);
736        s.append("\n syzygy = " + syzygy);
737        s.append(")");
738        return s.toString();
739    }
740}
741
742
743/**
744 * Container for polynomial resolution components.
745 * @param <C> coefficient type
746 */
747class SolvResPolPart<C extends RingElem<C>> implements Serializable {
748
749
750    public final PolynomialList<C> ideal;
751
752
753    public final PolynomialList<C> GB;
754
755
756    public final ModuleList<C> syzygy;
757
758
759    /**
760     * SolvResPolPart.
761     * @param m a polynomial list.
762     * @param g a polynomial list GB.
763     * @param z a syzygy module list.
764     */
765    public SolvResPolPart(PolynomialList<C> m, PolynomialList<C> g, ModuleList<C> z) {
766        ideal = m;
767        GB = g;
768        syzygy = z;
769    }
770
771
772    /**
773     * toString.
774     */
775    @Override
776    public String toString() {
777        StringBuffer s = new StringBuffer("SolvResPolPart(\n");
778        s.append("ideal = " + ideal);
779        s.append("\n GB = " + GB);
780        s.append("\n syzygy = " + syzygy);
781        s.append(")");
782        return s.toString();
783    }
784
785}