001    /*
002     * $Id: SyzygyAbstract.java 3584 2011-03-26 11:39:39Z kredel $
003     */
004    
005    package edu.jas.gbmod;
006    
007    
008    import java.io.Serializable;
009    import java.util.ArrayList;
010    import java.util.Iterator;
011    import java.util.List;
012    import java.util.Map;
013    
014    import org.apache.log4j.Logger;
015    
016    import edu.jas.gb.ExtendedGB;
017    import edu.jas.gb.GroebnerBase;
018    import edu.jas.gb.Reduction;
019    import edu.jas.gb.ReductionSeq;
020    import edu.jas.gbufd.GBFactory;
021    import edu.jas.poly.ExpVector;
022    import edu.jas.poly.GenPolynomial;
023    import edu.jas.poly.GenPolynomialRing;
024    import edu.jas.poly.ModuleList;
025    import edu.jas.poly.PolynomialList;
026    import edu.jas.structure.GcdRingElem;
027    import edu.jas.structure.RingElem;
028    import edu.jas.vector.BasicLinAlg;
029    import edu.jas.vector.GenVector;
030    import 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    
039    public 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, zero;
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.clone().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    
375            if (F == null) {
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     */
581    class 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     */
624    class 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    }