Source code

001/*
002 * $Id$
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 = blas.genVector(nzlen, null);
189                //C c = p.leadingBaseCoefficient();
190                //c = c.inverse();
191                //p = p.multiply( c );
192                row.set(k, mone); //.multiply(c) );
193                k++;
194                if (p.isUnit()) {
195                    G.clear();
196                    G.add(p);
197                    G2F.clear();
198                    G2F.add(row);
199                    oneInGB = true;
200                    break;
201                }
202                G.add(p);
203                G2F.add(row);
204                if (pairlist == null) {
205                    pairlist = new CriticalPairList<C>(modv, p.ring);
206                }
207                // putOne not required
208                pairlist.put(p);
209            } else {
210                len--;
211            }
212        }
213        ExtendedGB<C> exgb;
214        if (len <= 1 || oneInGB) {
215            // adjust F2G
216            for (GenPolynomial<C> f : F) {
217                row = blas.genVector(G.size(), null);
218                H = red.normalform(row, G, f);
219                if (!H.isZERO()) {
220                    logger.error("nonzero H = {}", H);
221                }
222                F2G.add(row);
223            }
224            exgb = new ExtendedGB<C>(F, G, F2G, G2F);
225            //System.out.println("exgb 1 = " + exgb);
226            return exgb;
227        }
228
229        CriticalPair<C> pair;
230        int i, j;
231        GenPolynomial<C> pi;
232        GenPolynomial<C> pj;
233        GenPolynomial<C> S;
234        GenPolynomial<C> x;
235        GenPolynomial<C> y;
236        //GenPolynomial<C> z;
237        while (pairlist.hasNext() && !oneInGB) {
238            pair = pairlist.getNext();
239            if (pair == null) {
240                pairlist.update(); // ?
241                continue;
242            }
243            i = pair.i;
244            j = pair.j;
245            pi = pair.pi;
246            pj = pair.pj;
247            if (debug) {
248                logger.info("i, pi    = {}, {}", i, pi);
249                logger.info("j, pj    = {}, {}", j, pj);
250            }
251
252            rows = new ArrayList<GenPolynomial<C>>(G.size());
253            for (int m = 0; m < G.size(); m++) {
254                rows.add(null);
255            }
256            S = red.SPolynomial(rows, i, pi, j, pj);
257            if (debug) {
258                logger.debug("is reduction S = {}", red.isReductionNF(rows, G, ring.getZERO(), S));
259            }
260            if (S.isZERO()) {
261                pairlist.update(pair, S);
262                // do not add to G2F
263                continue;
264            }
265            if (debug) {
266                logger.debug("ht(S) = {}", S.leadingExpVector());
267            }
268
269            rowh = new ArrayList<GenPolynomial<C>>(G.size());
270            for (int m = 0; m < G.size(); m++) {
271                rowh.add(null);
272            }
273            H = red.normalform(rowh, G, S);
274            if (debug) {
275                logger.debug("is reduction H = {}", red.isReductionNF(rowh, G, S, H));
276            }
277            if (H.isZERO()) {
278                pairlist.update(pair, H);
279                // do not add to G2F
280                continue;
281            }
282            if (debug) {
283                logger.debug("ht(H) = {}", H.leadingExpVector());
284            }
285
286            row = blas.vectorCombineOld(rows,rowh);
287            // if (debug) {
288            //     logger.debug("is reduction 0+sum(row,G) == H : "
289            //             + red.isReductionNF(row, G, H, ring.getZERO()));
290            // }
291
292            //  H = H.monic();
293            C c = H.leadingBaseCoefficient();
294            c = c.inverse();
295            H = H.multiply(c);
296            row = blas.scalarProduct(mone.multiply(c), row);
297            row.set(G.size(), mone);
298            if (H.isONE()) {
299                // pairlist.record( pair, H );
300                // G.clear(); 
301                G.add(H);
302                G2F.add(row);
303                oneInGB = true;
304                break;
305            }
306            if (debug) {
307                logger.debug("H = {}", H);
308            }
309            G.add(H);
310            pairlist.update(pair, H);
311            G2F.add(row);
312        }
313        if (debug) {
314            exgb = new ExtendedGB<C>(F, G, F2G, G2F);
315            logger.info("exgb unnorm = {}", exgb);
316        }
317        G2F = normalizeMatrix(F.size(), G2F);
318        if (debug) {
319            exgb = new ExtendedGB<C>(F, G, F2G, G2F);
320            logger.info("exgb nonmin = {}", exgb);
321            boolean t2 = isReductionMatrix(exgb);
322            logger.info("exgb t2 = {}", t2);
323        }
324        exgb = minimalExtendedGB(F.size(), G, G2F);
325        G = exgb.G;
326        G2F = exgb.G2F;
327        logger.debug("#sequential list = {}", G.size());
328        logger.info("{}", pairlist);
329        // setup matrices F and F2G
330        for (GenPolynomial<C> f : F) {
331            row = blas.genVector(G.size(), null);
332            H = red.normalform(row, G, f);
333            if (!H.isZERO()) {
334                logger.error("nonzero H = {}", H);
335            }
336            F2G.add(row);
337        }
338        exgb = new ExtendedGB<C>(F, G, F2G, G2F);
339        if (debug) {
340            logger.info("exgb nonmin = {}", exgb);
341            boolean t2 = isReductionMatrix(exgb);
342            logger.info("exgb t2 = {}", t2);
343        }
344        return exgb;
345    }
346
347}