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