Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.Iterator;
010import java.util.List;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.gb.ExtendedGB;
016import edu.jas.gb.GroebnerBaseAbstract;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenPolynomialRing;
019import edu.jas.poly.ModuleList;
020import edu.jas.poly.PolynomialList;
021import edu.jas.structure.GcdRingElem;
022import edu.jas.structure.RingFactory;
023
024
025/**
026 * SyzygySeq class. Implements Syzygy computations and tests.
027 * @param <C> coefficient type
028 * @author Heinz Kredel
029 */
030
031public class SyzygySeq<C extends GcdRingElem<C>> extends SyzygyAbstract<C> {
032
033
034    private static final Logger logger = LogManager.getLogger(SyzygySeq.class);
035
036
037    private static final boolean debug = logger.isDebugEnabled();
038
039
040    /**
041     * Groebner base engine.
042     */
043    protected GroebnerBaseAbstract<C> bb;
044
045
046    /*
047     * Module Groebner base engine.
048    //protected ModGroebnerBaseAbstract<C> mbb;
049     */
050
051
052    /**
053     * Constructor.
054     * @param cf coefficient ring.
055     */
056    public SyzygySeq(RingFactory<C> cf) {
057        super();
058        bb = GBFactory.getImplementation(cf);
059        //mbb = new ModGroebnerBaseSeq<C>(cf);
060    }
061
062
063    /**
064     * Resolution of a module. Only with direct GBs.
065     * @param M a module list of a Groebner basis.
066     * @return a resolution of M.
067     */
068    public List<ResPart<C>> resolution(ModuleList<C> M) {
069        List<ResPart<C>> R = new ArrayList<ResPart<C>>();
070        ModuleList<C> MM = M;
071        ModuleList<C> GM;
072        ModuleList<C> Z;
073        //ModGroebnerBase<C> mbb = new ModGroebnerBaseSeq<C>(M.ring.coFac);
074        //assert cf == M.ring.coFac;
075        while (true) {
076            GM = bb.GB(MM);
077            Z = zeroRelations(GM);
078            R.add(new ResPart<C>(MM, GM, Z));
079            if (Z == null || Z.list == null || Z.list.size() == 0) {
080                break;
081            }
082            MM = Z;
083        }
084        return R;
085    }
086
087
088    /**
089     * Resolution of a polynomial list. Only with direct GBs.
090     * @param F a polynomial list of a Groebner basis.
091     * @return a resolution of F.
092     */
093    @SuppressWarnings("unchecked")
094    public List // <ResPart<C>|ResPolPart<C>>
095    resolution(PolynomialList<C> F) {
096        List<List<GenPolynomial<C>>> Z;
097        ModuleList<C> Zm;
098        List<GenPolynomial<C>> G;
099        PolynomialList<C> Gl;
100
101        //GroebnerBase<C> gb = GBFactory.getImplementation(F.ring.coFac);
102        //assert cf == F.ring.coFac;
103        G = bb.GB(F.list);
104        Z = zeroRelations(G);
105        Gl = new PolynomialList<C>(F.ring, G);
106        Zm = new ModuleList<C>(F.ring, Z);
107
108        List R = resolution(Zm); //// <ResPart<C>|ResPolPart<C>>
109        R.add(0, new ResPolPart<C>(F, Gl, Zm));
110        return R;
111    }
112
113
114    /**
115     * Resolution of a polynomial list.
116     * @param F a polynomial list of an arbitrary basis.
117     * @return a resolution of F.
118     */
119    @SuppressWarnings("unchecked")
120    public List // <ResPart<C>|ResPolPart<C>>
121    resolutionArbitrary(PolynomialList<C> F) {
122        List<List<GenPolynomial<C>>> Z;
123        ModuleList<C> Zm;
124        //List<GenPolynomial<C>> G;
125        PolynomialList<C> Gl = null;
126
127        //G = bb.GB(F.list);
128        Z = zeroRelationsArbitrary(F.list);
129        //Gl = new PolynomialList<C>(F.ring, F.list);
130        Zm = new ModuleList<C>(F.ring, Z);
131
132        List R = resolutionArbitrary(Zm); //// <ResPart<C>|ResPolPart<C>>
133        R.add(0, new ResPolPart<C>(F, Gl, Zm));
134        return R;
135    }
136
137
138    /**
139     * Resolution of a module.
140     * @param M a module list of an arbitrary basis.
141     * @return a resolution of M.
142     */
143    public List<ResPart<C>> resolutionArbitrary(ModuleList<C> M) {
144        List<ResPart<C>> R = new ArrayList<ResPart<C>>();
145        ModuleList<C> MM = M;
146        ModuleList<C> GM = null;
147        ModuleList<C> Z;
148        while (true) {
149            //GM = bb.GB(MM);
150            Z = zeroRelationsArbitrary(MM);
151            R.add(new ResPart<C>(MM, GM, Z));
152            if (Z == null || Z.list == null || Z.list.size() == 0) {
153                break;
154            }
155            MM = Z;
156        }
157        return R;
158    }
159
160
161    /**
162     * Syzygy module from arbitrary base.
163     * @param modv number of module variables.
164     * @param F a polynomial list.
165     * @return syz(F), a basis for the module of syzygies for F.
166     */
167    public List<List<GenPolynomial<C>>> zeroRelationsArbitrary(int modv, List<GenPolynomial<C>> F) {
168        if (F == null) {
169            return new ArrayList<List<GenPolynomial<C>>>();
170            //return zeroRelations(modv, F);
171        }
172        if (F.size() <= 1) {
173            return zeroRelations(modv, F);
174        }
175        //GroebnerBase<C> gb = GBFactory.getImplementation(F.get(0).ring.coFac);
176        // assert cf == F.get(0).ring.coFac;
177        final int lenf = F.size();
178        ExtendedGB<C> exgb = bb.extGB(F);
179        if (debug) {
180            logger.debug("exgb = {}", exgb);
181            if (!bb.isReductionMatrix(exgb)) {
182                logger.error("is reduction matrix ? false");
183            }
184        }
185        List<GenPolynomial<C>> G = exgb.G;
186        List<List<GenPolynomial<C>>> G2F = exgb.G2F;
187        List<List<GenPolynomial<C>>> F2G = exgb.F2G;
188
189        List<List<GenPolynomial<C>>> sg = zeroRelations(modv, G);
190        GenPolynomialRing<C> ring = G.get(0).ring;
191        ModuleList<C> S = new ModuleList<C>(ring, sg);
192        if (debug) {
193            logger.debug("syz = {}", S);
194            if (!isZeroRelation(sg, G)) {
195                logger.error("is syzygy ? false");
196            }
197        }
198        List<List<GenPolynomial<C>>> sf;
199        sf = new ArrayList<List<GenPolynomial<C>>>(sg.size());
200        //List<GenPolynomial<C>> row;
201        for (List<GenPolynomial<C>> r : sg) {
202            Iterator<GenPolynomial<C>> it = r.iterator();
203            Iterator<List<GenPolynomial<C>>> jt = G2F.iterator();
204
205            List<GenPolynomial<C>> rf;
206            rf = new ArrayList<GenPolynomial<C>>(lenf);
207            for (int m = 0; m < lenf; m++) {
208                rf.add(ring.getZERO());
209            }
210            while (it.hasNext() && jt.hasNext()) {
211                GenPolynomial<C> si = it.next();
212                List<GenPolynomial<C>> ai = jt.next();
213                //System.out.println("si = " + si);
214                //System.out.println("ai = " + ai);
215                if (si == null || ai == null) {
216                    continue;
217                }
218                List<GenPolynomial<C>> pi = blas.scalarProduct(si, ai);
219                //System.out.println("pi = " + pi);
220                rf = blas.vectorAdd(rf, pi);
221            }
222            if (it.hasNext() || jt.hasNext()) {
223                logger.error("zeroRelationsArbitrary wrong sizes");
224            }
225            //System.out.println("\nrf = " + rf + "\n");
226            sf.add(rf);
227        }
228        List<List<GenPolynomial<C>>> M;
229        M = new ArrayList<List<GenPolynomial<C>>>(lenf);
230        for (List<GenPolynomial<C>> r : F2G) {
231            Iterator<GenPolynomial<C>> it = r.iterator();
232            Iterator<List<GenPolynomial<C>>> jt = G2F.iterator();
233
234            List<GenPolynomial<C>> rf;
235            rf = new ArrayList<GenPolynomial<C>>(lenf);
236            for (int m = 0; m < lenf; m++) {
237                rf.add(ring.getZERO());
238            }
239            while (it.hasNext() && jt.hasNext()) {
240                GenPolynomial<C> si = it.next();
241                List<GenPolynomial<C>> ai = jt.next();
242                //System.out.println("si = " + si);
243                //System.out.println("ai = " + ai);
244                if (si == null || ai == null) {
245                    continue;
246                }
247                List<GenPolynomial<C>> pi = blas.scalarProduct(ai, si);
248                //System.out.println("pi = " + pi);
249                rf = blas.vectorAdd(rf, pi);
250            }
251            if (it.hasNext() || jt.hasNext()) {
252                logger.error("zeroRelationsArbitrary wrong sizes");
253            }
254            //System.out.println("\nMg Mf = " + rf + "\n");
255            M.add(rf);
256        }
257        //ModuleList<C> ML = new ModuleList<C>( ring, M );
258        //System.out.println("syz ML = " + ML);
259        // debug only:
260        /* not true in general
261        List<GenPolynomial<C>> F2 = new ArrayList<GenPolynomial<C>>( F.size() );
262        for ( List<GenPolynomial<C>> rr: M ) {
263            GenPolynomial<C> rrg = blas.scalarProduct( F, rr );
264            F2.add( rrg );
265        }
266        PolynomialList<C> pF = new PolynomialList<C>( ring, F );
267        PolynomialList<C> pF2 = new PolynomialList<C>( ring, F2 );
268        if ( ! pF.equals( pF2 ) ) {
269           logger.error("is FAB = F ? false");
270        }
271        */
272        int sflen = sf.size();
273        List<List<GenPolynomial<C>>> M2;
274        M2 = new ArrayList<List<GenPolynomial<C>>>(lenf);
275        int i = 0;
276        for (List<GenPolynomial<C>> ri : M) {
277            List<GenPolynomial<C>> r2i;
278            r2i = new ArrayList<GenPolynomial<C>>(ri.size());
279            int j = 0;
280            for (GenPolynomial<C> rij : ri) {
281                GenPolynomial<C> p = null;
282                if (i == j) {
283                    p = ring.getONE().subtract(rij);
284                } else {
285                    if (rij != null) {
286                        p = rij.negate();
287                    }
288                }
289                r2i.add(p);
290                j++;
291            }
292            M2.add(r2i);
293            if (!blas.isZero(r2i)) {
294                sf.add(r2i);
295            }
296            i++;
297        }
298        if (debug) {
299            ModuleList<C> M2L = new ModuleList<C>(ring, M2);
300            logger.debug("syz M2L = {}", M2L);
301            ModuleList<C> SF = new ModuleList<C>(ring, sf);
302            logger.debug("syz sf = {}", SF);
303            logger.debug("#syz {}, {}", sflen, sf.size());
304            if (!isZeroRelation(sf, F)) {
305                logger.error("is syz sf ? false");
306            }
307        }
308        return sf;
309    }
310
311}