Source code

001/*
002 * $Id: GroebnerBaseSeqPairSeq.java 4946 2014-10-05 22:03:04Z axelclk $
003 */
004
005package edu.jas.gb;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.ListIterator;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.poly.GenPolynomial;
015import edu.jas.poly.GenPolynomialRing;
016import edu.jas.structure.RingElem;
017
018
019/**
020 * Groebner Base sequential algorithm. Implements Groebner bases and GB test.
021 * Uses sequential pair list class.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025
026public class GroebnerBaseSeqPairSeq<C extends RingElem<C>> extends GroebnerBaseAbstract<C> {
027
028
029    private static final Logger logger = Logger.getLogger(GroebnerBaseSeqPairSeq.class);
030
031
032    private final boolean debug = logger.isDebugEnabled();
033
034
035    /**
036     * Constructor.
037     */
038    public GroebnerBaseSeqPairSeq() {
039        super();
040    }
041
042
043    /**
044     * Constructor.
045     * @param red Reduction engine
046     */
047    public GroebnerBaseSeqPairSeq(Reduction<C> red) {
048        super(red);
049    }
050
051
052    /**
053     * Groebner base using pairlist class.
054     * @param modv module variable number.
055     * @param F polynomial list.
056     * @return GB(F) a Groebner base of F.
057     */
058    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
059        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
060        if (F == null) {
061            return G;
062        }
063        GenPolynomial<C> p;
064        CriticalPairList<C> pairlist = null;
065        int len = F.size();
066        ListIterator<GenPolynomial<C>> it = F.listIterator();
067        while (it.hasNext()) {
068            p = it.next();
069            if (p.length() > 0) {
070                p = p.monic();
071                if (p.isONE()) {
072                    G.clear();
073                    G.add(p);
074                    return G; // since no threads are activated
075                }
076                G.add(p);
077                if (pairlist == null) {
078                    pairlist = new CriticalPairList<C>(modv, p.ring);
079                }
080                // putOne not required
081                pairlist.put(p);
082            } else {
083                len--;
084            }
085        }
086        if (len <= 1) {
087            return G; // since no threads are activated
088        }
089
090        CriticalPair<C> pair;
091        GenPolynomial<C> pi;
092        GenPolynomial<C> pj;
093        GenPolynomial<C> S;
094        GenPolynomial<C> H;
095        while (pairlist.hasNext()) {
096            pair = pairlist.getNext();
097            if (pair == null) {
098                pairlist.update(); // ?
099                continue;
100            }
101            pi = pair.pi;
102            pj = pair.pj;
103            if (debug) {
104                logger.debug("pi    = " + pi);
105                logger.debug("pj    = " + pj);
106            }
107
108            S = red.SPolynomial(pi, pj);
109            if (S.isZERO()) {
110                pairlist.update(pair, S);
111                continue;
112            }
113            if (debug) {
114                logger.debug("ht(S) = " + S.leadingExpVector());
115            }
116
117            H = red.normalform(G, S);
118            if (H.isZERO()) {
119                pairlist.update(pair, H);
120                continue;
121            }
122            if (debug) {
123                logger.debug("ht(H) = " + H.leadingExpVector());
124            }
125
126            H = H.monic();
127            if (H.isONE()) {
128                // pairlist.record( pair, H );
129                G.clear();
130                G.add(H);
131                return G; // since no threads are activated
132            }
133            if (debug) {
134                logger.debug("H = " + H);
135            }
136            G.add(H);
137            pairlist.update(pair, H);
138            //pairlist.update();
139        }
140        logger.debug("#sequential list = " + G.size());
141        G = minimalGB(G);
142        logger.info("" + pairlist);
143        return G;
144    }
145
146
147    /**
148     * Extended Groebner base using critical pair class.
149     * @param modv module variable number.
150     * @param F polynomial list.
151     * @return a container for an extended Groebner base of F.
152     */
153    @Override
154    public ExtendedGB<C> extGB(int modv, List<GenPolynomial<C>> F) {
155        if ( F == null || F.isEmpty() ) {
156            throw new IllegalArgumentException("null or empty F not allowed");
157        }
158        List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
159        List<List<GenPolynomial<C>>> F2G = new ArrayList<List<GenPolynomial<C>>>();
160        List<List<GenPolynomial<C>>> G2F = new ArrayList<List<GenPolynomial<C>>>();
161        CriticalPairList<C> pairlist = null;
162        boolean oneInGB = false;
163        int len = F.size();
164
165        List<GenPolynomial<C>> row = null;
166        List<GenPolynomial<C>> rows = null;
167        List<GenPolynomial<C>> rowh = null;
168        GenPolynomialRing<C> ring = null;
169        GenPolynomial<C> H;
170        GenPolynomial<C> p;
171
172        int nzlen = 0;
173        for (GenPolynomial<C> f : F) {
174            if (f.length() > 0) {
175                nzlen++;
176            }
177            if (ring == null) {
178                ring = f.ring;
179            }
180        }
181        GenPolynomial<C> mone = ring.getONE(); //.negate();
182        int k = 0;
183        ListIterator<GenPolynomial<C>> it = F.listIterator();
184        while (it.hasNext()) {
185            p = it.next();
186            if (p.length() > 0) {
187                row = new ArrayList<GenPolynomial<C>>(nzlen);
188                for (int j = 0; j < nzlen; j++) {
189                    row.add(null);
190                }
191                //C c = p.leadingBaseCoefficient();
192                //c = c.inverse();
193                //p = p.multiply( c );
194                row.set(k, mone); //.multiply(c) );
195                k++;
196                if (p.isUnit()) {
197                    G.clear();
198                    G.add(p);
199                    G2F.clear();
200                    G2F.add(row);
201                    oneInGB = true;
202                    break;
203                }
204                G.add(p);
205                G2F.add(row);
206                if (pairlist == null) {
207                    pairlist = new CriticalPairList<C>(modv, p.ring);
208                }
209                // putOne not required
210                pairlist.put(p);
211            } else {
212                len--;
213            }
214        }
215        ExtendedGB<C> exgb;
216        if (len <= 1 || oneInGB) {
217            // adjust F2G
218            for (GenPolynomial<C> f : F) {
219                row = new ArrayList<GenPolynomial<C>>(G.size());
220                for (int j = 0; j < G.size(); j++) {
221                    row.add(null);
222                }
223                H = red.normalform(row, G, f);
224                if (!H.isZERO()) {
225                    logger.error("nonzero H = " + H);
226                }
227                F2G.add(row);
228            }
229            exgb = new ExtendedGB<C>(F, G, F2G, G2F);
230            //System.out.println("exgb 1 = " + exgb);
231            return exgb;
232        }
233
234        CriticalPair<C> pair;
235        int i, j;
236        GenPolynomial<C> pi;
237        GenPolynomial<C> pj;
238        GenPolynomial<C> S;
239        GenPolynomial<C> x;
240        GenPolynomial<C> y;
241        //GenPolynomial<C> z;
242        while (pairlist.hasNext() && !oneInGB) {
243            pair = pairlist.getNext();
244            if (pair == null) {
245                pairlist.update(); // ?
246                continue;
247            }
248            i = pair.i;
249            j = pair.j;
250            pi = pair.pi;
251            pj = pair.pj;
252            if (debug) {
253                logger.info("i, pi    = " + i + ", " + pi);
254                logger.info("j, pj    = " + j + ", " + pj);
255            }
256
257            rows = new ArrayList<GenPolynomial<C>>(G.size());
258            for (int m = 0; m < G.size(); m++) {
259                rows.add(null);
260            }
261            S = red.SPolynomial(rows, i, pi, j, pj);
262            if (debug) {
263                logger.debug("is reduction S = " + red.isReductionNF(rows, G, ring.getZERO(), S));
264            }
265            if (S.isZERO()) {
266                pairlist.update(pair, S);
267                // do not add to G2F
268                continue;
269            }
270            if (debug) {
271                logger.debug("ht(S) = " + S.leadingExpVector());
272            }
273
274            rowh = new ArrayList<GenPolynomial<C>>(G.size());
275            for (int m = 0; m < G.size(); m++) {
276                rowh.add(null);
277            }
278            H = red.normalform(rowh, G, S);
279            if (debug) {
280                logger.debug("is reduction H = " + red.isReductionNF(rowh, G, S, H));
281            }
282            if (H.isZERO()) {
283                pairlist.update(pair, H);
284                // do not add to G2F
285                continue;
286            }
287            if (debug) {
288                logger.debug("ht(H) = " + H.leadingExpVector());
289            }
290
291            row = new ArrayList<GenPolynomial<C>>(G.size() + 1);
292            for (int m = 0; m < G.size(); m++) {
293                x = rows.get(m);
294                if (x != null) {
295                    //System.out.println("ms = " + m + " " + x);
296                    x = x.negate();
297                }
298                y = rowh.get(m);
299                if (y != null) {
300                    y = y.negate();
301                    //System.out.println("mh = " + m + " " + y);
302                }
303                if (x == null) {
304                    x = y;
305                } else {
306                    x = x.sum(y);
307                }
308                //System.out.println("mx = " + m + " " + x);
309                row.add(x);
310            }
311            if (debug) {
312                logger.debug("is reduction 0+sum(row,G) == H : "
313                        + red.isReductionNF(row, G, H, ring.getZERO()));
314            }
315            row.add(null);
316
317
318            //  H = H.monic();
319            C c = H.leadingBaseCoefficient();
320            c = c.inverse();
321            H = H.multiply(c);
322            row = blas.scalarProduct(mone.multiply(c), row);
323            row.set(G.size(), mone);
324            if (H.isONE()) {
325                // pairlist.record( pair, H );
326                // G.clear(); 
327                G.add(H);
328                G2F.add(row);
329                oneInGB = true;
330                break;
331            }
332            if (debug) {
333                logger.debug("H = " + H);
334            }
335            G.add(H);
336            pairlist.update(pair, H);
337            G2F.add(row);
338        }
339        if (debug) {
340            exgb = new ExtendedGB<C>(F, G, F2G, G2F);
341            logger.info("exgb unnorm = " + exgb);
342        }
343        G2F = normalizeMatrix(F.size(), G2F);
344        if (debug) {
345            exgb = new ExtendedGB<C>(F, G, F2G, G2F);
346            logger.info("exgb nonmin = " + exgb);
347            boolean t2 = isReductionMatrix(exgb);
348            logger.info("exgb t2 = " + t2);
349        }
350        exgb = minimalExtendedGB(F.size(), G, G2F);
351        G = exgb.G;
352        G2F = exgb.G2F;
353        logger.debug("#sequential list = " + G.size());
354        logger.info("" + pairlist); 
355        // setup matrices F and F2G
356        for (GenPolynomial<C> f : F) {
357            row = new ArrayList<GenPolynomial<C>>(G.size());
358            for (int m = 0; m < G.size(); m++) {
359                row.add(null);
360            }
361            H = red.normalform(row, G, f);
362            if (!H.isZERO()) {
363                logger.error("nonzero H = " + H);
364            }
365            F2G.add(row);
366        }
367        exgb = new ExtendedGB<C>(F, G, F2G, G2F);
368        if (debug) {
369            logger.info("exgb nonmin = " + exgb);
370            boolean t2 = isReductionMatrix(exgb);
371            logger.info("exgb t2 = " + t2);
372        }
373        return exgb;
374    }
375
376}