Source code

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