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}