001/* 002 * $Id: GroebnerBasePartial.java 4116 2012-08-19 13:26:25Z 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.GroebnerBaseSeq; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenPolynomialRing; 018import edu.jas.poly.OptimizedPolynomialList; 019import edu.jas.poly.PolyUtil; 020import edu.jas.poly.TermOrder; 021import edu.jas.poly.TermOrderOptimization; 022import edu.jas.structure.GcdRingElem; 023import edu.jas.structure.RingFactory; 024 025 026/** 027 * Partial Groebner Bases for subsets of variables. Let <code>pvars</code> be a 028 * subset of variables <code>vars</code> of the polynomial ring K[vars]. Methods 029 * compute Groebner bases with coefficients from K[vars \ pvars] in the 030 * polynomial ring K[vars \ pvars][pvars]. 031 * @param <C> coefficient type 032 * @author Heinz Kredel 033 */ 034 035public class GroebnerBasePartial<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<C> { 036 037 038 private static final Logger logger = Logger.getLogger(GroebnerBasePartial.class); 039 040 041 //private final boolean debug = logger.isDebugEnabled(); 042 043 044 /** 045 * Backing Groebner base engine. 046 */ 047 protected GroebnerBaseAbstract<C> bb; 048 049 050 /** 051 * Backing recursive Groebner base engine. 052 */ 053 protected GroebnerBaseAbstract<GenPolynomial<C>> rbb; // can be null 054 055 056 /** 057 * Constructor. 058 */ 059 public GroebnerBasePartial() { 060 this(new GroebnerBaseSeq<C>(), null); 061 } 062 063 064 /** 065 * Constructor. 066 * @param rf coefficient ring factory. 067 */ 068 public GroebnerBasePartial(RingFactory<GenPolynomial<C>> rf) { 069 this(new GroebnerBaseSeq<C>(), new GroebnerBasePseudoRecSeq<C>(rf)); 070 } 071 072 073 /** 074 * Constructor. 075 * @param bb Groebner base engine 076 * @param rbb recursive Groebner base engine 077 */ 078 public GroebnerBasePartial(GroebnerBaseAbstract<C> bb, GroebnerBaseAbstract<GenPolynomial<C>> rbb) { 079 super(); 080 this.bb = bb; 081 this.rbb = rbb; 082 //if (rbb == null) { 083 //logger.warn("no recursive GB given"); 084 //} 085 } 086 087 088 /** 089 * Groebner base using pairlist class. 090 * @param modv module variable number. 091 * @param F polynomial list. 092 * @return GB(F) a Groebner base of F. 093 */ 094 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 095 return bb.GB(modv, F); 096 } 097 098 099 /** 100 * Groebner base test. 101 * @param F polynomial list. 102 * @return true, if F is a partial Groebner base, else false. 103 */ 104 public boolean isGBrec(List<GenPolynomial<GenPolynomial<C>>> F) { 105 return isGBrec(0, F); 106 } 107 108 109 /** 110 * Groebner base test. 111 * @param modv module variable number. 112 * @param F polynomial list. 113 * @return true, if F is a partial Groebner base, else false. 114 */ 115 public boolean isGBrec(int modv, List<GenPolynomial<GenPolynomial<C>>> F) { 116 if (F == null || F.isEmpty()) { 117 return true; 118 } 119 if (true) { 120 rbb = new GroebnerBasePseudoRecSeq<C>(F.get(0).ring.coFac); 121 } 122 return rbb.isGB(modv, F); 123 } 124 125 126 /** 127 * Partial permuation for specific variables. Computes a permutation perm 128 * for the variables vars, such that perm(vars) == pvars ... (vars \ pvars). 129 * Uses internal (reversed) variable sorting. 130 * @param vars names for all variables. 131 * @param pvars names for main variables, pvars subseteq vars. 132 * @return permutation for vars, such that perm(vars) == pvars ... (vars \ 133 * pvars). 134 */ 135 public static List<Integer> partialPermutation(String[] vars, String[] pvars) { 136 return partialPermutation(vars, pvars, null); 137 //no: return getPermutation(vars,pvars); 138 } 139 140 141 /** 142 * Permutation of variables for elimination. 143 * @param aname variables for the full polynomial ring. 144 * @param ename variables for the elimination ring, subseteq aname. 145 * @return perm({vars \ ename},ename) 146 */ 147 public static List<Integer> getPermutation(String[] aname, String[] ename) { 148 if (aname == null || ename == null) { 149 throw new IllegalArgumentException("aname or ename may not be null"); 150 } 151 List<Integer> perm = new ArrayList<Integer>(aname.length); 152 // add ename permutation 153 for (int i = 0; i < ename.length; i++) { 154 int j = indexOf(ename[i], aname); 155 if (j < 0) { 156 throw new IllegalArgumentException("ename not contained in aname"); 157 } 158 perm.add(j); 159 } 160 //System.out.println("perm_low = " + perm); 161 // add aname \ ename permutation 162 for (int i = 0; i < aname.length; i++) { 163 if (!perm.contains(i)) { 164 perm.add(i); 165 } 166 } 167 //System.out.println("perm_all = " + perm); 168 // reverse permutation indices 169 int n1 = aname.length - 1; 170 List<Integer> perm1 = new ArrayList<Integer>(aname.length); 171 for (Integer k : perm) { 172 perm1.add(n1 - k); 173 } 174 perm = perm1; 175 //System.out.println("perm_inv = " + perm1); 176 Collections.reverse(perm); 177 //System.out.println("perm_rev = " + perm); 178 return perm; 179 } 180 181 182 /** 183 * Index of s in A. 184 * @param s search string 185 * @param A string array 186 * @return i if s == A[i] for some i, else -1. 187 */ 188 public static int indexOf(String s, String[] A) { 189 for (int i = 0; i < A.length; i++) { 190 if (s.equals(A[i])) { 191 return i; 192 } 193 } 194 return -1; 195 } 196 197 198 /** 199 * Partial permuation for specific variables. Computes a permutation perm 200 * for the variables vars, such that perm(vars) == pvars ... (vars \ pvars). 201 * Uses internal (reversed) variable sorting. 202 * @param vars names for all variables. 203 * @param pvars names for main variables, pvars subseteq vars. 204 * @param rvars names for remaining variables, rvars eq { vars \ pvars }. 205 * @return permutation for vars, such that perm(vars) == (pvars, {vars \ 206 * pvars}). 207 */ 208 public static List<Integer> partialPermutation(String[] vars, String[] pvars, String[] rvars) { 209 if (vars == null || pvars == null) { 210 throw new IllegalArgumentException("no variable names found"); 211 } 212 List<String> variables = new ArrayList<String>(vars.length); 213 List<String> pvariables = new ArrayList<String>(pvars.length); 214 for (int i = 0; i < vars.length; i++) { 215 variables.add(vars[i]); 216 } 217 for (int i = 0; i < pvars.length; i++) { 218 pvariables.add(pvars[i]); 219 } 220 if (rvars == null) { 221 rvars = remainingVars(vars, pvars); 222 } 223 List<String> rvariables = new ArrayList<String>(rvars.length); 224 for (int i = 0; i < rvars.length; i++) { 225 rvariables.add(rvars[i]); 226 } 227 if (rvars.length + pvars.length == vars.length) { 228 //System.out.println("pvariables = " + pvariables); 229 return getPermutation(vars, rvars); 230 } 231 logger.info("not implemented for " + variables + " != " + pvariables + " cup " + rvariables); 232 throw new UnsupportedOperationException("not implemented"); 233 /* 234 if (!variables.containsAll(pvariables) || !variables.containsAll(rvariables)) { 235 throw new IllegalArgumentException("partial variables not contained in all variables "); 236 } 237 Collections.reverse(variables); 238 Collections.reverse(pvariables); 239 Collections.reverse(rvariables); 240 System.out.println("variables = " + variables); 241 System.out.println("pvariables = " + pvariables); 242 System.out.println("rvariables = " + rvariables); 243 244 List<Integer> perm = new ArrayList<Integer>(); 245 List<Integer> pv = new ArrayList<Integer>(); 246 for (String s : variables) { 247 int j = pvariables.indexOf(s); 248 if (j >= 0) { 249 perm.add(j); 250 } 251 } 252 int i = pvariables.size(); 253 for (String s : variables) { 254 if (!pvariables.contains(s)) { 255 pv.add(i); 256 } 257 i++; 258 } 259 260 System.out.println("perm, 1 = " + perm); 261 //System.out.println("pv = " + pv); 262 // sort perm according to pvars 263 int ps = perm.size(); // == pvars.length 264 for (int k = 0; k < ps; k++) { 265 for (int j = k + 1; j < ps; j++) { 266 int kk = variables.indexOf(pvariables.get(k)); 267 int jj = variables.indexOf(pvariables.get(j)); 268 if (kk > jj) { // swap 269 int t = perm.get(k); 270 System.out.println("swap " + t + " with " + perm.get(j)); 271 perm.set(k, perm.get(j)); 272 perm.set(j, t); 273 } 274 } 275 } 276 //System.out.println("perm = " + perm); 277 // sort pv according to rvars 278 int rs = pv.size(); // == rvars.length 279 for (int k = 0; k < rs; k++) { 280 for (int j = k + 1; j < rs; j++) { 281 int kk = variables.indexOf(rvariables.get(k)); 282 int jj = variables.indexOf(rvariables.get(j)); 283 if (kk > jj) { // swap 284 int t = pv.get(k); 285 //System.out.println("swap " + t + " with " + perm.get(j)); 286 pv.set(k, pv.get(j)); 287 pv.set(j, t); 288 } 289 } 290 } 291 //System.out.println("pv = " + pv); 292 perm.addAll(pv); 293 System.out.println("perm, 2 = " + perm); 294 return perm; 295 */ 296 } 297 298 299 /** 300 * Partial permuation for specific variables. Computes a permutation perm 301 * for the variables vars, such that perm(vars) == (evars, pvars, (vars \ { 302 * evars, pvars }). Uses internal (reversed) variable sorting. 303 * @param vars names for all variables. 304 * @param evars names for elimination variables, evars subseteq vars. 305 * @param pvars names for main variables, pvars subseteq vars. 306 * @param rvars names for remaining variables, rvars eq {vars \ { evars, 307 * pvars } }. 308 * @return permutation for vars, such that perm(vars) == (evars,pvars, {vars 309 * \ {evars,pvars}}. 310 */ 311 public static List<Integer> partialPermutation(String[] vars, String[] evars, String[] pvars, 312 String[] rvars) { 313 if (vars == null || evars == null || pvars == null) { 314 throw new IllegalArgumentException("not all variable names given"); 315 } 316 String[] uvars; 317 if (rvars != null) { 318 uvars = new String[pvars.length + rvars.length]; 319 for (int i = 0; i < pvars.length; i++) { 320 uvars[i] = pvars[i]; 321 } 322 for (int i = 0; i < rvars.length; i++) { 323 uvars[pvars.length + i] = rvars[i]; 324 } 325 } else { 326 uvars = pvars; 327 } 328 //System.out.println("uvars = " + Arrays.toString(uvars)); 329 List<Integer> perm = partialPermutation(vars, evars, uvars); 330 return perm; 331 } 332 333 334 /** 335 * Remaining variables vars \ pvars. Uses internal (reversed) variable 336 * sorting, original order is preserved. 337 * @param vars names for all variables. 338 * @param pvars names for main variables, pvars subseteq vars. 339 * @return remaining vars = (vars \ pvars). 340 */ 341 public static String[] remainingVars(String[] vars, String[] pvars) { 342 if (vars == null || pvars == null) { 343 throw new IllegalArgumentException("no variable names found"); 344 } 345 List<String> variables = new ArrayList<String>(vars.length); 346 List<String> pvariables = new ArrayList<String>(pvars.length); 347 for (int i = 0; i < vars.length; i++) { 348 variables.add(vars[i]); 349 } 350 for (int i = 0; i < pvars.length; i++) { 351 pvariables.add(pvars[i]); 352 } 353 if (!variables.containsAll(pvariables)) { 354 throw new IllegalArgumentException("partial variables not contained in all variables "); 355 } 356 // variables.setMinus(pvariables) 357 List<String> rvariables = new ArrayList<String>(variables); 358 for (String s : pvariables) { 359 rvariables.remove(s); 360 } 361 int cl = vars.length - pvars.length; 362 String[] rvars = new String[cl]; 363 int i = 0; 364 for (String s : rvariables) { 365 rvars[i++] = s; 366 } 367 return rvars; 368 } 369 370 371 /** 372 * Partial recursive Groebner base for specific variables. Computes Groebner 373 * base in K[vars \ pvars][pvars] with coefficients from K[vars \ pvars]. 374 * @param F polynomial list. 375 * @param pvars names for main variables of partial Groebner base 376 * computation. 377 * @return a container for a partial Groebner base of F wrt pvars. 378 */ 379 public OptimizedPolynomialList<GenPolynomial<C>> partialGBrec(List<GenPolynomial<C>> F, String[] pvars) { 380 if (F == null || F.isEmpty()) { 381 throw new IllegalArgumentException("empty F not allowed"); 382 } 383 GenPolynomialRing<C> fac = F.get(0).ring; 384 String[] vars = fac.getVars(); 385 if (vars == null || pvars == null) { 386 throw new IllegalArgumentException("not all variable names found"); 387 } 388 if (vars.length == pvars.length) { 389 throw new IllegalArgumentException("use non recursive partialGB algorithm"); 390 } 391 // compute permutation (in reverse sorting) 392 List<Integer> perm = partialPermutation(vars, pvars); 393 394 GenPolynomialRing<C> pfac = TermOrderOptimization.<C> permutation(perm, fac); 395 if (logger.isInfoEnabled()) { 396 logger.info("pfac = " + pfac); 397 } 398 List<GenPolynomial<C>> ppolys = TermOrderOptimization.<C> permutation(perm, pfac, F); 399 //System.out.println("ppolys = " + ppolys); 400 401 int cl = fac.nvar - pvars.length; // > 0 402 int pl = pvars.length; 403 String[] rvars = remainingVars(vars, pvars); 404 GenPolynomialRing<C> cfac = new GenPolynomialRing<C>(fac.coFac, cl, fac.tord, rvars); 405 //System.out.println("cfac = " + cfac); 406 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pl, 407 fac.tord, pvars); 408 if (logger.isInfoEnabled()) { 409 logger.info("rfac = " + rfac); 410 } 411 //System.out.println("rfac = " + rfac); 412 413 List<GenPolynomial<GenPolynomial<C>>> Fr = PolyUtil.<C> recursive(rfac, ppolys); 414 //System.out.println("\nFr = " + Fr); 415 416 if (true) { 417 rbb = new GroebnerBasePseudoRecSeq<C>(cfac); 418 } 419 List<GenPolynomial<GenPolynomial<C>>> Gr = rbb.GB(Fr); 420 //System.out.println("\nGr = " + Gr); 421 //perm = perm.subList(0,pl); 422 OptimizedPolynomialList<GenPolynomial<C>> pgb = new OptimizedPolynomialList<GenPolynomial<C>>(perm, 423 rfac, Gr); 424 return pgb; 425 } 426 427 428 /** 429 * Partial Groebner base for specific variables. Computes Groebner base in 430 * K[vars \ pvars][pvars] with coefficients from K[vars \ pvars] but returns 431 * polynomials in K[vars \ pvars, pvars]. 432 * @param F polynomial list. 433 * @param pvars names for main variables of partial Groebner base 434 * computation. 435 * @return a container for a partial Groebner base of F wrt pvars. 436 */ 437 public OptimizedPolynomialList<C> partialGB(List<GenPolynomial<C>> F, String[] pvars) { 438 if (F == null || F.isEmpty()) { 439 throw new IllegalArgumentException("empty F not allowed"); 440 } 441 GenPolynomialRing<C> fac = F.get(0).ring; 442 String[] vars = fac.getVars(); 443 // compute permutation (in reverse sorting) 444 //String[] xvars = remainingVars(vars, pvars); 445 //System.out.println("xvars = " + Arrays.toString(xvars)); 446 447 List<Integer> perm = partialPermutation(vars, pvars); 448 //System.out.println("pGB, perm = " + perm); 449 //System.out.println("pGB, perm,1 = " + getPermutation(vars, xvars)); 450 451 GenPolynomialRing<C> pfac = TermOrderOptimization.<C> permutation(perm, fac); 452 if (logger.isInfoEnabled()) { 453 logger.info("pfac = " + pfac); 454 } 455 List<GenPolynomial<C>> ppolys = TermOrderOptimization.<C> permutation(perm, pfac, F); 456 //System.out.println("ppolys = " + ppolys); 457 458 int cl = fac.nvar - pvars.length; 459 if (cl == 0) { // non recursive case 460 //GroebnerBaseSeq<C> bb = new GroebnerBaseSeq<C>(); 461 List<GenPolynomial<C>> G = bb.GB(ppolys); 462 OptimizedPolynomialList<C> pgb = new OptimizedPolynomialList<C>(perm, pfac, G); 463 return pgb; 464 } 465 // recursive case 466 int pl = pvars.length; 467 String[] rvars = remainingVars(vars, pvars); 468 GenPolynomialRing<C> cfac = new GenPolynomialRing<C>(fac.coFac, cl, fac.tord, rvars); 469 //System.out.println("cfac = " + cfac); 470 471 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pl, 472 fac.tord, pvars); 473 if (logger.isInfoEnabled()) { 474 logger.info("rfac = " + rfac); 475 } 476 //System.out.println("rfac = " + rfac); 477 478 List<GenPolynomial<GenPolynomial<C>>> Fr = PolyUtil.<C> recursive(rfac, ppolys); 479 //System.out.println("\nFr = " + Fr); 480 481 if (true) { 482 rbb = new GroebnerBasePseudoRecSeq<C>(cfac); 483 } 484 List<GenPolynomial<GenPolynomial<C>>> Gr = rbb.GB(Fr); 485 //System.out.println("\nGr = " + Gr); 486 487 List<GenPolynomial<C>> G = PolyUtil.<C> distribute(pfac, Gr); 488 //System.out.println("\nG = " + G); 489 490 OptimizedPolynomialList<C> pgb = new OptimizedPolynomialList<C>(perm, pfac, G); 491 return pgb; 492 } 493 494 495 /** 496 * Partial Groebner base for specific variables. Computes Groebner base with 497 * coefficients from K[pvars] but returns polynomials in K[pvars, evars]. 498 * @param F polynomial list. 499 * @param evars names for upper main variables of partial Groebner base 500 * computation. 501 * @param pvars names for lower main variables of partial Groebner base 502 * computation. 503 * @return a container for a partial Groebner base of F wrt (pvars,evars). 504 */ 505 public OptimizedPolynomialList<C> elimPartialGB(List<GenPolynomial<C>> F, String[] evars, String[] pvars) { 506 if (F == null || F.isEmpty()) { 507 throw new IllegalArgumentException("empty F not allowed"); 508 } 509 GenPolynomialRing<C> fac = F.get(0).ring; 510 String[] vars = fac.getVars(); 511 // compute permutation (in reverse sorting) 512 //System.out.println("vars = " + Arrays.toString(vars)); 513 //System.out.println("evars = " + Arrays.toString(evars)); 514 //System.out.println("pvars = " + Arrays.toString(pvars)); 515 List<Integer> perm = partialPermutation(vars, evars, pvars); 516 //System.out.println("perm = " + perm); 517 518 GenPolynomialRing<C> pfac = TermOrderOptimization.<C> permutation(perm, fac); 519 if (logger.isInfoEnabled()) { 520 logger.info("pfac = " + pfac); 521 } 522 List<GenPolynomial<C>> ppolys = TermOrderOptimization.<C> permutation(perm, pfac, F); 523 //System.out.println("ppolys = " + ppolys); 524 525 int cl = fac.nvar - evars.length - pvars.length; 526 if (cl == 0) { // non recursive case 527 TermOrder to = pfac.tord; 528 int ev = to.getEvord(); 529 //ev = TermOrder.IGRLEX; 530 TermOrder split = new TermOrder(ev, ev, pfac.nvar, evars.length); 531 pfac = new GenPolynomialRing<C>(pfac.coFac, pfac.nvar, split, pfac.getVars()); 532 if (logger.isInfoEnabled()) { 533 //logger.info("split = " + split); 534 logger.info("pfac = " + pfac); 535 } 536 List<GenPolynomial<C>> Fs = new ArrayList<GenPolynomial<C>>(ppolys.size()); 537 for (GenPolynomial<C> p : ppolys) { 538 Fs.add(pfac.copy(p)); 539 } 540 List<GenPolynomial<C>> G = bb.GB(Fs); 541 OptimizedPolynomialList<C> pgb = new OptimizedPolynomialList<C>(perm, pfac, G); 542 if (logger.isInfoEnabled()) { 543 logger.info("pgb = " + pgb); 544 } 545 return pgb; 546 } 547 logger.warn("not meaningful for elimination " + cl); 548 // recursive case 549 int pl = pvars.length + pvars.length; 550 String[] rvars = remainingVars(vars, evars); 551 rvars = remainingVars(rvars, pvars); 552 String[] uvars = new String[evars.length + pvars.length]; 553 for (int i = 0; i < pvars.length; i++) { 554 uvars[i] = pvars[i]; 555 } 556 for (int i = 0; i < evars.length; i++) { 557 uvars[pvars.length + i] = evars[i]; 558 } 559 560 GenPolynomialRing<C> cfac = new GenPolynomialRing<C>(fac.coFac, cl, fac.tord, rvars); 561 //System.out.println("cfac = " + cfac); 562 563 TermOrder to = pfac.tord; 564 int ev = to.getEvord(); 565 TermOrder split = new TermOrder(ev, ev, pl, evars.length); 566 //GenPolynomialRing<C> sfac = new GenPolynomialRing<C>(pfac.coFac, pfac.nvar, split, pfac.getVars()); 567 568 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pl, split, 569 uvars); 570 //System.out.println("rfac = " + rfac); 571 572 List<GenPolynomial<GenPolynomial<C>>> Fr = PolyUtil.<C> recursive(rfac, ppolys); 573 if (logger.isInfoEnabled()) { 574 logger.info("rfac = " + rfac); 575 logger.info("Fr = " + Fr); 576 } 577 578 if (true) { 579 rbb = new GroebnerBasePseudoRecSeq<C>(cfac); 580 } 581 List<GenPolynomial<GenPolynomial<C>>> Gr = rbb.GB(Fr); 582 //System.out.println("\nGr = " + Gr); 583 584 List<GenPolynomial<C>> G = PolyUtil.<C> distribute(pfac, Gr); 585 //System.out.println("\nG = " + G); 586 587 OptimizedPolynomialList<C> pgb = new OptimizedPolynomialList<C>(perm, pfac, G); 588 return pgb; 589 } 590 591}