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