Source code

001/*
002 * $Id: SyzygyAbstract.java 5267 2015-07-27 17:57:50Z kredel $
003 */
004
005package edu.jas.gbufd;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Map;
012
013import org.apache.log4j.Logger;
014
015import edu.jas.gb.Reduction;
016import edu.jas.gb.ReductionSeq;
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.ModuleList;
020import edu.jas.poly.PolynomialList;
021import edu.jas.structure.GcdRingElem;
022import edu.jas.structure.RingElem;
023import edu.jas.vector.BasicLinAlg;
024import edu.jas.vector.GenVector;
025import edu.jas.vector.GenVectorModul;
026
027
028/**
029 * SyzygyAbstract class. Implements Syzygy computations and tests.
030 * @param <C> coefficient type
031 * @author Heinz Kredel
032 */
033
034public abstract class SyzygyAbstract<C extends GcdRingElem<C>> implements Syzygy<C> {
035
036
037    private static final Logger logger = Logger.getLogger(SyzygyAbstract.class);
038
039
040    private final boolean debug = logger.isDebugEnabled();
041
042
043    /**
044     * Reduction engine.
045     */
046    protected Reduction<C> red;
047
048
049    /**
050     * Linear algebra engine.
051     */
052    protected BasicLinAlg<GenPolynomial<C>> blas;
053
054
055    /**
056     * Constructor.
057     */
058    public SyzygyAbstract() {
059        red = new ReductionSeq<C>();
060        blas = new BasicLinAlg<GenPolynomial<C>>();
061    }
062
063
064    /**
065     * Syzygy module from Groebner base. F must be a Groebner base.
066     * @param F a Groebner base.
067     * @return syz(F), a basis for the module of syzygies for F.
068     */
069    public List<List<GenPolynomial<C>>> zeroRelations(List<GenPolynomial<C>> F) {
070        return zeroRelations(0, F);
071    }
072
073
074    /**
075     * Syzygy module from Groebner base. F must be a Groebner base.
076     * @param modv number of module variables.
077     * @param F a Groebner base.
078     * @return syz(F), a basis for the module of syzygies for F.
079     */
080    public List<List<GenPolynomial<C>>> zeroRelations(int modv, List<GenPolynomial<C>> F) {
081        List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
082        if (F == null) {
083            return Z;
084        }
085        GenVectorModul<GenPolynomial<C>> mfac = null;
086        int i = 0;
087        while (mfac == null && i < F.size()) {
088            GenPolynomial<C> p = F.get(i);
089            if (p != null) {
090                mfac = new GenVectorModul<GenPolynomial<C>>(p.ring, F.size());
091            }
092        }
093        if (mfac == null) {
094            return Z;
095        }
096        GenVector<GenPolynomial<C>> v = mfac.fromList(F);
097        //System.out.println("F = " + F + " v = " + v);
098        return zeroRelations(modv, v);
099    }
100
101
102    /**
103     * Syzygy module from Groebner base. v must be a Groebner base.
104     * @param modv number of module variables.
105     * @param v a Groebner base.
106     * @return syz(v), a basis for the module of syzygies for v.
107     */
108    public List<List<GenPolynomial<C>>> zeroRelations(int modv, GenVector<GenPolynomial<C>> v) {
109        List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
110        GenVectorModul<GenPolynomial<C>> mfac = v.modul;
111        List<GenPolynomial<C>> F = v.val;
112        GenVector<GenPolynomial<C>> S = mfac.getZERO();
113        GenPolynomial<C> pi, pj, s, h;
114        //zero = mfac.coFac.getZERO();
115        for (int i = 0; i < F.size(); i++) {
116            pi = F.get(i);
117            for (int j = i + 1; j < F.size(); j++) {
118                pj = F.get(j);
119                //logger.info("p"+i+", p"+j+" = " + pi + ", " +pj);
120
121                if (!red.moduleCriterion(modv, pi, pj)) {
122                    continue;
123                }
124                // if ( ! red.criterion4( pi, pj ) ) { continue; }
125                List<GenPolynomial<C>> row = S.copy().val;
126
127                s = red.SPolynomial(row, i, pi, j, pj);
128                if (s.isZERO()) {
129                    Z.add(row);
130                    continue;
131                }
132
133                h = red.normalform(row, F, s);
134                if (!h.isZERO()) {
135                    throw new RuntimeException("Syzygy no GB");
136                }
137                if (debug) {
138                    logger.info("row = " + row.size());
139                }
140                Z.add(row);
141            }
142        }
143        return Z;
144    }
145
146
147    /**
148     * Syzygy module from module Groebner base. M must be a module Groebner
149     * base.
150     * @param M a module Groebner base.
151     * @return syz(M), a basis for the module of syzygies for M.
152     */
153    public ModuleList<C> zeroRelations(ModuleList<C> M) {
154        ModuleList<C> N = M;
155        if (M == null || M.list == null) {
156            return N;
157        }
158        if (M.rows == 0 || M.cols == 0) {
159            return N;
160        }
161        GenPolynomial<C> zero = M.ring.getZERO();
162        //System.out.println("zero = " + zero);
163
164        //ModuleList<C> Np = null;
165        PolynomialList<C> F = M.getPolynomialList();
166        int modv = M.cols; // > 0  
167        //System.out.println("modv = " + modv);
168        List<List<GenPolynomial<C>>> G = zeroRelations(modv, F.list);
169        List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
170        for (int i = 0; i < G.size(); i++) {
171            //F = new PolynomialList(F.ring,(List)G.get(i));
172            List<GenPolynomial<C>> Gi = G.get(i);
173            List<GenPolynomial<C>> Zi = new ArrayList<GenPolynomial<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                GenPolynomial<C> p = Gi.get(j);
178                if (p != null) {
179                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
180                    int s = 0;
181                    for (GenPolynomial<C> vi : r.values()) {
182                        Zi.add(vi);
183                        s++;
184                    }
185                    if (s == 0) {
186                        Zi.add(zero);
187                    } else if (s > 1) { // will not happen
188                        System.out.println("p = " + p);
189                        System.out.println("map(" + i + "," + j + ") = " + r + ", size = " + r.size());
190                        throw new RuntimeException("Map.size() > 1 = " + r.size());
191                    }
192                }
193            }
194            //System.out.println("\nZ("+i+") = " + Zi);
195            Z.add(Zi);
196        }
197        N = new ModuleList<C>(M.ring, Z);
198        //System.out.println("\n\nN = " + N);
199        return N;
200    }
201
202
203    /**
204     * Test if sysygy.
205     * @param Z list of sysygies.
206     * @param F a polynomial list.
207     * @return true, if Z is a list of syzygies for F, else false.
208     */
209
210    public boolean isZeroRelation(List<List<GenPolynomial<C>>> Z, List<GenPolynomial<C>> F) {
211        for (List<GenPolynomial<C>> row : Z) {
212            GenPolynomial<C> p = blas.scalarProduct(row, F);
213            if (p == null) {
214                continue;
215            }
216            if (!p.isZERO()) {
217                logger.info("is not ZeroRelation = " + p.toString(p.ring.getVars()));
218                logger.info("row = " + row);
219                //logger.info("F = " + F);
220                return false;
221            }
222        }
223        return true;
224    }
225
226
227    /**
228     * Test if sysygy of modules.
229     * @param Z list of sysygies.
230     * @param F a module list.
231     * @return true, if Z is a list of syzygies for F, else false.
232     */
233
234    public boolean isZeroRelation(ModuleList<C> Z, ModuleList<C> F) {
235        if (Z == null || Z.list == null) {
236            return true;
237        }
238        for (List<GenPolynomial<C>> row : Z.list) {
239            List<GenPolynomial<C>> zr = blas.leftScalarProduct(row, F.list);
240            if (!blas.isZero(zr)) {
241                logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr);
242                return false;
243            }
244        }
245        return true;
246    }
247
248
249    /**
250     * Syzygy module from arbitrary base.
251     * @param F a polynomial list.
252     * @return syz(F), a basis for the module of syzygies for F.
253     */
254    public List<List<GenPolynomial<C>>> zeroRelationsArbitrary(List<GenPolynomial<C>> F) {
255        return zeroRelationsArbitrary(0, F);
256    }
257
258
259    /**
260     * Syzygy module from arbitrary module base.
261     * @param M an arbitrary module base.
262     * @return syz(M), a basis for the module of syzygies for M.
263     */
264    public ModuleList<C> zeroRelationsArbitrary(ModuleList<C> M) {
265        ModuleList<C> N = M;
266        if (M == null || M.list == null) {
267            return N;
268        }
269        if (M.rows == 0 || M.cols == 0) {
270            return N;
271        }
272        GenPolynomial<C> zero = M.ring.getZERO();
273        //System.out.println("zero = " + zero);
274
275        //ModuleList<C> Np = null;
276        PolynomialList<C> F = M.getPolynomialList();
277        int modv = M.cols; // > 0  
278        //System.out.println("modv = " + modv);
279        List<List<GenPolynomial<C>>> G = zeroRelationsArbitrary(modv, F.list);
280        List<List<GenPolynomial<C>>> Z = new ArrayList<List<GenPolynomial<C>>>();
281        for (int i = 0; i < G.size(); i++) {
282            //F = new PolynomialList(F.ring,(List)G.get(i));
283            List<GenPolynomial<C>> Gi = G.get(i);
284            List<GenPolynomial<C>> Zi = new ArrayList<GenPolynomial<C>>();
285            // System.out.println("\nG("+i+") = " + G.get(i));
286            for (int j = 0; j < Gi.size(); j++) {
287                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
288                GenPolynomial<C> p = Gi.get(j);
289                if (p != null) {
290                    Map<ExpVector, GenPolynomial<C>> r = p.contract(M.ring);
291                    int s = 0;
292                    for (GenPolynomial<C> vi : r.values()) {
293                        Zi.add(vi);
294                        s++;
295                    }
296                    if (s == 0) {
297                        Zi.add(zero);
298                    } else if (s > 1) { // will not happen
299                        System.out.println("p = " + p);
300                        System.out.println("map(" + i + "," + j + ") = " + r + ", size = " + r.size());
301                        throw new RuntimeException("Map.size() > 1 = " + r.size());
302                    }
303                }
304            }
305            //System.out.println("\nZ("+i+") = " + Zi);
306            Z.add(Zi);
307        }
308        N = new ModuleList<C>(M.ring, Z);
309        //System.out.println("\n\nN = " + N);
310        return N;
311    }
312
313}
314
315
316/**
317 * Container for module resolution components.
318 * @param <C> coefficient type
319 */
320class ResPart<C extends RingElem<C>> implements Serializable {
321
322
323    public final ModuleList<C> module;
324
325
326    public final ModuleList<C> GB;
327
328
329    public final ModuleList<C> syzygy;
330
331
332    /**
333     * ResPart.
334     * @param m a module list.
335     * @param g a module list GB.
336     * @param z a syzygy module list.
337     */
338    public ResPart(ModuleList<C> m, ModuleList<C> g, ModuleList<C> z) {
339        module = m;
340        GB = g;
341        syzygy = z;
342    }
343
344
345    /**
346     * toString.
347     */
348    @Override
349    public String toString() {
350        StringBuffer s = new StringBuffer("ResPart(\n");
351        s.append("module = " + module);
352        s.append("\n GB = " + GB);
353        s.append("\n syzygy = " + syzygy);
354        s.append(")");
355        return s.toString();
356    }
357}
358
359
360/**
361 * Container for polynomial resolution components.
362 */
363class ResPolPart<C extends RingElem<C>> implements Serializable {
364
365
366    public final PolynomialList<C> ideal;
367
368
369    public final PolynomialList<C> GB;
370
371
372    public final ModuleList<C> syzygy;
373
374
375    /**
376     * ResPolPart.
377     * @param m a polynomial list.
378     * @param g a polynomial list GB.
379     * @param z a syzygy module list.
380     */
381    public ResPolPart(PolynomialList<C> m, PolynomialList<C> g, ModuleList<C> z) {
382        ideal = m;
383        GB = g;
384        syzygy = z;
385    }
386
387
388    /**
389     * toString.
390     */
391    @Override
392    public String toString() {
393        StringBuffer s = new StringBuffer("ResPolPart(\n");
394        s.append("ideal = " + ideal);
395        s.append("\n GB = " + GB);
396        s.append("\n syzygy = " + syzygy);
397        s.append(")");
398        return s.toString();
399    }
400
401}