Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.ps;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.logging.log4j.Logger;
012import org.apache.logging.log4j.LogManager; 
013
014import edu.jas.poly.ExpVector;
015import edu.jas.structure.RingElem;
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/* extends StandardBaseAbstract<C> */{
028
029
030    private static final Logger logger = LogManager.getLogger(StandardBaseSeq.class);
031
032
033    private static 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     * Normalize power series list.
062     * @param A list of power series.
063     * @return list of power series with zeros removed and ones/units reduced.
064     */
065    public List<MultiVarPowerSeries<C>> normalizeZerosOnes(List<MultiVarPowerSeries<C>> A) {
066        if (A == null) {
067            return A;
068        }
069        List<MultiVarPowerSeries<C>> N = new ArrayList<MultiVarPowerSeries<C>>(A.size());
070        if (A.isEmpty()) {
071            return N;
072        }
073        for (MultiVarPowerSeries<C> p : A) {
074            if (p == null || p.isZERO()) {
075                continue;
076            }
077            if (p.isUnit()) {
078                N.clear();
079                N.add(p.ring.getONE());
080                return N;
081            }
082            N.add(p.abs());
083        }
084        //N.trimToSize();
085        return N;
086    }
087
088
089    /**
090     * Standard base test.
091     * @param F power series list.
092     * @return true, if F is a Standard base, else false.
093     */
094    public boolean isSTD(List<MultiVarPowerSeries<C>> F) {
095        return isSTD(0, F);
096    }
097
098
099    /**
100     * Standard base test.
101     * @param modv module variable number.
102     * @param F power series list.
103     * @return true, if F is a Standard base, else false.
104     */
105    public boolean isSTD(int modv, List<MultiVarPowerSeries<C>> F) {
106        if (F == null) {
107            return true;
108        }
109        MultiVarPowerSeries<C> pi, pj, s, h;
110        for (int i = 0; i < F.size(); i++) {
111            pi = F.get(i);
112            for (int j = i + 1; j < F.size(); j++) {
113                pj = F.get(j);
114                if (!red.moduleCriterion(modv, pi, pj)) {
115                    continue;
116                }
117                // if ( ! red.criterion4( pi, pj ) ) { 
118                //       continue;
119                // }
120                s = red.SPolynomial(pi, pj);
121                if (s.isZERO()) {
122                    continue;
123                }
124                h = red.normalform(F, s);
125                if (!h.isZERO()) {
126                    System.out.println("pi = " + pi + ", pj = " + pj);
127                    System.out.println("s  = " + s + ", h = " + h);
128                    return false;
129                }
130            }
131        }
132        return true;
133    }
134
135
136    /**
137     * Standard base using pairlist class.
138     * @param F power series list.
139     * @return STD(F) a Standard base of F.
140     */
141    public List<MultiVarPowerSeries<C>> STD(List<MultiVarPowerSeries<C>> F) {
142        return STD(0, F);
143    }
144
145
146    /**
147     * Standard base using pairlist class.
148     * @param modv module variable number.
149     * @param F power series list.
150     * @return STD(F) a Standard base of F.
151     */
152    public List<MultiVarPowerSeries<C>> STD(int modv, List<MultiVarPowerSeries<C>> F) {
153        List<MultiVarPowerSeries<C>> G = normalizeZerosOnes(F);
154        G = PSUtil.<C> monic(G);
155        if (G.size() <= 1) {
156            return G;
157        }
158        MultiVarPowerSeriesRing<C> ring = G.get(0).ring;
159        if (!ring.coFac.isField()) {
160            throw new IllegalArgumentException("coefficients not from a field");
161        }
162        OrderedPairlist<C> pairlist = new OrderedPairlist<C>(modv, ring); //strategy.create( modv, ring ); 
163        pairlist.put(G);
164        logger.info("start {}", pairlist);
165
166        Pair<C> pair;
167        MultiVarPowerSeries<C> pi, pj, S, H;
168        while (pairlist.hasNext()) {
169            pair = pairlist.removeNext();
170            //logger.debug("pair = {}", pair);
171            if (pair == null) {
172                continue;
173            }
174            pi = pair.pi;
175            pj = pair.pj;
176            if ( /*false &&*/debug) {
177                logger.debug("pi    = {}", pi);
178                logger.debug("pj    = {}", pj);
179            }
180
181            S = red.SPolynomial(pi, pj);
182            //S.setTruncate(p.ring.truncate()); // ??
183            if (S.isZERO()) {
184                pair.setZero();
185                continue;
186            }
187            if (logger.isInfoEnabled()) {
188                ExpVector es = S.orderExpVector();
189                logger.info("ht(S) = {}, {}", es.toString(S.ring.vars), es); // + ", S = {}", S);
190            }
191
192            //long t = System.currentTimeMillis();
193            H = red.normalform(G, S);
194            if (H.isZERO()) {
195                pair.setZero();
196                continue;
197            }
198            //t = System.currentTimeMillis() - t;
199            //System.out.println("time = " + t);
200            if (logger.isInfoEnabled()) {
201                ExpVector eh = H.orderExpVector();
202                logger.info("ht(H) = {}, {}", eh.toString(S.ring.vars), eh); // + ", coeff(HT(H)) = {}", H.coefficient(eh));
203            }
204
205            //H = H.monic();
206            if (H.isUnit()) {
207                G.clear();
208                G.add(H);
209                return G; // since no threads are activated
210            }
211            if (debug) {
212                logger.info("H = {}", H);
213            }
214            //if (!H.isZERO()) {
215            //l++;
216            G.add(H);
217            pairlist.put(H);
218            //}
219        }
220        logger.debug("#sequential list = {}", G.size());
221        G = minimalSTD(G);
222        logger.info("end {}", pairlist);
223        return G;
224    }
225
226
227    /**
228     * Minimal ordered Standard basis.
229     * @param Gp a Standard base.
230     * @return a minimal Standard base of Gp, not auto reduced.
231     */
232    public List<MultiVarPowerSeries<C>> minimalSTD(List<MultiVarPowerSeries<C>> Gp) {
233        if (Gp == null || Gp.size() <= 1) {
234            return Gp;
235        }
236        // remove zero power series
237        List<MultiVarPowerSeries<C>> G = new ArrayList<MultiVarPowerSeries<C>>(Gp.size());
238        for (MultiVarPowerSeries<C> a : Gp) {
239            if (a != null && !a.isZERO()) { // always true in GB()
240                // make positive a = a.abs(); ?
241                a = a.monic();
242                G.add(a);
243            }
244        }
245        if (G.size() <= 1) {
246            return G;
247        }
248        // remove top reducible power series
249        MultiVarPowerSeries<C> a;
250        List<MultiVarPowerSeries<C>> F = new ArrayList<MultiVarPowerSeries<C>>(G.size());
251        while (G.size() > 0) {
252            a = G.remove(0);
253            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
254                // drop power series 
255                if (debug) {
256                    System.out.println("dropped " + a);
257                    List<MultiVarPowerSeries<C>> ff = new ArrayList<MultiVarPowerSeries<C>>(G);
258                    ff.addAll(F);
259                    a = red.normalform(ff, a);
260                    if (!a.isZERO()) {
261                        System.out.println("error, nf(a) " + a);
262                    }
263                }
264            } else {
265                F.add(a);
266            }
267        }
268        G = F;
269        // power series not reduced
270        return G;
271    }
272
273}