Source code

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