Source code

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