001 /*
002 * $Id: GroebnerBaseSeqPairSeq.java 3414 2010-12-19 12:47:23Z kredel $
003 */
004
005 package edu.jas.gb;
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.poly.GenPolynomial;
015 import edu.jas.poly.GenPolynomialRing;
016 import edu.jas.structure.RingElem;
017
018
019 /**
020 * Groebner Base sequential algorithm. Implements Groebner bases and GB test.
021 * Uses sequential pair list class.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025
026 public class GroebnerBaseSeqPairSeq<C extends RingElem<C>> extends GroebnerBaseAbstract<C> {
027
028
029 private static final Logger logger = Logger.getLogger(GroebnerBaseSeqPairSeq.class);
030
031
032 private final boolean debug = logger.isDebugEnabled();
033
034
035 /**
036 * Constructor.
037 */
038 public GroebnerBaseSeqPairSeq() {
039 super();
040 }
041
042
043 /**
044 * Constructor.
045 * @param red Reduction engine
046 */
047 public GroebnerBaseSeqPairSeq(Reduction<C> red) {
048 super(red);
049 }
050
051
052 /**
053 * Groebner base using pairlist class.
054 * @param modv module variable number.
055 * @param F polynomial list.
056 * @return GB(F) a Groebner base of F.
057 */
058 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
059 GenPolynomial<C> p;
060 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
061 CriticalPairList<C> pairlist = null;
062 int len = F.size();
063 ListIterator<GenPolynomial<C>> it = F.listIterator();
064 while (it.hasNext()) {
065 p = it.next();
066 if (p.length() > 0) {
067 p = p.monic();
068 if (p.isONE()) {
069 G.clear();
070 G.add(p);
071 return G; // since no threads are activated
072 }
073 G.add(p);
074 if (pairlist == null) {
075 pairlist = new CriticalPairList<C>(modv, p.ring);
076 }
077 // putOne not required
078 pairlist.put(p);
079 } else {
080 len--;
081 }
082 }
083 if (len <= 1) {
084 return G; // since no threads are activated
085 }
086
087 CriticalPair<C> pair;
088 GenPolynomial<C> pi;
089 GenPolynomial<C> pj;
090 GenPolynomial<C> S;
091 GenPolynomial<C> H;
092 while (pairlist.hasNext()) {
093 pair = pairlist.getNext();
094 if (pair == null) {
095 pairlist.update(); // ?
096 continue;
097 }
098 pi = pair.pi;
099 pj = pair.pj;
100 if (debug) {
101 logger.debug("pi = " + pi);
102 logger.debug("pj = " + pj);
103 }
104
105 S = red.SPolynomial(pi, pj);
106 if (S.isZERO()) {
107 pairlist.update(pair, S);
108 continue;
109 }
110 if (debug) {
111 logger.debug("ht(S) = " + S.leadingExpVector());
112 }
113
114 H = red.normalform(G, S);
115 if (H.isZERO()) {
116 pairlist.update(pair, H);
117 continue;
118 }
119 if (debug) {
120 logger.debug("ht(H) = " + H.leadingExpVector());
121 }
122
123 H = H.monic();
124 if (H.isONE()) {
125 // pairlist.record( pair, H );
126 G.clear();
127 G.add(H);
128 return G; // since no threads are activated
129 }
130 if (debug) {
131 logger.debug("H = " + H);
132 }
133 G.add(H);
134 pairlist.update(pair, H);
135 //pairlist.update();
136 }
137 logger.debug("#sequential list = " + G.size());
138 G = minimalGB(G);
139 logger.info("" + pairlist);
140 return G;
141 }
142
143
144 /**
145 * Extended Groebner base using critical pair class.
146 * @param modv module variable number.
147 * @param F polynomial list.
148 * @return a container for an extended Groebner base of F.
149 */
150 @Override
151 public ExtendedGB<C> extGB(int modv, List<GenPolynomial<C>> F) {
152 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
153 List<List<GenPolynomial<C>>> F2G = new ArrayList<List<GenPolynomial<C>>>();
154 List<List<GenPolynomial<C>>> G2F = new ArrayList<List<GenPolynomial<C>>>();
155 CriticalPairList<C> pairlist = null;
156 boolean oneInGB = false;
157 int len = F.size();
158
159 List<GenPolynomial<C>> row = null;
160 List<GenPolynomial<C>> rows = null;
161 List<GenPolynomial<C>> rowh = null;
162 GenPolynomialRing<C> ring = null;
163 GenPolynomial<C> H;
164 GenPolynomial<C> p;
165
166 int nzlen = 0;
167 for (GenPolynomial<C> f : F) {
168 if (f.length() > 0) {
169 nzlen++;
170 }
171 if (ring == null) {
172 ring = f.ring;
173 }
174 }
175 GenPolynomial<C> mone = ring.getONE(); //.negate();
176 int k = 0;
177 ListIterator<GenPolynomial<C>> it = F.listIterator();
178 while (it.hasNext()) {
179 p = it.next();
180 if (p.length() > 0) {
181 row = new ArrayList<GenPolynomial<C>>(nzlen);
182 for (int j = 0; j < nzlen; j++) {
183 row.add(null);
184 }
185 //C c = p.leadingBaseCoefficient();
186 //c = c.inverse();
187 //p = p.multiply( c );
188 row.set(k, mone); //.multiply(c) );
189 k++;
190 if (p.isUnit()) {
191 G.clear();
192 G.add(p);
193 G2F.clear();
194 G2F.add(row);
195 oneInGB = true;
196 break;
197 }
198 G.add(p);
199 G2F.add(row);
200 if (pairlist == null) {
201 pairlist = new CriticalPairList<C>(modv, p.ring);
202 }
203 // putOne not required
204 pairlist.put(p);
205 } else {
206 len--;
207 }
208 }
209 ExtendedGB<C> exgb;
210 if (len <= 1 || oneInGB) {
211 // adjust F2G
212 for (GenPolynomial<C> f : F) {
213 row = new ArrayList<GenPolynomial<C>>(G.size());
214 for (int j = 0; j < G.size(); j++) {
215 row.add(null);
216 }
217 H = red.normalform(row, G, f);
218 if (!H.isZERO()) {
219 logger.error("nonzero H = " + H);
220 }
221 F2G.add(row);
222 }
223 exgb = new ExtendedGB<C>(F, G, F2G, G2F);
224 //System.out.println("exgb 1 = " + exgb);
225 return exgb;
226 }
227
228 CriticalPair<C> pair;
229 int i, j;
230 GenPolynomial<C> pi;
231 GenPolynomial<C> pj;
232 GenPolynomial<C> S;
233 GenPolynomial<C> x;
234 GenPolynomial<C> y;
235 //GenPolynomial<C> z;
236 while (pairlist.hasNext() && !oneInGB) {
237 pair = pairlist.getNext();
238 if (pair == null) {
239 pairlist.update(); // ?
240 continue;
241 }
242 i = pair.i;
243 j = pair.j;
244 pi = pair.pi;
245 pj = pair.pj;
246 if (debug) {
247 logger.info("i, pi = " + i + ", " + pi);
248 logger.info("j, pj = " + j + ", " + pj);
249 }
250
251 rows = new ArrayList<GenPolynomial<C>>(G.size());
252 for (int m = 0; m < G.size(); m++) {
253 rows.add(null);
254 }
255 S = red.SPolynomial(rows, i, pi, j, pj);
256 if (debug) {
257 logger.debug("is reduction S = " + red.isReductionNF(rows, G, ring.getZERO(), S));
258 }
259 if (S.isZERO()) {
260 pairlist.update(pair, S);
261 // do not add to G2F
262 continue;
263 }
264 if (debug) {
265 logger.debug("ht(S) = " + S.leadingExpVector());
266 }
267
268 rowh = new ArrayList<GenPolynomial<C>>(G.size());
269 for (int m = 0; m < G.size(); m++) {
270 rowh.add(null);
271 }
272 H = red.normalform(rowh, G, S);
273 if (debug) {
274 logger.debug("is reduction H = " + red.isReductionNF(rowh, G, S, H));
275 }
276 if (H.isZERO()) {
277 pairlist.update(pair, H);
278 // do not add to G2F
279 continue;
280 }
281 if (debug) {
282 logger.debug("ht(H) = " + H.leadingExpVector());
283 }
284
285 row = new ArrayList<GenPolynomial<C>>(G.size() + 1);
286 for (int m = 0; m < G.size(); m++) {
287 x = rows.get(m);
288 if (x != null) {
289 //System.out.println("ms = " + m + " " + x);
290 x = x.negate();
291 }
292 y = rowh.get(m);
293 if (y != null) {
294 y = y.negate();
295 //System.out.println("mh = " + m + " " + y);
296 }
297 if (x == null) {
298 x = y;
299 } else {
300 x = x.sum(y);
301 }
302 //System.out.println("mx = " + m + " " + x);
303 row.add(x);
304 }
305 if (debug) {
306 logger.debug("is reduction 0+sum(row,G) == H : "
307 + red.isReductionNF(row, G, H, ring.getZERO()));
308 }
309 row.add(null);
310
311
312 // H = H.monic();
313 C c = H.leadingBaseCoefficient();
314 c = c.inverse();
315 H = H.multiply(c);
316 row = blas.scalarProduct(mone.multiply(c), row);
317 row.set(G.size(), mone);
318 if (H.isONE()) {
319 // pairlist.record( pair, H );
320 // G.clear();
321 G.add(H);
322 G2F.add(row);
323 oneInGB = true;
324 break;
325 }
326 if (debug) {
327 logger.debug("H = " + H);
328 }
329 G.add(H);
330 pairlist.update(pair, H);
331 G2F.add(row);
332 }
333 if (debug) {
334 exgb = new ExtendedGB<C>(F, G, F2G, G2F);
335 logger.info("exgb unnorm = " + exgb);
336 }
337 G2F = normalizeMatrix(F.size(), G2F);
338 if (debug) {
339 exgb = new ExtendedGB<C>(F, G, F2G, G2F);
340 logger.info("exgb nonmin = " + exgb);
341 boolean t2 = isReductionMatrix(exgb);
342 logger.info("exgb t2 = " + t2);
343 }
344 exgb = minimalExtendedGB(F.size(), G, G2F);
345 G = exgb.G;
346 G2F = exgb.G2F;
347 logger.debug("#sequential list = " + G.size());
348 logger.info("" + pairlist);
349 // setup matrices F and F2G
350 for (GenPolynomial<C> f : F) {
351 row = new ArrayList<GenPolynomial<C>>(G.size());
352 for (int m = 0; m < G.size(); m++) {
353 row.add(null);
354 }
355 H = red.normalform(row, G, f);
356 if (!H.isZERO()) {
357 logger.error("nonzero H = " + H);
358 }
359 F2G.add(row);
360 }
361 exgb = new ExtendedGB<C>(F, G, F2G, G2F);
362 if (debug) {
363 logger.info("exgb nonmin = " + exgb);
364 boolean t2 = isReductionMatrix(exgb);
365 logger.info("exgb t2 = " + t2);
366 }
367 return exgb;
368 }
369
370 }