001/* 002 * $Id: GroebnerBaseFGLM.java 5374 2015-12-29 18:26:20Z kredel $ 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 logger.error("use Groebner Walk algorithm"); 168 throw new IllegalArgumentException("ideal(G) not zero dimensional, dim = " + z); 169 } 170 //Polynomial ring of input Groebnerbasis G 171 GenPolynomialRing<C> ring = groebnerBasis.get(0).ring; 172 int numberOfVariables = ring.nvar; //Number of Variables of the given Polynomial Ring 173 String[] ArrayOfVariables = ring.getVars(); //Variables of given polynomial ring w.r.t. to input G 174 RingFactory<C> cfac = ring.coFac; 175 176 //Main Algorithm 177 //Initialization 178 179 TermOrder invlex = new TermOrder(TermOrder.INVLEX); 180 //Polynomial ring of newGB with invlex order 181 GenPolynomialRing<C> ufac = new GenPolynomialRing<C>(cfac, numberOfVariables, invlex, 182 ArrayOfVariables); 183 184 //Local Lists 185 List<GenPolynomial<C>> newGB = new ArrayList<GenPolynomial<C>>(); //Instantiate the return list of polynomials 186 List<GenPolynomial<C>> H = new ArrayList<GenPolynomial<C>>(); //Instantiate a help list of polynomials 187 List<GenPolynomial<C>> redTerms = new ArrayList<GenPolynomial<C>>();//Instantiate the return list of reduced terms 188 189 //Local Polynomials 190 GenPolynomial<C> t = ring.ONE; //Create ONE polynom of original polynomial ring 191 GenPolynomial<C> h; //Create help polynomial 192 GenPolynomial<GenPolynomial<C>> hh; //h as polynomial in rfac 193 GenPolynomial<GenPolynomial<C>> p; //Create another help polynomial 194 redTerms.add(t); //Add ONE to list of reduced terms 195 196 //create new indeterminate Y1 197 int indeterminates = 1; //Number of indeterminates, starting with Y1 198 GenPolynomialRing<C> cpfac = createRingOfIndeterminates(ring, indeterminates); 199 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cpfac, ring); 200 GenPolynomial<GenPolynomial<C>> q = rfac.getZERO().sum(cpfac.univariate(0)); 201 202 //Main while loop 203 z = -1; 204 t = lMinterm(H, t); 205 while (t != null) { 206 //System.out.println("t = " + t); 207 h = red.normalform(groebnerBasis, t); 208 //System.out.println("Zwischennormalform h = " + h.toString()); 209 hh = PolyUtil.<C> toRecursive(rfac, h); 210 p = hh.sum(q); 211 List<GenPolynomial<C>> Cf = new ArrayList<GenPolynomial<C>>(p.getMap().values()); 212 Cf = red.irreducibleSet(Cf); 213 //System.out.println("Cf = " + Cf); 214 //System.out.println("Current Polynomial ring in Y_n: " + rfac.toString()); 215 216 z = commonZeroTest(Cf); 217 //System.out.println("z = " + z); 218 if (z != 0) { //z=1 OR z=-1 --> Infinite number of solutions OR No solution 219 indeterminates++; //then, increase number of indeterminates by one 220 redTerms.add(t); //add current t to list of reduced terms 221 cpfac = addIndeterminate(cpfac); 222 rfac = new GenPolynomialRing<GenPolynomial<C>>(cpfac, ring); 223 hh = PolyUtil.<C> toRecursive(rfac, h); 224 GenPolynomial<GenPolynomial<C>> Yt = rfac.getZERO().sum(cpfac.univariate(0)); 225 GenPolynomial<GenPolynomial<C>> Yth = hh.multiply(Yt); 226 q = PolyUtil.<C> extendCoefficients(rfac, q, 0, 0L); 227 q = Yth.sum(q); 228 } else { // z=0 --> one solution 229 GenPolynomial<C> g = ufac.getZERO(); 230 for (GenPolynomial<C> pc : Cf) { 231 ExpVector e = pc.leadingExpVector(); 232 //System.out.println("e = " + e); 233 if (e == null) { 234 continue; 235 } 236 int[] v = e.dependencyOnVariables(); 237 if (v == null || v.length == 0) { 238 continue; 239 } 240 int vi = v[0]; 241 vi = indeterminates - vi; 242 C tc = pc.trailingBaseCoefficient(); 243 if (!tc.isZERO()) { 244 tc = tc.negate(); 245 GenPolynomial<C> csRedterm = redTerms.get(vi - 1).multiply(tc); 246 //System.out.println("csRedterm = " + csRedterm); 247 g = g.sum(csRedterm); 248 } 249 } 250 g = g.sum(t); 251 g = ufac.copy(g); 252 H.add(t); 253 if (!g.isZERO()) { 254 newGB.add(g); 255 logger.info("new element for GB = " + g.leadingExpVector()); 256 } 257 } 258 t = lMinterm(H, t); // compute lMINTERM of current t (lexMinterm) 259 } 260 //logger.info("GB = " + newGB); 261 return newGB; 262 } 263 264 265 /** 266 * Algorithm lMinterm: MINTERM algorithm for inverse lexicographical term 267 * order. 268 * @param t Term 269 * @param G Groebner basis 270 * @return Term that specifies condition (D) or null (Condition (D) in 271 * "A computational approach to commutative algebra", Becker, 272 * Weispfenning, Kredel, 1993, p. 427) 273 */ 274 public GenPolynomial<C> lMinterm(List<GenPolynomial<C>> G, GenPolynomial<C> t) { 275 //not ok: if ( G == null || G.size() == 0 ) ... 276 GenPolynomialRing<C> ring = t.ring; 277 int numberOfVariables = ring.nvar; 278 GenPolynomial<C> u = new GenPolynomial<C>(ring, t.leadingBaseCoefficient(), t.leadingExpVector()); //HeadTerm of of input polynomial 279 ReductionSeq<C> redHelp = new ReductionSeq<C>(); // Create instance of ReductionSeq to use method isReducible 280 //not ok: if ( redHelp.isTopReducible(G,u) ) ... 281 for (int i = numberOfVariables - 1; i >= 0; i--) { // Walk through all variables, starting with least w.r.t to lex-order 282 GenPolynomial<C> x = ring.univariate(i); // Create Linear Polynomial X_i 283 u = u.multiply(x); // Multiply current u with x 284 if (!redHelp.isTopReducible(G, u)) { // Check if any term in HT(G) divides current u 285 return u; 286 } 287 GenPolynomial<C> s = ring.univariate(i, u.degree(numberOfVariables - (i + 1))); //if not, eliminate variable x_i 288 u = u.divide(s); 289 } 290 return null; 291 } 292 293 294 /** 295 * Compute the residues to given polynomial list. 296 * @return List of reduced terms 297 */ 298 public List<GenPolynomial<C>> redTerms(List<GenPolynomial<C>> groebnerBasis) { 299 if (groebnerBasis == null || groebnerBasis.size() == 0) { 300 throw new IllegalArgumentException("groebnerBasis may not be null or empty"); 301 } 302 GenPolynomialRing<C> ring = groebnerBasis.get(0).ring; 303 int numberOfVariables = ring.nvar; //Number of Variables of the given Polynomial Ring 304 long[] degrees = new long[numberOfVariables]; //Array for the degree-limits for the reduced terms 305 306 List<GenPolynomial<C>> terms = new ArrayList<GenPolynomial<C>>(); //Instantiate the return object 307 for (GenPolynomial<C> g : groebnerBasis) { //For each polynomial of G 308 if (g.isONE()) { 309 terms.clear(); 310 return terms; //If 1 e G, return empty list terms 311 } 312 ExpVector e = g.leadingExpVector(); //Take the exponent of the leading monomial 313 if (e.totalDeg() == e.maxDeg()) { //and check, whether a variable x_i is isolated 314 for (int i = 0; i < numberOfVariables; i++) { 315 long exp = e.getVal(i); 316 if (exp > 0) { 317 degrees[i] = exp; //if true, add the degree of univariate x_i to array degrees 318 } 319 } 320 } 321 } 322 long max = maxArray(degrees); //Find maximum in Array degrees 323 for (int i = 0; i < degrees.length; i++) { //Set all zero grades to maximum of array "degrees" 324 if (degrees[i] == 0) { 325 logger.info("dimension not zero, setting degree to " + max); 326 degrees[i] = max; //--> to "make" the ideal zero-dimensional 327 } 328 } 329 terms.add(ring.ONE); //Add the one-polynomial of the ring to the list of reduced terms 330 ReductionSeq<C> s = new ReductionSeq<C>(); //Create instance of ReductionSeq to use method isReducible 331 332 //Main Algorithm 333 for (int i = 0; i < numberOfVariables; i++) { 334 GenPolynomial<C> x = ring.univariate(i); //Create Linear Polynomial X_i 335 List<GenPolynomial<C>> S = new ArrayList<GenPolynomial<C>>(terms); //Copy all entries of return list "terms" into list "S" 336 for (GenPolynomial<C> t : S) { 337 for (int l = 1; l <= degrees[i]; l++) { 338 t = t.multiply(x); //Multiply current element t with Linear Polynomial X_i 339 if (!s.isReducible(groebnerBasis, t)) { //Check, if t is irreducible mod groebnerbase 340 terms.add(t); //Add t to return list terms 341 } 342 } 343 } 344 } 345 return terms; 346 } 347 348 349 /** 350 * Internal method to create a polynomial ring in i indeterminates. Create 351 * new ring over coefficients of ring with i variables Y1,...,Yi 352 * (indeterminate) 353 * @return polynomial ring with variables Y1...Yi and coefficient of ring. 354 */ 355 GenPolynomialRing<C> createRingOfIndeterminates(GenPolynomialRing<C> ring, int i) { 356 RingFactory<C> cfac = ring.coFac; 357 int indeterminates = i; 358 String[] stringIndeterminates = new String[indeterminates]; 359 for (int j = 1; j <= indeterminates; j++) { 360 stringIndeterminates[j - 1] = ("Y" + j); 361 } 362 TermOrder invlex = new TermOrder(TermOrder.INVLEX); 363 GenPolynomialRing<C> cpfac = new GenPolynomialRing<C>(cfac, indeterminates, invlex, 364 stringIndeterminates); 365 return cpfac; 366 } 367 368 369 /** 370 * Internal method to add new indeterminates. Add another variabe 371 * (indeterminate) Y_{i+1} to existing ring 372 * @return polynomial ring with variables Y1,..,Yi,Yi+1 and coefficients of 373 * ring. 374 */ 375 GenPolynomialRing<C> addIndeterminate(GenPolynomialRing<C> ring) { 376 String[] stringIndeterminates = new String[1]; 377 int number = ring.nvar + 1; 378 stringIndeterminates[0] = ("Y" + number); 379 ring = ring.extend(stringIndeterminates); 380 return ring; 381 } 382 383 384 /** 385 * Maximum of an array. 386 * @return maximum of an array 387 */ 388 long maxArray(long[] t) { 389 if (t.length == 0) { 390 return 0L; 391 } 392 long maximum = t[0]; 393 for (int i = 1; i < t.length; i++) { 394 if (t[i] > maximum) { 395 maximum = t[i]; 396 } 397 } 398 return maximum; 399 } 400 401 402 /** 403 * Cleanup and terminate ThreadPool. 404 */ 405 public void terminate() { 406 if ( sgb == null ) { 407 return; 408 } 409 sgb.terminate(); 410 } 411 412 413 /** 414 * Cancel ThreadPool. 415 */ 416 public int cancel() { 417 if ( sgb == null ) { 418 return 0; 419 } 420 return sgb.cancel(); 421 } 422 423}