Source code

001/*
002 * $Id: SyzygyAbstract.java 4125 2012-08-19 19:05:22Z 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.ExtendedGB;
017import edu.jas.gb.GroebnerBase;
018import edu.jas.gb.Reduction;
019import edu.jas.gb.ReductionSeq;
020import edu.jas.gbufd.GBFactory;
021import edu.jas.poly.ExpVector;
022import edu.jas.poly.GenPolynomial;
023import edu.jas.poly.GenPolynomialRing;
024import edu.jas.poly.ModuleList;
025import edu.jas.poly.PolynomialList;
026import edu.jas.structure.GcdRingElem;
027import edu.jas.structure.RingElem;
028import edu.jas.vector.BasicLinAlg;
029import edu.jas.vector.GenVector;
030import edu.jas.vector.GenVectorModul;
031
032
033/**
034 * SyzygyAbstract class. Implements Syzygy computations and tests.
035 * @param <C> coefficient type
036 * @author Heinz Kredel
037 */
038
039public class SyzygyAbstract<C extends GcdRingElem<C>> implements Syzygy<C> {
040
041
042    private static final Logger logger = Logger.getLogger(SyzygyAbstract.class);
043
044
045    private final boolean debug = logger.isDebugEnabled();
046
047
048    /**
049     * Reduction engine.
050     */
051    protected Reduction<C> red;
052
053
054    /**
055     * Linear algebra engine.
056     */
057    protected BasicLinAlg<GenPolynomial<C>> blas;
058
059
060    /**
061     * Constructor.
062     */
063    public SyzygyAbstract() {
064        red = new ReductionSeq<C>();
065        blas = new BasicLinAlg<GenPolynomial<C>>();
066        //gb = new GroebnerBaseSeqPairSeq<C>();
067        //gb = new GroebnerBaseSeq<C>();
068        //gb = GBFactory. getImplementation(); 
069    }
070
071
072    /**
073     * Syzygy module from Groebner base. F must be a Groebner base.
074     * @param F a Groebner base.
075     * @return syz(F), a basis for the module of syzygies for F.
076     */
077    public List<List<GenPolynomial<C>>> zeroRelations(List<GenPolynomial<C>> F) {
078        return zeroRelations(0, F);
079    }
080
081
082    /**
083     * Syzygy module from Groebner base. F must be a Groebner base.
084     * @param modv number of module variables.
085     * @param F a Groebner base.
086     * @return syz(F), a basis for the module of syzygies for F.
087     */
088    public List<List<GenPolynomial<C>>> zeroRelations(int modv, List<GenPolynomial<C>> F) {
089        List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
090        if (F == null) {
091            return Z;
092        }
093        GenVectorModul<GenPolynomial<C>> mfac = null;
094        int i = 0;
095        while (mfac == null && i < F.size()) {
096            GenPolynomial<C> p = F.get(i);
097            if (p != null) {
098                mfac = new GenVectorModul<GenPolynomial<C>>(p.ring, F.size());
099            }
100        }
101        if (mfac == null) {
102            return Z;
103        }
104        GenVector<GenPolynomial<C>> v = mfac.fromList(F);
105        //System.out.println("F = " + F + " v = " + v);
106        return zeroRelations(modv, v);
107    }
108
109
110    /**
111     * Syzygy module from Groebner base. v must be a Groebner base.
112     * @param modv number of module variables.
113     * @param v a Groebner base.
114     * @return syz(v), a basis for the module of syzygies for v.
115     */
116    public List<List<GenPolynomial<C>>> zeroRelations(int modv, GenVector<GenPolynomial<C>> v) {
117
118        List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
119
120        GenVectorModul<GenPolynomial<C>> mfac = v.modul;
121        List<GenPolynomial<C>> F = v.val;
122        GenVector<GenPolynomial<C>> S = mfac.getZERO();
123        GenPolynomial<C> pi, pj, s, h;
124        //zero = mfac.coFac.getZERO();
125        for (int i = 0; i < F.size(); i++) {
126            pi = F.get(i);
127            for (int j = i + 1; j < F.size(); j++) {
128                pj = F.get(j);
129                //logger.info("p"+i+", p"+j+" = " + pi + ", " +pj);
130
131                if (!red.moduleCriterion(modv, pi, pj)) {
132                    continue;
133                }
134                // if ( ! red.criterion4( pi, pj ) ) { continue; }
135                List<GenPolynomial<C>> row = S.copy().val;
136
137                s = red.SPolynomial(row, i, pi, j, pj);
138                if (s.isZERO()) {
139                    Z.add(row);
140                    continue;
141                }
142
143                h = red.normalform(row, F, s);
144                if (!h.isZERO()) {
145                    throw new RuntimeException("Syzygy no GB");
146                }
147                if (debug) {
148                    logger.info("row = " + row.size());
149                }
150                Z.add(row);
151            }
152        }
153        return Z;
154    }
155
156
157    /**
158     * Syzygy module from module Groebner base. M must be a module Groebner
159     * base.
160     * @param M a module Groebner base.
161     * @return syz(M), a basis for the module of syzygies for M.
162     */
163    public ModuleList<C> zeroRelations(ModuleList<C> M) {
164        ModuleList<C> N = M;
165        if (M == null || M.list == null) {
166            return N;
167        }
168        if (M.rows == 0 || M.cols == 0) {
169            return N;
170        }
171        GenPolynomial<C> zero = M.ring.getZERO();
172        //System.out.println("zero = " + zero);
173
174        //ModuleList<C> Np = null;
175        PolynomialList<C> F = M.getPolynomialList();
176        int modv = M.cols; // > 0  
177        //System.out.println("modv = " + modv);
178        List<List<GenPolynomial<C>>> G = zeroRelations(modv, F.list);
179        //if (G == null) {
180        //    return N;
181        //}
182        List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
183        for (int i = 0; i < G.size(); i++) {
184            //F = new PolynomialList(F.ring,(List)G.get(i));
185            List<GenPolynomial<C>> Gi = G.get(i);
186            List<GenPolynomial<C>> Zi = new ArrayList<GenPolynomial<C>>();
187            // System.out.println("\nG("+i+") = " + G.get(i));
188            for (int j = 0; j < Gi.size(); j++) {
189                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
190                GenPolynomial<C> p = Gi.get(j);
191                if (p != null) {
192                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
193                    int s = 0;
194                    for (GenPolynomial<C> vi : r.values()) {
195                        Zi.add(vi);
196                        s++;
197                    }
198                    if (s == 0) {
199                        Zi.add(zero);
200                    } else if (s > 1) { // will not happen
201                        System.out.println("p = " + p);
202                        System.out.println("map(" + i + "," + j + ") = " + r + ", size = " + r.size());
203                        throw new RuntimeException("Map.size() > 1 = " + r.size());
204                    }
205                }
206            }
207            //System.out.println("\nZ("+i+") = " + Zi);
208            Z.add(Zi);
209        }
210        N = new ModuleList<C>(M.ring, Z);
211        //System.out.println("\n\nN = " + N);
212        return N;
213    }
214
215
216    /**
217     * Test if sysygy.
218     * @param Z list of sysygies.
219     * @param F a polynomial list.
220     * @return true, if Z is a list of syzygies for F, else false.
221     */
222
223    public boolean isZeroRelation(List<List<GenPolynomial<C>>> Z, List<GenPolynomial<C>> F) {
224        for (List<GenPolynomial<C>> row : Z) {
225            GenPolynomial<C> p = blas.scalarProduct(row, F);
226            if (p == null) {
227                continue;
228            }
229            if (!p.isZERO()) {
230                logger.info("is not ZeroRelation = " + p.toString(p.ring.getVars()));
231                logger.info("row = " + row);
232                //logger.info("F = " + F);
233                return false;
234            }
235        }
236        return true;
237    }
238
239
240    /**
241     * Test if sysygy of modules.
242     * @param Z list of sysygies.
243     * @param F a module list.
244     * @return true, if Z is a list of syzygies for F, else false.
245     */
246
247    public boolean isZeroRelation(ModuleList<C> Z, ModuleList<C> F) {
248        if (Z == null || Z.list == null) {
249            return true;
250        }
251        for (List<GenPolynomial<C>> row : Z.list) {
252            List<GenPolynomial<C>> zr = blas.leftScalarProduct(row, F.list);
253            if (!blas.isZero(zr)) {
254                logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr);
255                return false;
256            }
257        }
258        return true;
259    }
260
261
262    /**
263     * Resolution of a module. Only with direct GBs.
264     * @param M a module list of a Groebner basis.
265     * @return a resolution of M.
266     */
267    public List<ResPart<C>> resolution(ModuleList<C> M) {
268        List<ResPart<C>> R = new ArrayList<ResPart<C>>();
269        ModuleList<C> MM = M;
270        ModuleList<C> GM;
271        ModuleList<C> Z;
272        ModGroebnerBase<C> mbb = new ModGroebnerBaseAbstract<C>(M.ring.coFac);
273        while (true) {
274            GM = mbb.GB(MM);
275            Z = zeroRelations(GM);
276            R.add(new ResPart<C>(MM, GM, Z));
277            if (Z == null || Z.list == null || Z.list.size() == 0) {
278                break;
279            }
280            MM = Z;
281        }
282        return R;
283    }
284
285
286    /**
287     * Resolution of a polynomial list. Only with direct GBs.
288     * @param F a polynomial list of a Groebner basis.
289     * @return a resolution of F.
290     */
291    public List // <ResPart<C>|ResPolPart<C>>
292    resolution(PolynomialList<C> F) {
293        List<List<GenPolynomial<C>>> Z;
294        ModuleList<C> Zm;
295        List<GenPolynomial<C>> G;
296        PolynomialList<C> Gl;
297
298        GroebnerBase<C> gb = GBFactory.getImplementation(F.ring.coFac);
299        G = gb.GB(F.list);
300        Z = zeroRelations(G);
301        Gl = new PolynomialList<C>(F.ring, G);
302        Zm = new ModuleList<C>(F.ring, Z);
303
304        List R = resolution(Zm); //// <ResPart<C>|ResPolPart<C>>
305        R.add(0, new ResPolPart<C>(F, Gl, Zm));
306        return R;
307    }
308
309
310    /**
311     * Resolution of a polynomial list.
312     * @param F a polynomial list of an arbitrary basis.
313     * @return a resolution of F.
314     */
315    public List // <ResPart<C>|ResPolPart<C>>
316    resolutionArbitrary(PolynomialList<C> F) {
317        List<List<GenPolynomial<C>>> Z;
318        ModuleList<C> Zm;
319        //List<GenPolynomial<C>> G;
320        PolynomialList<C> Gl = null;
321
322        //G = (new GroebnerBaseSeq<C>()).GB( F.list );
323        Z = zeroRelationsArbitrary(F.list);
324        //Gl = new PolynomialList<C>(F.ring, F.list);
325        Zm = new ModuleList<C>(F.ring, Z);
326
327        List R = resolutionArbitrary(Zm); //// <ResPart<C>|ResPolPart<C>>
328        R.add(0, new ResPolPart<C>(F, Gl, Zm));
329        return R;
330    }
331
332
333    /**
334     * Resolution of a module.
335     * @param M a module list of an arbitrary basis.
336     * @return a resolution of M.
337     */
338    public List<ResPart<C>> resolutionArbitrary(ModuleList<C> M) {
339        List<ResPart<C>> R = new ArrayList<ResPart<C>>();
340        ModuleList<C> MM = M;
341        ModuleList<C> GM = null;
342        ModuleList<C> Z;
343        //ModGroebnerBase<C> mbb = new ModGroebnerBaseAbstract<C>(M.ring.coFac);
344        while (true) {
345            //GM = mbb.GB(MM);
346            Z = zeroRelationsArbitrary(MM);
347            R.add(new ResPart<C>(MM, GM, Z));
348            if (Z == null || Z.list == null || Z.list.size() == 0) {
349                break;
350            }
351            MM = Z;
352        }
353        return R;
354    }
355
356
357    /**
358     * Syzygy module from arbitrary base.
359     * @param F a polynomial list.
360     * @return syz(F), a basis for the module of syzygies for F.
361     */
362    public List<List<GenPolynomial<C>>> zeroRelationsArbitrary(List<GenPolynomial<C>> F) {
363        return zeroRelationsArbitrary(0, F);
364    }
365
366
367    /**
368     * Syzygy module from arbitrary base.
369     * @param modv number of module variables.
370     * @param F a polynomial list.
371     * @return syz(F), a basis for the module of syzygies for F.
372     */
373    public List<List<GenPolynomial<C>>> zeroRelationsArbitrary(int modv, List<GenPolynomial<C>> F) {
374        if (F == null) {
375            return new ArrayList<List<GenPolynomial<C>>>();
376            //return zeroRelations(modv, F);
377        }
378        if (F.size() <= 1) {
379            return zeroRelations(modv, F);
380        }
381        GroebnerBase<C> gb = GBFactory.getImplementation(F.get(0).ring.coFac);
382        final int lenf = F.size();
383        ExtendedGB<C> exgb = gb.extGB(F);
384        if (debug) {
385            logger.debug("exgb = " + exgb);
386            if (!gb.isReductionMatrix(exgb)) {
387                logger.error("is reduction matrix ? false");
388            }
389        }
390        List<GenPolynomial<C>> G = exgb.G;
391        List<List<GenPolynomial<C>>> G2F = exgb.G2F;
392        List<List<GenPolynomial<C>>> F2G = exgb.F2G;
393
394        List<List<GenPolynomial<C>>> sg = zeroRelations(modv, G);
395        GenPolynomialRing<C> ring = G.get(0).ring;
396        ModuleList<C> S = new ModuleList<C>(ring, sg);
397        if (debug) {
398            logger.debug("syz = " + S);
399            if (!isZeroRelation(sg, G)) {
400                logger.error("is syzygy ? false");
401            }
402        }
403        List<List<GenPolynomial<C>>> sf;
404        sf = new ArrayList<List<GenPolynomial<C>>>(sg.size());
405        //List<GenPolynomial<C>> row;
406        for (List<GenPolynomial<C>> r : sg) {
407            Iterator<GenPolynomial<C>> it = r.iterator();
408            Iterator<List<GenPolynomial<C>>> jt = G2F.iterator();
409
410            List<GenPolynomial<C>> rf;
411            rf = new ArrayList<GenPolynomial<C>>(lenf);
412            for (int m = 0; m < lenf; m++) {
413                rf.add(ring.getZERO());
414            }
415            while (it.hasNext() && jt.hasNext()) {
416                GenPolynomial<C> si = it.next();
417                List<GenPolynomial<C>> ai = jt.next();
418                //System.out.println("si = " + si);
419                //System.out.println("ai = " + ai);
420                if (si == null || ai == null) {
421                    continue;
422                }
423                List<GenPolynomial<C>> pi = blas.scalarProduct(si, ai);
424                //System.out.println("pi = " + pi);
425                rf = blas.vectorAdd(rf, pi);
426            }
427            if (it.hasNext() || jt.hasNext()) {
428                logger.error("zeroRelationsArbitrary wrong sizes");
429            }
430            //System.out.println("\nrf = " + rf + "\n");
431            sf.add(rf);
432        }
433        List<List<GenPolynomial<C>>> M;
434        M = new ArrayList<List<GenPolynomial<C>>>(lenf);
435        for (List<GenPolynomial<C>> r : F2G) {
436            Iterator<GenPolynomial<C>> it = r.iterator();
437            Iterator<List<GenPolynomial<C>>> jt = G2F.iterator();
438
439            List<GenPolynomial<C>> rf;
440            rf = new ArrayList<GenPolynomial<C>>(lenf);
441            for (int m = 0; m < lenf; m++) {
442                rf.add(ring.getZERO());
443            }
444            while (it.hasNext() && jt.hasNext()) {
445                GenPolynomial<C> si = it.next();
446                List<GenPolynomial<C>> ai = jt.next();
447                //System.out.println("si = " + si);
448                //System.out.println("ai = " + ai);
449                if (si == null || ai == null) {
450                    continue;
451                }
452                List<GenPolynomial<C>> pi = blas.scalarProduct(ai, si);
453                //System.out.println("pi = " + pi);
454                rf = blas.vectorAdd(rf, pi);
455            }
456            if (it.hasNext() || jt.hasNext()) {
457                logger.error("zeroRelationsArbitrary wrong sizes");
458            }
459            //System.out.println("\nMg Mf = " + rf + "\n");
460            M.add(rf);
461        }
462        //ModuleList<C> ML = new ModuleList<C>( ring, M );
463        //System.out.println("syz ML = " + ML);
464        // debug only:
465        /* not true in general
466        List<GenPolynomial<C>> F2 = new ArrayList<GenPolynomial<C>>( F.size() );
467        for ( List<GenPolynomial<C>> rr: M ) {
468            GenPolynomial<C> rrg = blas.scalarProduct( F, rr );
469            F2.add( rrg );
470        }
471        PolynomialList<C> pF = new PolynomialList<C>( ring, F );
472        PolynomialList<C> pF2 = new PolynomialList<C>( ring, F2 );
473        if ( ! pF.equals( pF2 ) ) {
474           logger.error("is FAB = F ? false");
475        }
476        */
477        int sflen = sf.size();
478        List<List<GenPolynomial<C>>> M2;
479        M2 = new ArrayList<List<GenPolynomial<C>>>(lenf);
480        int i = 0;
481        for (List<GenPolynomial<C>> ri : M) {
482            List<GenPolynomial<C>> r2i;
483            r2i = new ArrayList<GenPolynomial<C>>(ri.size());
484            int j = 0;
485            for (GenPolynomial<C> rij : ri) {
486                GenPolynomial<C> p = null;
487                if (i == j) {
488                    p = ring.getONE().subtract(rij);
489                } else {
490                    if (rij != null) {
491                        p = rij.negate();
492                    }
493                }
494                r2i.add(p);
495                j++;
496            }
497            M2.add(r2i);
498            if (!blas.isZero(r2i)) {
499                sf.add(r2i);
500            }
501            i++;
502        }
503        if (debug) {
504            ModuleList<C> M2L = new ModuleList<C>(ring, M2);
505            logger.debug("syz M2L = " + M2L);
506            ModuleList<C> SF = new ModuleList<C>(ring, sf);
507            logger.debug("syz sf = " + SF);
508            logger.debug("#syz " + sflen + ", " + sf.size());
509            if (!isZeroRelation(sf, F)) {
510                logger.error("is syz sf ? false");
511            }
512        }
513        return sf;
514    }
515
516
517    /**
518     * Syzygy module from arbitrary module base.
519     * @param M an arbitrary module base.
520     * @return syz(M), a basis for the module of syzygies for M.
521     */
522    public ModuleList<C> zeroRelationsArbitrary(ModuleList<C> M) {
523        ModuleList<C> N = M;
524        if (M == null || M.list == null) {
525            return N;
526        }
527        if (M.rows == 0 || M.cols == 0) {
528            return N;
529        }
530        GenPolynomial<C> zero = M.ring.getZERO();
531        //System.out.println("zero = " + zero);
532
533        //ModuleList<C> Np = null;
534        PolynomialList<C> F = M.getPolynomialList();
535        int modv = M.cols; // > 0  
536        //System.out.println("modv = " + modv);
537        List<List<GenPolynomial<C>>> G = zeroRelationsArbitrary(modv, F.list);
538        //if (G == null) {
539        //    return N;
540        //}
541        List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
542        for (int i = 0; i < G.size(); i++) {
543            //F = new PolynomialList(F.ring,(List)G.get(i));
544            List<GenPolynomial<C>> Gi = G.get(i);
545            List<GenPolynomial<C>> Zi = new ArrayList<GenPolynomial<C>>();
546            // System.out.println("\nG("+i+") = " + G.get(i));
547            for (int j = 0; j < Gi.size(); j++) {
548                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
549                GenPolynomial<C> p = Gi.get(j);
550                if (p != null) {
551                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
552                    int s = 0;
553                    for (GenPolynomial<C> vi : r.values()) {
554                        Zi.add(vi);
555                        s++;
556                    }
557                    if (s == 0) {
558                        Zi.add(zero);
559                    } else if (s > 1) { // will not happen
560                        System.out.println("p = " + p);
561                        System.out.println("map(" + i + "," + j + ") = " + r + ", size = " + r.size());
562                        throw new RuntimeException("Map.size() > 1 = " + r.size());
563                    }
564                }
565            }
566            //System.out.println("\nZ("+i+") = " + Zi);
567            Z.add(Zi);
568        }
569        N = new ModuleList<C>(M.ring, Z);
570        //System.out.println("\n\nN = " + N);
571        return N;
572    }
573
574}
575
576
577/**
578 * Container for module resolution components.
579 * @param <C> coefficient type
580 */
581class ResPart<C extends RingElem<C>> implements Serializable {
582
583
584    public final ModuleList<C> module;
585
586
587    public final ModuleList<C> GB;
588
589
590    public final ModuleList<C> syzygy;
591
592
593    /**
594     * ResPart.
595     * @param m a module list.
596     * @param g a module list GB.
597     * @param z a syzygy module list.
598     */
599    public ResPart(ModuleList<C> m, ModuleList<C> g, ModuleList<C> z) {
600        module = m;
601        GB = g;
602        syzygy = z;
603    }
604
605
606    /**
607     * toString.
608     */
609    @Override
610    public String toString() {
611        StringBuffer s = new StringBuffer("ResPart(\n");
612        s.append("module = " + module);
613        s.append("\n GB = " + GB);
614        s.append("\n syzygy = " + syzygy);
615        s.append(")");
616        return s.toString();
617    }
618}
619
620
621/**
622 * Container for polynomial resolution components.
623 */
624class ResPolPart<C extends RingElem<C>> implements Serializable {
625
626
627    public final PolynomialList<C> ideal;
628
629
630    public final PolynomialList<C> GB;
631
632
633    public final ModuleList<C> syzygy;
634
635
636    /**
637     * ResPolPart.
638     * @param m a polynomial list.
639     * @param g a polynomial list GB.
640     * @param z a syzygy module list.
641     */
642    public ResPolPart(PolynomialList<C> m, PolynomialList<C> g, ModuleList<C> z) {
643        ideal = m;
644        GB = g;
645        syzygy = z;
646    }
647
648
649    /**
650     * toString.
651     */
652    @Override
653    public String toString() {
654        StringBuffer s = new StringBuffer("ResPolPart(\n");
655        s.append("ideal = " + ideal);
656        s.append("\n GB = " + GB);
657        s.append("\n syzygy = " + syzygy);
658        s.append(")");
659        return s.toString();
660    }
661
662}