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