Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.ps;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.structure.RingElem;
019
020
021/**
022 * Multivariate power series reduction sequential use algorithm. Implements Mora
023 * normal-form algorithm.
024 * @param <C> coefficient type
025 * @author Heinz Kredel
026 */
027
028public class ReductionSeq<C extends RingElem<C>> // should be FieldElem<C>>
029/* extends ReductionAbstract<C> */{
030
031
032    private static final Logger logger = LogManager.getLogger(ReductionSeq.class);
033
034
035    private static final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Constructor.
040     */
041    public ReductionSeq() {
042    }
043
044
045    /**
046     * Module criterium.
047     * @param modv number of module variables.
048     * @param A power series.
049     * @param B power series.
050     * @return true if the module S-power-series(i,j) is required.
051     */
052    public boolean moduleCriterion(int modv, MultiVarPowerSeries<C> A, MultiVarPowerSeries<C> B) {
053        if (modv == 0) {
054            return true;
055        }
056        ExpVector ei = A.orderExpVector();
057        ExpVector ej = B.orderExpVector();
058        return moduleCriterion(modv, ei, ej);
059    }
060
061
062    /**
063     * Module criterion.
064     * @param modv number of module variables.
065     * @param ei ExpVector.
066     * @param ej ExpVector.
067     * @return true if the module S-power-series(i,j) is required.
068     */
069    public boolean moduleCriterion(int modv, ExpVector ei, ExpVector ej) {
070        if (modv == 0) {
071            return true;
072        }
073        if (ei.invLexCompareTo(ej, 0, modv) != 0) {
074            return false; // skip pair
075        }
076        return true;
077    }
078
079
080    /**
081     * GB criterion 4. Use only for commutative power series rings.
082     * @param A power series.
083     * @param B power series.
084     * @param e = lcm(ht(A),ht(B))
085     * @return true if the S-power-series(i,j) is required, else false.
086     */
087    public boolean criterion4(MultiVarPowerSeries<C> A, MultiVarPowerSeries<C> B, ExpVector e) {
088        if (logger.isInfoEnabled()) {
089            if (!A.ring.equals(B.ring)) {
090                logger.error("rings not equal: {} != {}", A.ring, B.ring);
091            }
092            if (!A.ring.isCommutative()) {
093                logger.error("GBCriterion4 not applicabable to non-commutative power series");
094                return true;
095            }
096        }
097        ExpVector ei = A.orderExpVector();
098        ExpVector ej = B.orderExpVector();
099        ExpVector g = ei.sum(ej);
100        // boolean t =  g == e ;
101        ExpVector h = g.subtract(e);
102        int s = h.signum();
103        return !(s == 0);
104    }
105
106
107    /**
108     * S-Power-series, S-polynomial.
109     * @param A power series.
110     * @param B power series.
111     * @return spol(A,B) the S-power-series of A and B.
112     */
113    public MultiVarPowerSeries<C> SPolynomial(MultiVarPowerSeries<C> A, MultiVarPowerSeries<C> B) {
114        if (B == null || B.isZERO()) {
115            if (A == null) {
116                return B;
117            }
118            return A.ring.getZERO();
119        }
120        if (A == null || A.isZERO()) {
121            return B.ring.getZERO();
122        }
123        if (debug) {
124            if (!A.ring.equals(B.ring)) {
125                logger.error("rings not equal: {} != {}", A.ring, B.ring);
126            }
127        }
128        Map.Entry<ExpVector, C> ma = A.orderMonomial();
129        Map.Entry<ExpVector, C> mb = B.orderMonomial();
130
131        ExpVector e = ma.getKey();
132        ExpVector f = mb.getKey();
133
134        ExpVector g = e.lcm(f);
135        ExpVector e1 = g.subtract(e);
136        ExpVector f1 = g.subtract(f);
137
138        C a = ma.getValue();
139        C b = mb.getValue();
140
141        MultiVarPowerSeries<C> Ap = A.multiply(b, e1);
142        MultiVarPowerSeries<C> Bp = B.multiply(a, f1);
143        MultiVarPowerSeries<C> C = Ap.subtract(Bp);
144        return C;
145    }
146
147
148    /**
149     * Top normal-form with Mora's algorithm.
150     * @param Ap power series.
151     * @param Pp power series list.
152     * @return top-nf(Ap) with respect to Pp.
153     */
154    public MultiVarPowerSeries<C> normalform(List<MultiVarPowerSeries<C>> Pp, MultiVarPowerSeries<C> Ap) {
155        if (Pp == null || Pp.isEmpty()) {
156            return Ap;
157        }
158        if (Ap == null || Ap.isZERO()) {
159            return Ap;
160        }
161        if (!Ap.ring.coFac.isField()) {
162            throw new IllegalArgumentException("coefficients not from a field");
163        }
164        List<MultiVarPowerSeries<C>> P = new ArrayList<MultiVarPowerSeries<C>>(Pp.size());
165        synchronized (Pp) {
166            P.addAll(Pp);
167        }
168        ArrayList<ExpVector> htl = new ArrayList<ExpVector>(P.size());
169        ArrayList<C> lbc = new ArrayList<C>(P.size());
170        ArrayList<MultiVarPowerSeries<C>> p = new ArrayList<MultiVarPowerSeries<C>>(P.size());
171        ArrayList<Long> ecart = new ArrayList<Long>(P.size());
172        Map.Entry<ExpVector, C> m;
173        //int j = 0;
174        for (int i = 0; i < P.size(); i++) {
175            m = P.get(i).orderMonomial();
176            //System.out.println("m_i = " + m);
177            if (m != null) {
178                p.add(P.get(i));
179                //System.out.println("e = " + m.getKey().toString(Ap.ring.vars));
180                htl.add(m.getKey());
181                lbc.add(m.getValue());
182                ecart.add(P.get(i).ecart());
183                //j++;
184            }
185        }
186        //int ll = j;
187        MultiVarPowerSeries<C> S = Ap;
188        //S.setTruncate(Ap.ring.truncate()); // ??
189        m = S.orderMonomial();
190        while (true) {
191            //System.out.println("m = " + m);
192            //System.out.println("S = " + S);
193            if (m == null) {
194                return S;
195            }
196            if (S.isZERO()) {
197                return S;
198            }
199            ExpVector e = m.getKey();
200            if (debug) {
201                logger.debug("e = {}", e.toString(Ap.ring.vars));
202            }
203            // search ps with ht(ps) | ht(S)
204            List<Integer> li = new ArrayList<Integer>();
205            int i;
206            for (i = 0; i < htl.size(); i++) {
207                if (e.multipleOf(htl.get(i))) {
208                    //System.out.println("m = " + m);
209                    li.add(i);
210                }
211            }
212            if (li.isEmpty()) {
213                return S;
214            }
215            //System.out.println("li = " + li);
216            // select ps with smallest ecart
217            long mi = Long.MAX_VALUE;
218            //String es = "";
219            for (int k = 0; k < li.size(); k++) {
220                int ki = li.get(k);
221                long x = ecart.get(ki); //p.get( ki ).ecart();
222                //es = es + x + " ";
223                if (x < mi) { // first < or last <= ?
224                    mi = x;
225                    i = ki;
226                }
227            }
228            //System.out.println("li = " + li + ", ecarts = " + es);
229            //System.out.println("i = " + i + ", p_i = " + p.get(i));
230            //if ( i <= ll ) {
231            //} else {
232            //    System.out.println("i = " + i + ", ll = " + ll);
233            //}
234            long si = S.ecart();
235            if (mi > si) {
236                //System.out.println("ecart_i = " + mi + ", ecart_S = " + si + ", S+ = " + S);
237                p.add(S);
238                htl.add(m.getKey());
239                lbc.add(m.getValue());
240                ecart.add(si);
241            }
242            e = e.subtract(htl.get(i));
243            C a = m.getValue().divide(lbc.get(i));
244            MultiVarPowerSeries<C> Q = p.get(i).multiply(a, e);
245            S = S.subtract(Q);
246            m = S.orderMonomial();
247        }
248    }
249
250
251    /**
252     * Total reduced normal-form with Mora's algorithm.
253     * @param A power series.
254     * @param P power series list.
255     * @return total-nf(A) with respect to P.
256     */
257    public MultiVarPowerSeries<C> totalNormalform(List<MultiVarPowerSeries<C>> P, MultiVarPowerSeries<C> A) {
258        if (P == null || P.isEmpty()) {
259            return A;
260        }
261        if (A == null) {
262            return A;
263        }
264        MultiVarPowerSeries<C> R = normalform(P, A);
265        if (R.isZERO()) {
266            return R;
267        }
268        MultiVarCoefficients<C> Rc = new MultiVarCoefficients<C>(A.ring) {
269
270
271            @Override
272            public C generate(ExpVector i) { // will not be used
273                return pfac.coFac.getZERO();
274            }
275        };
276        GenPolynomialRing<C> pfac = A.lazyCoeffs.pfac;
277        while (!R.isZERO()) {
278            Map.Entry<ExpVector, C> m = R.orderMonomial();
279            if (m == null) {
280                break;
281            }
282            R = R.reductum();
283            ExpVector e = m.getKey();
284            long t = e.totalDeg();
285            GenPolynomial<C> p = Rc.coeffCache.get(t);
286            if (p == null) {
287                p = pfac.getZERO();
288            }
289            p = p.sum(m.getValue(), e);
290            Rc.coeffCache.put(t, p);
291            // zeros need never update
292
293            R = normalform(P, R);
294        }
295        R = R.sum(Rc);
296        //System.out.println("R+Rc = " + R);
297        return R;
298    }
299
300
301    /**
302     * Total reduced normalform with Mora's algorithm.
303     * @param P power series list.
304     * @return total-nf(p) for p with respect to P\{p}.
305     */
306    public List<MultiVarPowerSeries<C>> totalNormalform(List<MultiVarPowerSeries<C>> P) {
307        if (P == null || P.isEmpty()) {
308            return P;
309        }
310        //StandardBaseSeq<C> std = new StandardBaseSeq<C>();
311        List<MultiVarPowerSeries<C>> R = new ArrayList<MultiVarPowerSeries<C>>(P.size());
312        List<MultiVarPowerSeries<C>> S = new ArrayList<MultiVarPowerSeries<C>>(P);
313        for (MultiVarPowerSeries<C> a : P) {
314            //S.remove(a);
315            //if ( !std.isSTD(S) ) {
316            //    System.out.println("a = " + a);
317            //}
318            Map.Entry<ExpVector, C> m = a.orderMonomial();
319            if (m == null) {
320                //S.add(a);
321                continue;
322            }
323            MultiVarPowerSeries<C> r = a.reductum();
324
325            MultiVarPowerSeries<C> b = normalform(S, r);
326            // need also unit of reduction: u r --> b
327            // b = b.multiply(u);
328            b = b.sum(m);
329            if (!b.isZERO()) {
330                R.add(b);
331            }
332        }
333        return R;
334    }
335
336
337    /**
338     * Is top reducible.
339     * @param A power series.
340     * @param P power series list.
341     * @return true if A is top reducible with respect to P.
342     */
343    public boolean isTopReducible(List<MultiVarPowerSeries<C>> P, MultiVarPowerSeries<C> A) {
344        if (P == null || P.isEmpty()) {
345            return false;
346        }
347        if (A == null) {
348            return false;
349        }
350        ExpVector e = A.orderExpVector();
351        if (e == null) {
352            return false;
353        }
354        for (MultiVarPowerSeries<C> p : P) {
355            ExpVector ep = p.orderExpVector();
356            if (ep == null) { // found by findbugs
357                continue;
358            }
359            if (e.multipleOf(ep)) {
360                return true;
361            }
362        }
363        return false;
364    }
365
366
367    /**
368     * Ideal containment. Test if each b in B is contained in ideal S.
369     * @param S standard base.
370     * @param B list of power series
371     * @return true, if each b in B is contained in ideal(S), else false
372     */
373    public boolean contains(List<MultiVarPowerSeries<C>> S, List<MultiVarPowerSeries<C>> B) {
374        if (B == null || B.size() == 0) {
375            return true;
376        }
377        if (S == null || S.size() == 0) {
378            return true;
379        }
380        for (MultiVarPowerSeries<C> b : B) {
381            if (b == null) {
382                continue;
383            }
384            MultiVarPowerSeries<C> z = normalform(S, b);
385            if (!z.isZERO()) {
386                System.out.println("contains nf(b) != 0: " + b + ", z = " + z);
387                return false;
388            }
389        }
390        return true;
391    }
392
393}