001 /*
002 * $Id: GroebnerBasePartial.java 3423 2010-12-24 10:56:50Z kredel $
003 */
004
005 package edu.jas.gbufd;
006
007
008 import java.util.ArrayList;
009 import java.util.Collections;
010 import java.util.List;
011
012 import org.apache.log4j.Logger;
013
014 import edu.jas.gb.GroebnerBaseAbstract;
015 import edu.jas.gb.GroebnerBaseSeq;
016 import edu.jas.poly.GenPolynomial;
017 import edu.jas.poly.GenPolynomialRing;
018 import edu.jas.poly.OptimizedPolynomialList;
019 import edu.jas.poly.PolyUtil;
020 import edu.jas.poly.TermOrder;
021 import edu.jas.poly.TermOrderOptimization;
022 import edu.jas.structure.GcdRingElem;
023 import 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
035 public 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 } else if (true) {
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 * Partial permuation for specific variables. Computes a permutation perm
300 * for the variables vars, such that perm(vars) == (evars, pvars, (vars \ {
301 * evars, pvars }). Uses internal (reversed) variable sorting.
302 * @param vars names for all variables.
303 * @param evars names for elimination variables, evars subseteq vars.
304 * @param pvars names for main variables, pvars subseteq vars.
305 * @param rvars names for remaining variables, rvars eq {vars \ { evars,
306 * pvars } }.
307 * @return permutation for vars, such that perm(vars) == (evars,pvars, {vars
308 * \ {evars,pvars}}.
309 */
310 public static List<Integer> partialPermutation(String[] vars, String[] evars, String[] pvars,
311 String[] rvars) {
312 if (vars == null || evars == null || pvars == null) {
313 throw new IllegalArgumentException("not all variable names given");
314 }
315 String[] uvars;
316 if (rvars != null) {
317 uvars = new String[pvars.length + rvars.length];
318 for (int i = 0; i < pvars.length; i++) {
319 uvars[i] = pvars[i];
320 }
321 for (int i = 0; i < rvars.length; i++) {
322 uvars[pvars.length + i] = rvars[i];
323 }
324 } else {
325 uvars = pvars;
326 }
327 //System.out.println("uvars = " + Arrays.toString(uvars));
328 List<Integer> perm = partialPermutation(vars, evars, uvars);
329 return perm;
330 }
331
332
333 /**
334 * Remaining variables vars \ pvars. Uses internal (reversed) variable
335 * sorting, original order is preserved.
336 * @param vars names for all variables.
337 * @param pvars names for main variables, pvars subseteq vars.
338 * @return remaining vars = (vars \ pvars).
339 */
340 public static String[] remainingVars(String[] vars, String[] pvars) {
341 if (vars == null || pvars == null) {
342 throw new IllegalArgumentException("no variable names found");
343 }
344 List<String> variables = new ArrayList<String>(vars.length);
345 List<String> pvariables = new ArrayList<String>(pvars.length);
346 for (int i = 0; i < vars.length; i++) {
347 variables.add(vars[i]);
348 }
349 for (int i = 0; i < pvars.length; i++) {
350 pvariables.add(pvars[i]);
351 }
352 if (!variables.containsAll(pvariables)) {
353 throw new IllegalArgumentException("partial variables not contained in all variables ");
354 }
355 // variables.setMinus(pvariables)
356 List<String> rvariables = new ArrayList<String>(variables);
357 for (String s : pvariables) {
358 rvariables.remove(s);
359 }
360 int cl = vars.length - pvars.length;
361 String[] rvars = new String[cl];
362 int i = 0;
363 for (String s : rvariables) {
364 rvars[i++] = s;
365 }
366 return rvars;
367 }
368
369
370 /**
371 * Partial recursive Groebner base for specific variables. Computes Groebner
372 * base in K[vars \ pvars][pvars] with coefficients from K[vars \ pvars].
373 * @param F polynomial list.
374 * @param pvars names for main variables of partial Groebner base
375 * computation.
376 * @return a container for a partial Groebner base of F wrt pvars.
377 */
378 public OptimizedPolynomialList<GenPolynomial<C>> partialGBrec(List<GenPolynomial<C>> F, String[] pvars) {
379 if (F == null || F.isEmpty()) {
380 throw new IllegalArgumentException("empty F not allowed");
381 }
382 GenPolynomialRing<C> fac = F.get(0).ring;
383 String[] vars = fac.getVars();
384 if (vars == null || pvars == null) {
385 throw new IllegalArgumentException("not all variable names found");
386 }
387 if (vars.length == pvars.length) {
388 throw new IllegalArgumentException("use non recursive partialGB algorithm");
389 }
390 // compute permutation (in reverse sorting)
391 List<Integer> perm = partialPermutation(vars, pvars);
392
393 GenPolynomialRing<C> pfac = TermOrderOptimization.<C> permutation(perm, fac);
394 if (logger.isInfoEnabled()) {
395 logger.info("pfac = " + pfac);
396 }
397 List<GenPolynomial<C>> ppolys = TermOrderOptimization.<C> permutation(perm, pfac, F);
398 //System.out.println("ppolys = " + ppolys);
399
400 int cl = fac.nvar - pvars.length; // > 0
401 int pl = pvars.length;
402 String[] rvars = remainingVars(vars, pvars);
403 GenPolynomialRing<C> cfac = new GenPolynomialRing<C>(fac.coFac, cl, fac.tord, rvars);
404 //System.out.println("cfac = " + cfac);
405 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pl,
406 fac.tord, pvars);
407 if (logger.isInfoEnabled()) {
408 logger.info("rfac = " + rfac);
409 }
410 //System.out.println("rfac = " + rfac);
411
412 List<GenPolynomial<GenPolynomial<C>>> Fr = PolyUtil.<C> recursive(rfac, ppolys);
413 //System.out.println("\nFr = " + Fr);
414
415 if (true) {
416 rbb = new GroebnerBasePseudoRecSeq<C>(cfac);
417 }
418 List<GenPolynomial<GenPolynomial<C>>> Gr = rbb.GB(Fr);
419 //System.out.println("\nGr = " + Gr);
420 //perm = perm.subList(0,pl);
421 OptimizedPolynomialList<GenPolynomial<C>> pgb = new OptimizedPolynomialList<GenPolynomial<C>>(perm,
422 rfac, Gr);
423 return pgb;
424 }
425
426
427 /**
428 * Partial Groebner base for specific variables. Computes Groebner base in
429 * K[vars \ pvars][pvars] with coefficients from K[vars \ pvars] but returns
430 * polynomials in K[vars \ pvars, pvars].
431 * @param F polynomial list.
432 * @param pvars names for main variables of partial Groebner base
433 * computation.
434 * @return a container for a partial Groebner base of F wrt pvars.
435 */
436 public OptimizedPolynomialList<C> partialGB(List<GenPolynomial<C>> F, String[] pvars) {
437 if (F == null || F.isEmpty()) {
438 throw new IllegalArgumentException("empty F not allowed");
439 }
440 GenPolynomialRing<C> fac = F.get(0).ring;
441 String[] vars = fac.getVars();
442 // compute permutation (in reverse sorting)
443 String[] xvars = remainingVars(vars, pvars);
444 //System.out.println("xvars = " + Arrays.toString(xvars));
445
446 List<Integer> perm = partialPermutation(vars, pvars);
447 //System.out.println("pGB, perm = " + perm);
448 //System.out.println("pGB, perm,1 = " + getPermutation(vars, xvars));
449
450 GenPolynomialRing<C> pfac = TermOrderOptimization.<C> permutation(perm, fac);
451 if (logger.isInfoEnabled()) {
452 logger.info("pfac = " + pfac);
453 }
454 List<GenPolynomial<C>> ppolys = TermOrderOptimization.<C> permutation(perm, pfac, F);
455 //System.out.println("ppolys = " + ppolys);
456
457 int cl = fac.nvar - pvars.length;
458 if (cl == 0) { // non recursive case
459 //GroebnerBaseSeq<C> bb = new GroebnerBaseSeq<C>();
460 List<GenPolynomial<C>> G = bb.GB(ppolys);
461 OptimizedPolynomialList<C> pgb = new OptimizedPolynomialList<C>(perm, pfac, G);
462 return pgb;
463 }
464 // recursive case
465 int pl = pvars.length;
466 String[] rvars = remainingVars(vars, pvars);
467 GenPolynomialRing<C> cfac = new GenPolynomialRing<C>(fac.coFac, cl, fac.tord, rvars);
468 //System.out.println("cfac = " + cfac);
469
470 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pl,
471 fac.tord, pvars);
472 if (logger.isInfoEnabled()) {
473 logger.info("rfac = " + rfac);
474 }
475 //System.out.println("rfac = " + rfac);
476
477 List<GenPolynomial<GenPolynomial<C>>> Fr = PolyUtil.<C> recursive(rfac, ppolys);
478 //System.out.println("\nFr = " + Fr);
479
480 if (true) {
481 rbb = new GroebnerBasePseudoRecSeq<C>(cfac);
482 }
483 List<GenPolynomial<GenPolynomial<C>>> Gr = rbb.GB(Fr);
484 //System.out.println("\nGr = " + Gr);
485
486 List<GenPolynomial<C>> G = PolyUtil.<C> distribute(pfac, Gr);
487 //System.out.println("\nG = " + G);
488
489 OptimizedPolynomialList<C> pgb = new OptimizedPolynomialList<C>(perm, pfac, G);
490 return pgb;
491 }
492
493
494 /**
495 * Partial Groebner base for specific variables. Computes Groebner base with
496 * coefficients from K[pvars] but returns polynomials in K[pvars, evars].
497 * @param F polynomial list.
498 * @param evars names for upper main variables of partial Groebner base
499 * computation.
500 * @param pvars names for lower main variables of partial Groebner base
501 * computation.
502 * @return a container for a partial Groebner base of F wrt (pvars,evars).
503 */
504 public OptimizedPolynomialList<C> elimPartialGB(List<GenPolynomial<C>> F, String[] evars, String[] pvars) {
505 if (F == null || F.isEmpty()) {
506 throw new IllegalArgumentException("empty F not allowed");
507 }
508 GenPolynomialRing<C> fac = F.get(0).ring;
509 String[] vars = fac.getVars();
510 // compute permutation (in reverse sorting)
511 //System.out.println("vars = " + Arrays.toString(vars));
512 //System.out.println("evars = " + Arrays.toString(evars));
513 //System.out.println("pvars = " + Arrays.toString(pvars));
514 List<Integer> perm = partialPermutation(vars, evars, pvars);
515 //System.out.println("perm = " + perm);
516
517 GenPolynomialRing<C> pfac = TermOrderOptimization.<C> permutation(perm, fac);
518 if (logger.isInfoEnabled()) {
519 logger.info("pfac = " + pfac);
520 }
521 List<GenPolynomial<C>> ppolys = TermOrderOptimization.<C> permutation(perm, pfac, F);
522 //System.out.println("ppolys = " + ppolys);
523
524 int cl = fac.nvar - evars.length - pvars.length;
525 if (cl == 0) { // non recursive case
526 TermOrder to = pfac.tord;
527 int ev = to.getEvord();
528 //ev = TermOrder.IGRLEX;
529 TermOrder split = new TermOrder(ev, ev, pfac.nvar, evars.length);
530 pfac = new GenPolynomialRing<C>(pfac.coFac, pfac.nvar, split, pfac.getVars());
531 if (logger.isInfoEnabled()) {
532 //logger.info("split = " + split);
533 logger.info("pfac = " + pfac);
534 }
535 List<GenPolynomial<C>> Fs = new ArrayList<GenPolynomial<C>>(ppolys.size());
536 for (GenPolynomial<C> p : ppolys) {
537 Fs.add(pfac.copy(p));
538 }
539 List<GenPolynomial<C>> G = bb.GB(Fs);
540 OptimizedPolynomialList<C> pgb = new OptimizedPolynomialList<C>(perm, pfac, G);
541 if (logger.isInfoEnabled()) {
542 logger.info("pgb = " + pgb);
543 }
544 return pgb;
545 } else {
546 logger.info("not meaningful for elimination " + cl);
547 }
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
567 GenPolynomialRing<C> sfac = new GenPolynomialRing<C>(pfac.coFac, pfac.nvar, split, pfac.getVars());
568
569 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pl, split,
570 uvars);
571 //System.out.println("rfac = " + rfac);
572
573 List<GenPolynomial<GenPolynomial<C>>> Fr = PolyUtil.<C> recursive(rfac, ppolys);
574 if (logger.isInfoEnabled()) {
575 logger.info("rfac = " + rfac);
576 logger.info("Fr = " + Fr);
577 }
578
579 if (true) {
580 rbb = new GroebnerBasePseudoRecSeq<C>(cfac);
581 }
582 List<GenPolynomial<GenPolynomial<C>>> Gr = rbb.GB(Fr);
583 //System.out.println("\nGr = " + Gr);
584
585 List<GenPolynomial<C>> G = PolyUtil.<C> distribute(pfac, Gr);
586 //System.out.println("\nG = " + G);
587
588 OptimizedPolynomialList<C> pgb = new OptimizedPolynomialList<C>(perm, pfac, G);
589 return pgb;
590 }
591
592 }