001/* 002 * $Id: GroebnerBaseFGLM.java 4177 2012-09-09 10:44:00Z suess $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import org.apache.log4j.Logger; 012 013import edu.jas.gb.GroebnerBaseAbstract; 014import edu.jas.gb.PairList; 015import edu.jas.gb.Reduction; 016import edu.jas.gb.ReductionSeq; 017import edu.jas.poly.ExpVector; 018import edu.jas.poly.GenPolynomial; 019import edu.jas.poly.GenPolynomialRing; 020import edu.jas.poly.PolyUtil; 021import edu.jas.poly.TermOrder; 022import edu.jas.structure.GcdRingElem; 023import edu.jas.structure.RingFactory; 024 025 026/** 027 * Groebner Base sequential FGLM algorithm. Implements Groebner base computation 028 * via FGLM algorithm. 029 * @param <C> coefficient type 030 * @author Jan Suess 031 * 032 * @see edu.jas.application.GBAlgorithmBuilder 033 * @see edu.jas.gbufd.GBFactory 034 */ 035public class GroebnerBaseFGLM<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<C> { 036 037 038 private static final Logger logger = Logger.getLogger(GroebnerBaseFGLM.class); 039 040 041 //private final boolean debug = logger.isDebugEnabled(); 042 043 044 /** 045 * The backing GB algorithm implementation. 046 */ 047 private GroebnerBaseAbstract<C> sgb; 048 049 050 /** 051 * Constructor. 052 */ 053 public GroebnerBaseFGLM() { 054 super(); 055 sgb = null; 056 } 057 058 059 /** 060 * Constructor. 061 * @param red Reduction engine 062 */ 063 public GroebnerBaseFGLM(Reduction<C> red) { 064 super(red); 065 sgb = null; 066 } 067 068 069 /** 070 * Constructor. 071 * @param red Reduction engine 072 * @param pl pair selection strategy 073 */ 074 public GroebnerBaseFGLM(Reduction<C> red, PairList<C> pl) { 075 super(red, pl); 076 sgb = null; 077 } 078 079 080 /** 081 * Constructor. 082 * @param red Reduction engine 083 * @param pl pair selection strategy 084 * @param gb backing GB algorithm. 085 */ 086 public GroebnerBaseFGLM(Reduction<C> red, PairList<C> pl, GroebnerBaseAbstract<C> gb) { 087 super(red, pl); 088 sgb = gb; 089 } 090 091 092 /** 093 * Constructor. 094 * @param gb backing GB algorithm. 095 */ 096 public GroebnerBaseFGLM(GroebnerBaseAbstract<C> gb) { 097 super(); 098 sgb = gb; 099 } 100 101 102 /** 103 * Groebner base using FGLM algorithm. 104 * @param modv module variable number. 105 * @param F polynomial list. 106 * @return GB(F) a inv lex term order Groebner base of F. 107 */ 108 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 109 if (modv != 0) { 110 throw new UnsupportedOperationException("case modv != 0 not yet implemented"); 111 } 112 if (F == null || F.size() == 0) { 113 return F; 114 } 115 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(); 116 if (F.size() <= 1) { 117 GenPolynomial<C> p = F.get(0).monic(); 118 G.add(p); 119 return G; 120 } 121 // convert to graded term order 122 List<GenPolynomial<C>> Fp = new ArrayList<GenPolynomial<C>>(F.size()); 123 GenPolynomialRing<C> pfac = F.get(0).ring; 124 if (!pfac.coFac.isField()) { 125 throw new IllegalArgumentException("coefficients not from a field: " + pfac.coFac); 126 } 127 TermOrder tord = new TermOrder(TermOrder.IGRLEX); 128 GenPolynomialRing<C> gfac = new GenPolynomialRing<C>(pfac.coFac, pfac.nvar, tord, pfac.getVars()); 129 for (GenPolynomial<C> p : F) { 130 GenPolynomial<C> g = gfac.copy(p); // change term order 131 Fp.add(g); 132 } 133 // compute graded term order Groebner base 134 if (sgb == null) { 135 sgb = GBFactory.<C> getImplementation(pfac.coFac); 136 } 137 List<GenPolynomial<C>> Gp = sgb.GB(modv, Fp); 138 logger.info("graded GB = " + Gp); 139 if (tord.equals(pfac.tord)) { 140 return Gp; 141 } 142 if (Gp.size() == 0) { 143 return Gp; 144 } 145 if (Gp.size() == 1) { 146 GenPolynomial<C> p = pfac.copy(Gp.get(0)); // change term order 147 G.add(p); 148 return G; 149 } 150 // compute invlex Groebner base via FGLM 151 G = convGroebnerToLex(Gp); 152 return G; 153 } 154 155 156 /** 157 * Algorithm CONVGROEBNER: Converts Groebner bases w.r.t. total degree 158 * termorder into Groebner base w.r.t to inverse lexicographical term order 159 * @return Groebner base w.r.t to inverse lexicographical term order 160 */ 161 public List<GenPolynomial<C>> convGroebnerToLex(List<GenPolynomial<C>> groebnerBasis) { 162 if (groebnerBasis == null || groebnerBasis.size() == 0) { 163 throw new IllegalArgumentException("G may not be null or empty"); 164 } 165 int z = commonZeroTest(groebnerBasis); 166 if (z != 0) { 167 throw new IllegalArgumentException("ideal(G) not zero dimensional, dim = " + z); 168 } 169 //Polynomial ring of input Groebnerbasis G 170 GenPolynomialRing<C> ring = groebnerBasis.get(0).ring; 171 int numberOfVariables = ring.nvar; //Number of Variables of the given Polynomial Ring 172 String[] ArrayOfVariables = ring.getVars(); //Variables of given polynomial ring w.r.t. to input G 173 RingFactory<C> cfac = ring.coFac; 174 175 //Main Algorithm 176 //Initialization 177 178 TermOrder invlex = new TermOrder(TermOrder.INVLEX); 179 //Polynomial ring of newGB with invlex order 180 GenPolynomialRing<C> ufac = new GenPolynomialRing<C>(cfac, numberOfVariables, invlex, 181 ArrayOfVariables); 182 183 //Local Lists 184 List<GenPolynomial<C>> newGB = new ArrayList<GenPolynomial<C>>(); //Instantiate the return list of polynomials 185 List<GenPolynomial<C>> H = new ArrayList<GenPolynomial<C>>(); //Instantiate a help list of polynomials 186 List<GenPolynomial<C>> redTerms = new ArrayList<GenPolynomial<C>>();//Instantiate the return list of reduced terms 187 188 //Local Polynomials 189 GenPolynomial<C> t = ring.ONE; //Create ONE polynom of original polynomial ring 190 GenPolynomial<C> h; //Create help polynomial 191 GenPolynomial<GenPolynomial<C>> hh; //h as polynomial in rfac 192 GenPolynomial<GenPolynomial<C>> p; //Create another help polynomial 193 redTerms.add(t); //Add ONE to list of reduced terms 194 195 //create new indeterminate Y1 196 int indeterminates = 1; //Number of indeterminates, starting with Y1 197 GenPolynomialRing<C> cpfac = createRingOfIndeterminates(ring, indeterminates); 198 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cpfac, ring); 199 GenPolynomial<GenPolynomial<C>> q = rfac.getZERO().sum(cpfac.univariate(0)); 200 201 //Main while loop 202 z = -1; 203 t = lMinterm(H, t); 204 while (t != null) { 205 //System.out.println("t = " + t); 206 h = red.normalform(groebnerBasis, t); 207 //System.out.println("Zwischennormalform h = " + h.toString()); 208 hh = PolyUtil.<C> toRecursive(rfac, h); 209 p = hh.sum(q); 210 List<GenPolynomial<C>> Cf = new ArrayList<GenPolynomial<C>>(p.getMap().values()); 211 Cf = red.irreducibleSet(Cf); 212 //System.out.println("Cf = " + Cf); 213 //System.out.println("Current Polynomial ring in Y_n: " + rfac.toString()); 214 215 z = commonZeroTest(Cf); 216 //System.out.println("z = " + z); 217 if (z != 0) { //z=1 OR z=-1 --> Infinite number of solutions OR No solution 218 indeterminates++; //then, increase number of indeterminates by one 219 redTerms.add(t); //add current t to list of reduced terms 220 cpfac = addIndeterminate(cpfac); 221 rfac = new GenPolynomialRing<GenPolynomial<C>>(cpfac, ring); 222 hh = PolyUtil.<C> toRecursive(rfac, h); 223 GenPolynomial<GenPolynomial<C>> Yt = rfac.getZERO().sum(cpfac.univariate(0)); 224 GenPolynomial<GenPolynomial<C>> Yth = hh.multiply(Yt); 225 q = PolyUtil.<C> extendCoefficients(rfac, q, 0, 0L); 226 q = Yth.sum(q); 227 } else { // z=0 --> one solution 228 GenPolynomial<C> g = ufac.getZERO(); 229 for (GenPolynomial<C> pc : Cf) { 230 ExpVector e = pc.leadingExpVector(); 231 //System.out.println("e = " + e); 232 if (e == null) { 233 continue; 234 } 235 int[] v = e.dependencyOnVariables(); 236 if (v == null || v.length == 0) { 237 continue; 238 } 239 int vi = v[0]; 240 vi = indeterminates - vi; 241 C tc = pc.trailingBaseCoefficient(); 242 if (!tc.isZERO()) { 243 tc = tc.negate(); 244 GenPolynomial<C> csRedterm = redTerms.get(vi - 1).multiply(tc); 245 //System.out.println("csRedterm = " + csRedterm); 246 g = g.sum(csRedterm); 247 } 248 } 249 g = g.sum(t); 250 g = ufac.copy(g); 251 H.add(t); 252 if (!g.isZERO()) { 253 newGB.add(g); 254 logger.info("new element for GB = " + g.leadingExpVector()); 255 } 256 } 257 t = lMinterm(H, t); // compute lMINTERM of current t (lexMinterm) 258 } 259 //logger.info("GB = " + newGB); 260 return newGB; 261 } 262 263 264 /** 265 * Algorithm lMinterm: MINTERM algorithm for inverse lexicographical term 266 * order. 267 * @param t Term 268 * @param G Groebner basis 269 * @return Term that specifies condition (D) or null (Condition (D) in 270 * "A computational approach to commutative algebra", Becker, 271 * Weispfenning, Kredel, 1993, p. 427) 272 */ 273 public GenPolynomial<C> lMinterm(List<GenPolynomial<C>> G, GenPolynomial<C> t) { 274 //not ok: if ( G == null || G.size() == 0 ) ... 275 GenPolynomialRing<C> ring = t.ring; 276 int numberOfVariables = ring.nvar; 277 GenPolynomial<C> u = new GenPolynomial<C>(ring, t.leadingBaseCoefficient(), t.leadingExpVector()); //HeadTerm of of input polynomial 278 ReductionSeq<C> redHelp = new ReductionSeq<C>(); // Create instance of ReductionSeq to use method isReducible 279 //not ok: if ( redHelp.isTopReducible(G,u) ) ... 280 for (int i = numberOfVariables - 1; i >= 0; i--) { // Walk through all variables, starting with least w.r.t to lex-order 281 GenPolynomial<C> x = ring.univariate(i); // Create Linear Polynomial X_i 282 u = u.multiply(x); // Multiply current u with x 283 if (!redHelp.isTopReducible(G, u)) { // Check if any term in HT(G) divides current u 284 return u; 285 } 286 GenPolynomial<C> s = ring.univariate(i, u.degree(numberOfVariables - (i + 1))); //if not, eliminate variable x_i 287 u = u.divide(s); 288 } 289 return null; 290 } 291 292 293 /** 294 * Compute the residues to given polynomial list. 295 * @return List of reduced terms 296 */ 297 public List<GenPolynomial<C>> redTerms(List<GenPolynomial<C>> groebnerBasis) { 298 if (groebnerBasis == null || groebnerBasis.size() == 0) { 299 throw new IllegalArgumentException("groebnerBasis may not be null or empty"); 300 } 301 GenPolynomialRing<C> ring = groebnerBasis.get(0).ring; 302 int numberOfVariables = ring.nvar; //Number of Variables of the given Polynomial Ring 303 long[] degrees = new long[numberOfVariables]; //Array for the degree-limits for the reduced terms 304 305 List<GenPolynomial<C>> terms = new ArrayList<GenPolynomial<C>>(); //Instantiate the return object 306 for (GenPolynomial<C> g : groebnerBasis) { //For each polynomial of G 307 if (g.isONE()) { 308 terms.clear(); 309 return terms; //If 1 e G, return empty list terms 310 } 311 ExpVector e = g.leadingExpVector(); //Take the exponent of the leading monomial 312 if (e.totalDeg() == e.maxDeg()) { //and check, whether a variable x_i is isolated 313 for (int i = 0; i < numberOfVariables; i++) { 314 long exp = e.getVal(i); 315 if (exp > 0) { 316 degrees[i] = exp; //if true, add the degree of univariate x_i to array degrees 317 } 318 } 319 } 320 } 321 long max = maxArray(degrees); //Find maximum in Array degrees 322 for (int i = 0; i < degrees.length; i++) { //Set all zero grades to maximum of array "degrees" 323 if (degrees[i] == 0) { 324 logger.info("dimension not zero, setting degree to " + max); 325 degrees[i] = max; //--> to "make" the ideal zero-dimensional 326 } 327 } 328 terms.add(ring.ONE); //Add the one-polynomial of the ring to the list of reduced terms 329 ReductionSeq<C> s = new ReductionSeq<C>(); //Create instance of ReductionSeq to use method isReducible 330 331 //Main Algorithm 332 for (int i = 0; i < numberOfVariables; i++) { 333 GenPolynomial<C> x = ring.univariate(i); //Create Linear Polynomial X_i 334 List<GenPolynomial<C>> S = new ArrayList<GenPolynomial<C>>(terms); //Copy all entries of return list "terms" into list "S" 335 for (GenPolynomial<C> t : S) { 336 for (int l = 1; l <= degrees[i]; l++) { 337 t = t.multiply(x); //Multiply current element t with Linear Polynomial X_i 338 if (!s.isReducible(groebnerBasis, t)) { //Check, if t is irreducible mod groebnerbase 339 terms.add(t); //Add t to return list terms 340 } 341 } 342 } 343 } 344 return terms; 345 } 346 347 348 /** 349 * Internal method to create a polynomial ring in i indeterminates. Create 350 * new ring over coefficients of ring with i variables Y1,...,Yi 351 * (indeterminate) 352 * @return polynomial ring with variables Y1...Yi and coefficient of ring. 353 */ 354 GenPolynomialRing<C> createRingOfIndeterminates(GenPolynomialRing<C> ring, int i) { 355 RingFactory<C> cfac = ring.coFac; 356 int indeterminates = i; 357 String[] stringIndeterminates = new String[indeterminates]; 358 for (int j = 1; j <= indeterminates; j++) { 359 stringIndeterminates[j - 1] = ("Y" + j); 360 } 361 TermOrder invlex = new TermOrder(TermOrder.INVLEX); 362 GenPolynomialRing<C> cpfac = new GenPolynomialRing<C>(cfac, indeterminates, invlex, 363 stringIndeterminates); 364 return cpfac; 365 } 366 367 368 /** 369 * Internal method to add new indeterminates. Add another variabe 370 * (indeterminate) Y_{i+1} to existing ring 371 * @return polynomial ring with variables Y1,..,Yi,Yi+1 and coefficients of 372 * ring. 373 */ 374 GenPolynomialRing<C> addIndeterminate(GenPolynomialRing<C> ring) { 375 String[] stringIndeterminates = new String[1]; 376 int number = ring.nvar + 1; 377 stringIndeterminates[0] = ("Y" + number); 378 ring = ring.extend(stringIndeterminates); 379 return ring; 380 } 381 382 383 /** 384 * Maximum of an array. 385 * @return maximum of an array 386 */ 387 long maxArray(long[] t) { 388 if (t.length == 0) { 389 return 0L; 390 } 391 long maximum = t[0]; 392 for (int i = 1; i < t.length; i++) { 393 if (t[i] > maximum) { 394 maximum = t[i]; 395 } 396 } 397 return maximum; 398 } 399 400 401 /** 402 * Cleanup and terminate ThreadPool. 403 */ 404 public void terminate() { 405 if ( sgb == null ) { 406 return; 407 } 408 sgb.terminate(); 409 } 410 411 412 /** 413 * Cancel ThreadPool. 414 */ 415 public int cancel() { 416 if ( sgb == null ) { 417 return 0; 418 } 419 return sgb.cancel(); 420 } 421 422}