Source code

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