Source code

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