001 /*
002 * $Id: ReductionSeq.java 3345 2010-10-15 19:50:36Z kredel $
003 */
004
005 package edu.jas.ps;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.Map;
011
012 import org.apache.log4j.Logger;
013
014 import edu.jas.poly.ExpVector;
015 import edu.jas.poly.GenPolynomial;
016 import edu.jas.poly.GenPolynomialRing;
017 import 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
027 public 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 (e == null) {
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 }