001 /*
002 * $Id: GroebnerBasePseudoSeq.java 3626 2011-05-08 09:51:57Z kredel $
003 */
004
005 package edu.jas.gbufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.ListIterator;
011 import java.util.Collections;
012
013 import org.apache.log4j.Logger;
014
015 import edu.jas.gb.GroebnerBaseAbstract;
016 import edu.jas.gb.OrderedPairlist;
017 import edu.jas.gb.Pair;
018 import edu.jas.poly.GenPolynomial;
019 import edu.jas.structure.GcdRingElem;
020 import edu.jas.structure.RingFactory;
021 import edu.jas.ufd.GCDFactory;
022 import edu.jas.ufd.GreatestCommonDivisorAbstract;
023
024
025 /**
026 * Groebner Base with pseudo reduction sequential algorithm. Implements Groebner
027 * bases and GB test.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 */
031
032 public class GroebnerBasePseudoSeq<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<C> {
033
034
035 private static final Logger logger = Logger.getLogger(GroebnerBasePseudoSeq.class);
036
037
038 private final boolean debug = logger.isDebugEnabled();
039
040
041 /**
042 * Greatest common divisor engine for coefficient content and primitive
043 * parts.
044 */
045 protected final GreatestCommonDivisorAbstract<C> engine;
046
047
048 /**
049 * Pseudo reduction engine.
050 */
051 protected final PseudoReduction<C> red;
052
053
054 /**
055 * Coefficient ring factory.
056 */
057 protected final RingFactory<C> cofac;
058
059
060 /**
061 * Constructor.
062 * @param rf coefficient ring factory.
063 */
064 public GroebnerBasePseudoSeq(RingFactory<C> rf) {
065 this(new PseudoReductionSeq<C>(), rf);
066 }
067
068
069 /**
070 * Constructor.
071 * @param red pseudo reduction engine.
072 * @param rf coefficient ring factory. <b>Note:</b> red must be an instance
073 * of PseudoReductionSeq.
074 */
075 public GroebnerBasePseudoSeq(PseudoReduction<C> red, RingFactory<C> rf) {
076 super(red);
077 this.red = red;
078 cofac = rf;
079 engine = GCDFactory.<C> getImplementation(rf);
080 //not used: engine = (GreatestCommonDivisorAbstract<C>)GCDFactory.<C>getProxy( rf );
081 }
082
083
084 /**
085 * Groebner base using pairlist class.
086 * @param modv module variable number.
087 * @param F polynomial list.
088 * @return GB(F) a Groebner base of F.
089 */
090 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
091 GenPolynomial<C> p;
092 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
093 OrderedPairlist<C> pairlist = null;
094 int l = F.size();
095 ListIterator<GenPolynomial<C>> it = F.listIterator();
096 while (it.hasNext()) {
097 p = it.next();
098 if (p.length() > 0) {
099 p = engine.basePrimitivePart(p); //p.monic();
100 p = p.abs();
101 if (p.isConstant()) {
102 G.clear();
103 G.add(p);
104 return G; // since no threads are activated
105 }
106 G.add(p);
107 if (pairlist == null) {
108 pairlist = new OrderedPairlist<C>(modv, p.ring);
109 }
110 // putOne not required
111 pairlist.put(p);
112 } else {
113 l--;
114 }
115 }
116 if (l <= 1) {
117 return G; // since no threads are activated
118 }
119
120 Pair<C> pair;
121 GenPolynomial<C> pi;
122 GenPolynomial<C> pj;
123 GenPolynomial<C> S;
124 GenPolynomial<C> H;
125 while (pairlist.hasNext()) {
126 pair = pairlist.removeNext();
127 if (pair == null)
128 continue;
129
130 pi = pair.pi;
131 pj = pair.pj;
132 if (false && logger.isDebugEnabled()) {
133 logger.debug("pi = " + pi);
134 logger.debug("pj = " + pj);
135 }
136
137 S = red.SPolynomial(pi, pj);
138 if (S.isZERO()) {
139 pair.setZero();
140 continue;
141 }
142 if (logger.isDebugEnabled()) {
143 logger.debug("ht(S) = " + S.leadingExpVector());
144 }
145
146 H = red.normalform(G, S);
147 if (H.isZERO()) {
148 pair.setZero();
149 continue;
150 }
151 if (logger.isDebugEnabled()) {
152 logger.debug("ht(H) = " + H.leadingExpVector());
153 }
154 H = engine.basePrimitivePart(H); //H.monic();
155 H = H.abs();
156 if (H.isConstant()) {
157 G.clear();
158 G.add(H);
159 return G; // since no threads are activated
160 }
161 if (logger.isDebugEnabled()) {
162 logger.debug("H = " + H);
163 }
164 if (H.length() > 0) {
165 l++;
166 G.add(H);
167 pairlist.put(H);
168 }
169 }
170 logger.debug("#sequential list = " + G.size());
171 G = minimalGB(G);
172 logger.info("" + pairlist);
173 return G;
174 }
175
176
177 /**
178 * Minimal ordered Groebner basis.
179 * @param Gp a Groebner base.
180 * @return a reduced Groebner base of Gp.
181 */
182 @Override
183 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Gp) {
184 if (Gp == null || Gp.size() <= 1) {
185 return Gp;
186 }
187 // remove zero polynomials
188 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(Gp.size());
189 for (GenPolynomial<C> a : Gp) {
190 if (a != null && !a.isZERO()) { // always true in GB()
191 // already positive a = a.abs();
192 G.add(a);
193 }
194 }
195 if (G.size() <= 1) {
196 return G;
197 }
198 // remove top reducible polynomials
199 GenPolynomial<C> a;
200 List<GenPolynomial<C>> F;
201 F = new ArrayList<GenPolynomial<C>>(G.size());
202 while (G.size() > 0) {
203 a = G.remove(0);
204 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
205 // drop polynomial
206 if (debug) {
207 System.out.println("dropped " + a);
208 List<GenPolynomial<C>> ff;
209 ff = new ArrayList<GenPolynomial<C>>(G);
210 ff.addAll(F);
211 a = red.normalform(ff, a);
212 if (!a.isZERO()) {
213 System.out.println("error, nf(a) " + a);
214 }
215 }
216 } else {
217 F.add(a);
218 }
219 }
220 G = F;
221 if (G.size() <= 1) {
222 return G;
223 }
224 Collections.reverse(G); // important for lex GB
225 // reduce remaining polynomials
226 int len = G.size();
227 int i = 0;
228 while (i < len) {
229 a = G.remove(0);
230 //System.out.println("doing " + a.length());
231 a = red.normalform(G, a);
232 a = engine.basePrimitivePart(a); //a.monic(); was not required
233 a = a.abs();
234 //a = red.normalform( F, a );
235 G.add(a); // adds as last
236 i++;
237 }
238 return G;
239 }
240
241 }