Source code

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