Source code

001/*
002 * $Id: StandardBaseSeq.java 3349 2010-10-15 20:54:27Z kredel $
003 */
004
005package edu.jas.ps;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.ListIterator;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.structure.RingElem;
015import edu.jas.poly.ExpVector;
016
017
018/**
019 * Standard Base sequential algorithm. Implements Standard bases and GB test.
020 * <b>Note: </b> Currently the term order is fixed to the order defined by the
021 * iterator over exponent vectors <code>ExpVectorIterator</code>.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025
026public class StandardBaseSeq<C extends RingElem<C>>
027    /*todo: extends StandardBaseAbstract<C>*/{
028
029
030    private static final Logger logger = Logger.getLogger(StandardBaseSeq.class);
031
032
033    private final boolean debug = logger.isDebugEnabled();
034
035
036    /**
037     * Reduction engine.
038     */
039    public final ReductionSeq<C> red;
040
041
042    /**
043     * Constructor.
044     */
045    public StandardBaseSeq() {
046        //super();
047        this(new ReductionSeq<C>());
048    }
049
050
051    /**
052     * Constructor.
053     * @param red Reduction engine
054     */
055    public StandardBaseSeq(ReductionSeq<C> red) {
056        this.red = red; //super(red);
057    }
058
059
060    /**
061     * Standard base test.
062     * @param F power series list.
063     * @return true, if F is a Standard base, else false.
064     */
065    public boolean isSTD(List<MultiVarPowerSeries<C>> F) {
066        return isSTD(0, F);
067    }
068
069
070    /**
071     * Standard base test.
072     * @param modv module variable number.
073     * @param F power series list.
074     * @return true, if F is a Standard base, else false.
075     */
076    public boolean isSTD(int modv, List<MultiVarPowerSeries<C>> F) {
077        if (F == null) {
078            return true;
079        }
080        MultiVarPowerSeries<C> pi, pj, s, h;
081        for (int i = 0; i < F.size(); i++) {
082            pi = F.get(i);
083            for (int j = i + 1; j < F.size(); j++) {
084                pj = F.get(j);
085                if (!red.moduleCriterion(modv, pi, pj)) {
086                    continue;
087                }
088                //                 if ( ! red.criterion4( pi, pj ) ) { 
089                //                    continue;
090                //                 }
091                s = red.SPolynomial(pi, pj);
092                if (s.isZERO()) {
093                    continue;
094                }
095                h = red.normalform(F, s);
096                if (!h.isZERO()) {
097                    System.out.println("pi = " + pi + ", pj = " + pj);
098                    System.out.println("s  = " + s + ", h = " + h);
099                    return false;
100                }
101            }
102        }
103        return true;
104    }
105
106
107    /**
108     * Standard base using pairlist class.
109     * @param F power series list.
110     * @return STD(F) a Standard base of F.
111     */
112    public List<MultiVarPowerSeries<C>> STD(List<MultiVarPowerSeries<C>> F) {
113        return STD(0, F);
114    }
115
116
117    /**
118     * Standard base using pairlist class.
119     * @param modv module variable number.
120     * @param F power series list.
121     * @return STD(F) a Standard base of F.
122     */
123    public List<MultiVarPowerSeries<C>> STD(int modv, List<MultiVarPowerSeries<C>> F) {
124        MultiVarPowerSeries<C> p = null;
125        List<MultiVarPowerSeries<C>> G = new ArrayList<MultiVarPowerSeries<C>>();
126        OrderedPairlist<C> pairlist = null;
127        int l = F.size();
128        ListIterator<MultiVarPowerSeries<C>> it = F.listIterator();
129        while (it.hasNext()) {
130            p = it.next();
131            if (!p.isZERO()) {
132                //p = p.monic();
133                if (p.isUnit()) {
134                    G.clear();
135                    G.add(p);
136                    return G; // since no threads are activated
137                }
138                G.add(p);
139                if (pairlist == null) {
140                    pairlist = new OrderedPairlist<C>(modv, p.ring);
141                    if (!p.ring.coFac.isField()) {
142                        throw new IllegalArgumentException("coefficients not from a field");
143                    }
144                }
145                // putOne not required
146                pairlist.put(p);
147            } else {
148                l--;
149            }
150        }
151        if (l <= 1) {
152            return G; // since no threads are activated
153        }
154
155        Pair<C> pair;
156        MultiVarPowerSeries<C> pi;
157        MultiVarPowerSeries<C> pj;
158        MultiVarPowerSeries<C> S;
159        MultiVarPowerSeries<C> H;
160        while (pairlist.hasNext()) {
161            pair = pairlist.removeNext();
162            //logger.debug("pair = " + pair);
163            if (pair == null) {
164                continue;
165            }
166            pi = pair.pi;
167            pj = pair.pj;
168            if ( /*false &&*/debug) {
169                logger.debug("pi    = " + pi);
170                logger.debug("pj    = " + pj);
171            }
172
173            S = red.SPolynomial(pi, pj);
174            //S.setTruncate(p.ring.truncate()); // ??
175            if (S.isZERO()) {
176                pair.setZero();
177                continue;
178            }
179            if (logger.isInfoEnabled()) {
180                ExpVector es = S.orderExpVector();
181                logger.info("ht(S) = " + es.toString(S.ring.vars) + ", " + es); // + ", S = " + S);
182            }
183
184            //long t = System.currentTimeMillis();
185            H = red.normalform(G, S);
186            if (H.isZERO()) {
187                pair.setZero();
188                continue;
189            }
190            //t = System.currentTimeMillis() - t;
191            //System.out.println("time = " + t);
192            if (logger.isInfoEnabled()) {
193                ExpVector eh = H.orderExpVector();
194                logger.info("ht(H) = " + eh.toString(S.ring.vars) + ", " + eh); // + ", coeff(HT(H)) = " + H.coefficient(eh));
195            }
196
197            //H = H.monic();
198            if (H.isUnit()) {
199                G.clear();
200                G.add(H);
201                return G; // since no threads are activated
202            }
203            if (logger.isDebugEnabled()) {
204                logger.info("H = " + H);
205            }
206            //if (!H.isZERO()) {
207                l++;
208                G.add(H);
209                pairlist.put(H);
210            //}
211        }
212        logger.debug("#sequential list = " + G.size());
213        G = minimalSTD(G);
214        logger.info("" + pairlist);
215        return G;
216    }
217
218
219    /**
220     * Minimal ordered Standard basis.
221     * @param Gp a Standard base.
222     * @return a minimal Standard base of Gp, not auto reduced.
223     */
224    public List<MultiVarPowerSeries<C>> minimalSTD(List<MultiVarPowerSeries<C>> Gp) {
225        if (Gp == null || Gp.size() <= 1) {
226            return Gp;
227        }
228        // remove zero power series
229        List<MultiVarPowerSeries<C>> G = new ArrayList<MultiVarPowerSeries<C>>(Gp.size());
230        for (MultiVarPowerSeries<C> a : Gp) {
231            if (a != null && !a.isZERO()) { // always true in GB()
232                // make positive a = a.abs(); ?
233                a = a.monic();
234                G.add(a);
235            }
236        }
237        if (G.size() <= 1) {
238            return G;
239        }
240        // remove top reducible power series
241        MultiVarPowerSeries<C> a;
242        List<MultiVarPowerSeries<C>> F = new ArrayList<MultiVarPowerSeries<C>>(G.size());
243        while (G.size() > 0) {
244            a = G.remove(0);
245            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
246                // drop power series 
247                if (debug) {
248                    System.out.println("dropped " + a);
249                    List<MultiVarPowerSeries<C>> ff = new ArrayList<MultiVarPowerSeries<C>>(G);
250                    ff.addAll(F);
251                    a = red.normalform(ff, a);
252                    if (!a.isZERO()) {
253                        System.out.println("error, nf(a) " + a);
254                    }
255                }
256            } else {
257                F.add(a);
258            }
259        }
260        G = F;
261        // power series not reduced
262        return G;
263    }
264
265}