Source code

001/*
002 * $Id: TermOrderOptimization.java 5226 2015-04-19 10:16:29Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import java.util.ArrayList;
009import java.util.Collection;
010import java.util.List;
011import java.util.Map;
012import java.util.SortedMap;
013import java.util.TreeMap;
014
015import org.apache.log4j.Logger;
016
017import edu.jas.arith.BigInteger;
018import edu.jas.structure.RingElem;
019import edu.jas.vector.BasicLinAlg;
020
021
022/**
023 * Term order optimization. See mas10/maspoly/DIPTOO.m{di}.
024 * @author Heinz Kredel
025 */
026
027public class TermOrderOptimization {
028
029
030    private static final Logger logger = Logger.getLogger(TermOrderOptimization.class);
031
032
033    //private static boolean debug = logger.isDebugEnabled();
034
035
036    /**
037     * Degree matrix.
038     * @param A polynomial to be considered.
039     * @return degree matrix.
040     */
041    public static <C extends RingElem<C>> List<GenPolynomial<BigInteger>> degreeMatrix(GenPolynomial<C> A) {
042
043        List<GenPolynomial<BigInteger>> dem = null;
044        if (A == null) {
045            return dem;
046        }
047
048        BigInteger cfac = new BigInteger();
049        GenPolynomialRing<BigInteger> ufac = new GenPolynomialRing<BigInteger>(cfac, 1);
050
051        int nvar = A.numberOfVariables();
052        dem = new ArrayList<GenPolynomial<BigInteger>>(nvar);
053
054        for (int i = 0; i < nvar; i++) {
055            dem.add(ufac.getZERO());
056        }
057        if (A.isZERO()) {
058            return dem;
059        }
060
061        for (ExpVector e : A.getMap().keySet()) {
062            dem = expVectorAdd(dem, e);
063        }
064        return dem;
065    }
066
067
068    /**
069     * Degree matrix exponent vector add.
070     * @param dm degree matrix.
071     * @param e exponent vector.
072     * @return degree matrix + e.
073     */
074    public static List<GenPolynomial<BigInteger>> expVectorAdd(List<GenPolynomial<BigInteger>> dm, ExpVector e) {
075        for (int i = 0; i < dm.size() && i < e.length(); i++) {
076            GenPolynomial<BigInteger> p = dm.get(i);
077            long u = e.getVal(i);
078            ExpVector f = ExpVector.create(1, 0, u);
079            p = p.sum(p.ring.getONECoefficient(), f);
080            dm.set(i, p);
081        }
082        return dm;
083    }
084
085
086    /**
087     * Degree matrix of coefficient polynomials.
088     * @param A polynomial to be considered.
089     * @return degree matrix for the coeficients.
090     */
091    public static <C extends RingElem<C>> List<GenPolynomial<BigInteger>> degreeMatrixOfCoefficients(
092                    GenPolynomial<GenPolynomial<C>> A) {
093        if (A == null) {
094            throw new IllegalArgumentException("polynomial must not be null");
095        }
096        return degreeMatrix(A.getMap().values());
097    }
098
099
100    /**
101     * Degree matrix.
102     * @param L list of polynomial to be considered.
103     * @return degree matrix.
104     */
105    public static <C extends RingElem<C>> List<GenPolynomial<BigInteger>> degreeMatrix(
106                    Collection<GenPolynomial<C>> L) {
107        if (L == null) {
108            throw new IllegalArgumentException("list must be non null");
109        }
110        BasicLinAlg<GenPolynomial<BigInteger>> blas = new BasicLinAlg<GenPolynomial<BigInteger>>();
111        List<GenPolynomial<BigInteger>> dem = null;
112        for (GenPolynomial<C> p : L) {
113            List<GenPolynomial<BigInteger>> dm = degreeMatrix(p);
114            if (dem == null) {
115                dem = dm;
116            } else {
117                dem = blas.vectorAdd(dem, dm);
118            }
119        }
120        return dem;
121    }
122
123
124    /**
125     * Degree matrix of coefficient polynomials.
126     * @param L list of polynomial to be considered.
127     * @return degree matrix for the coeficients.
128     */
129    public static <C extends RingElem<C>> List<GenPolynomial<BigInteger>> degreeMatrixOfCoefficients(
130                    Collection<GenPolynomial<GenPolynomial<C>>> L) {
131        if (L == null) {
132            throw new IllegalArgumentException("list must not be null");
133        }
134        BasicLinAlg<GenPolynomial<BigInteger>> blas = new BasicLinAlg<GenPolynomial<BigInteger>>();
135        List<GenPolynomial<BigInteger>> dem = null;
136        for (GenPolynomial<GenPolynomial<C>> p : L) {
137            List<GenPolynomial<BigInteger>> dm = degreeMatrixOfCoefficients(p);
138            if (dem == null) {
139                dem = dm;
140            } else {
141                dem = blas.vectorAdd(dem, dm);
142            }
143        }
144        return dem;
145    }
146
147
148    /**
149     * Optimal permutation for the Degree matrix.
150     * @param D degree matrix.
151     * @return optimal permutation for D.
152     */
153    public static List<Integer> optimalPermutation(List<GenPolynomial<BigInteger>> D) {
154        if (D == null) {
155            throw new IllegalArgumentException("list must be non null");
156        }
157        List<Integer> P = new ArrayList<Integer>(D.size());
158        if (D.size() == 0) {
159            return P;
160        }
161        if (D.size() == 1) {
162            P.add(0);
163            return P;
164        }
165        SortedMap<GenPolynomial<BigInteger>, List<Integer>> map = new TreeMap<GenPolynomial<BigInteger>, List<Integer>>();
166        int i = 0;
167        for (GenPolynomial<BigInteger> p : D) {
168            List<Integer> il = map.get(p);
169            if (il == null) {
170                il = new ArrayList<Integer>(3);
171            }
172            il.add(i);
173            map.put(p, il);
174            i++;
175        }
176        List<List<Integer>> V = new ArrayList<List<Integer>>(map.values());
177        //System.out.println("V = " + V);
178        if (logger.isDebugEnabled()) {
179            logger.info("V = " + V);
180        }
181        //for ( int j = V.size()-1; j >= 0; j-- ) {
182        for (int j = 0; j < V.size(); j++) {
183            List<Integer> v = V.get(j);
184            for (Integer k : v) {
185                P.add(k);
186            }
187        }
188        return P;
189    }
190
191
192    /**
193     * Inverse of a permutation.
194     * @param P permutation.
195     * @return S with S*P = id.
196     */
197    public static List<Integer> inversePermutation(List<Integer> P) {
198        if (P == null || P.size() <= 1) {
199            return P;
200        }
201        List<Integer> ip = new ArrayList<Integer>(P); // ensure size and content
202        for (int i = 0; i < P.size(); i++) {
203            ip.set(P.get(i), i); // inverse
204        }
205        return ip;
206    }
207
208
209    /**
210     * Test for identity permutation.
211     * @param P permutation.
212     * @return true , if P = id, else false.
213     */
214    public static boolean isIdentityPermutation(List<Integer> P) {
215        if (P == null || P.size() <= 1) {
216            return true;
217        }
218        for (int i = 0; i < P.size(); i++) {
219            if (P.get(i).intValue() != i) {
220                return false;
221            }
222        }
223        return true;
224    }
225
226
227    /**
228     * Multiplication permutations.
229     * @param P permutation.
230     * @param S permutation.
231     * @return P*S.
232     */
233    public static List<Integer> multiplyPermutation(List<Integer> P, List<Integer> S) {
234        if (P == null || S == null) {
235            return null;
236        }
237        if (P.size() != S.size()) {
238            throw new IllegalArgumentException("#P != #S: P =" + P + ", S = " + S);
239        }
240        List<Integer> ip = new ArrayList<Integer>(P); // ensure size and content
241        for (int i = 0; i < P.size(); i++) {
242            ip.set(i, S.get(P.get(i)));
243        }
244        return ip;
245    }
246
247
248    /**
249     * Permutation of a list.
250     * @param L list.
251     * @param P permutation.
252     * @return P(L).
253     */
254    @SuppressWarnings("cast")
255    public static <T> List<T> listPermutation(List<Integer> P, List<T> L) {
256        if (L == null || L.size() <= 1) {
257            return L;
258        }
259        List<T> pl = new ArrayList<T>(L.size());
260        for (Integer i : P) {
261            pl.add(L.get((int) i));
262        }
263        return pl;
264    }
265
266
267    /*
268     * Permutation of an array. Compiles, but does not work, requires JDK 1.6 to
269     * work.
270     * @param a array.
271     * @param P permutation.
272     * @return P(a).
273    @SuppressWarnings({ "unchecked", "cast" })
274    public static <T> T[] arrayPermutation(List<Integer> P, T[] a) {
275        if (a == null || a.length <= 1) {
276            return a;
277        }
278        T[] b = (T[]) new Object[a.length]; // jdk 1.5 
279        //T[] b = Arrays.<T>copyOf( a, a.length ); // jdk 1.6, works
280        int j = 0;
281        for (Integer i : P) {
282            b[j] = a[(int) i];
283            j++;
284        }
285        return b;
286    }
287     */
288
289
290    /**
291     * Permutation of polynomial exponent vectors.
292     * @param A polynomial.
293     * @param R polynomial ring.
294     * @param P permutation.
295     * @return P(A).
296     */
297    public static <C extends RingElem<C>> GenPolynomial<C> permutation(List<Integer> P,
298                    GenPolynomialRing<C> R, GenPolynomial<C> A) {
299        if (A == null) {
300            return A;
301        }
302        GenPolynomial<C> B = R.getZERO().copy();
303        Map<ExpVector, C> Bv = B.val; //getMap();
304        for (Map.Entry<ExpVector, C> y : A.getMap().entrySet()) {
305            ExpVector e = y.getKey();
306            C a = y.getValue();
307            //System.out.println("e = " + e);
308            ExpVector f = e.permutation(P);
309            //System.out.println("f = " + f);
310            Bv.put(f, a); // assert f not in Bv
311        }
312        return B;
313    }
314
315
316    /**
317     * Permutation of polynomial exponent vectors.
318     * @param L list of polynomials.
319     * @param R polynomial ring.
320     * @param P permutation.
321     * @return P(L).
322     */
323    public static <C extends RingElem<C>> List<GenPolynomial<C>> permutation(List<Integer> P,
324                    GenPolynomialRing<C> R, List<GenPolynomial<C>> L) {
325        if (L == null || L.size() == 0) {
326            return L;
327        }
328        List<GenPolynomial<C>> K = new ArrayList<GenPolynomial<C>>(L.size());
329        for (GenPolynomial<C> a : L) {
330            GenPolynomial<C> b = permutation(P, R, a);
331            K.add(b);
332        }
333        return K;
334    }
335
336
337    /**
338     * Permutation of polynomial exponent vectors of coefficient polynomials.
339     * @param A polynomial.
340     * @param R polynomial ring.
341     * @param P permutation.
342     * @return P(A).
343     */
344    public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> permutationOnCoefficients(
345                    List<Integer> P, GenPolynomialRing<GenPolynomial<C>> R, GenPolynomial<GenPolynomial<C>> A) {
346        if (A == null) {
347            return A;
348        }
349        GenPolynomial<GenPolynomial<C>> B = R.getZERO().copy();
350        GenPolynomialRing<C> cf = (GenPolynomialRing<C>) R.coFac;
351        Map<ExpVector, GenPolynomial<C>> Bv = B.val; //getMap();
352        for (Map.Entry<ExpVector, GenPolynomial<C>> y : A.getMap().entrySet()) {
353            ExpVector e = y.getKey();
354            GenPolynomial<C> a = y.getValue();
355            //System.out.println("e = " + e);
356            GenPolynomial<C> b = permutation(P, cf, a);
357            //System.out.println("b = " + b);
358            Bv.put(e, b); // assert e not in Bv
359        }
360        return B;
361    }
362
363
364    /**
365     * Permutation of polynomial exponent vectors of coefficients.
366     * @param L list of polynomials.
367     * @param R polynomial ring.
368     * @param P permutation.
369     * @return P(L).
370     */
371    public static <C extends RingElem<C>> List<GenPolynomial<GenPolynomial<C>>> permutationOnCoefficients(
372                    List<Integer> P, GenPolynomialRing<GenPolynomial<C>> R,
373                    List<GenPolynomial<GenPolynomial<C>>> L) {
374        if (L == null || L.size() == 0) {
375            return L;
376        }
377        List<GenPolynomial<GenPolynomial<C>>> K = new ArrayList<GenPolynomial<GenPolynomial<C>>>(L.size());
378        for (GenPolynomial<GenPolynomial<C>> a : L) {
379            GenPolynomial<GenPolynomial<C>> b = permutationOnCoefficients(P, R, a);
380            K.add(b);
381        }
382        return K;
383    }
384
385
386    /**
387     * Permutation of polynomial ring variables.
388     * @param R polynomial ring.
389     * @param P permutation.
390     * @return P(R).
391     */
392    public static <C extends RingElem<C>> GenPolynomialRing<C> permutation(List<Integer> P,
393                    GenPolynomialRing<C> R) {
394        return R.permutation(P);
395    }
396
397
398    /**
399     * Optimize variable order.
400     * @param R polynomial ring.
401     * @param L list of polynomials.
402     * @return optimized polynomial list.
403     */
404    public static <C extends RingElem<C>> OptimizedPolynomialList<C> optimizeTermOrder(
405                    GenPolynomialRing<C> R, List<GenPolynomial<C>> L) {
406        List<GenPolynomial<C>> Lp = new ArrayList<GenPolynomial<C>>(L);
407        if (R instanceof GenSolvablePolynomialRing) { // look also on solvable relations
408            GenSolvablePolynomialRing<C> Rs = (GenSolvablePolynomialRing<C>) R;
409            Lp.addAll(Rs.table.relationList());
410        }
411        List<Integer> perm = optimalPermutation(degreeMatrix(Lp));
412        GenPolynomialRing<C> pring = R.permutation(perm);
413        List<GenPolynomial<C>> ppolys = permutation(perm, pring, L);
414        OptimizedPolynomialList<C> op = new OptimizedPolynomialList<C>(perm, pring, ppolys);
415        return op;
416    }
417
418
419    /**
420     * Optimize variable order.
421     * @param P polynomial list.
422     * @return optimized polynomial list.
423     */
424    public static <C extends RingElem<C>> OptimizedPolynomialList<C> optimizeTermOrder(PolynomialList<C> P) {
425        if (P == null) {
426            return null;
427        }
428        return optimizeTermOrder(P.ring, P.list);
429    }
430
431
432    /**
433     * Optimize variable order on coefficients.
434     * @param P polynomial list.
435     * @return optimized polynomial list.
436     */
437    public static <C extends RingElem<C>> OptimizedPolynomialList<GenPolynomial<C>> optimizeTermOrderOnCoefficients(
438                    PolynomialList<GenPolynomial<C>> P) {
439        return optimizeTermOrderOnCoefficients(P.ring, P.list);
440    }
441
442
443    /**
444     * Optimize variable order on coefficients.
445     * @param ring polynomial ring.
446     * @param L list of polynomials.
447     * @return optimized polynomial list.
448     */
449    @SuppressWarnings("cast")
450    public static <C extends RingElem<C>> OptimizedPolynomialList<GenPolynomial<C>> optimizeTermOrderOnCoefficients(
451                    GenPolynomialRing<GenPolynomial<C>> ring, List<GenPolynomial<GenPolynomial<C>>> L) {
452        if (L == null) {
453            return null;
454        }
455        List<GenPolynomial<GenPolynomial<C>>> Lp = new ArrayList<GenPolynomial<GenPolynomial<C>>>(L);
456        //GenPolynomialRing<GenPolynomial<C>> ring = P.ring;
457        if (ring instanceof GenSolvablePolynomialRing) { // look also on solvable relations
458            GenSolvablePolynomialRing<GenPolynomial<C>> Rs = (GenSolvablePolynomialRing<GenPolynomial<C>>) ring;
459            Lp.addAll(Rs.table.relationList());
460        }
461        List<Integer> perm = optimalPermutation(degreeMatrixOfCoefficients(Lp));
462
463        GenPolynomialRing<C> coFac = (GenPolynomialRing<C>) ring.coFac;
464        GenPolynomialRing<C> pFac = coFac.permutation(perm);
465        GenSolvablePolynomialRing<GenPolynomial<C>> sring, psring;
466        GenPolynomialRing<GenPolynomial<C>> pring;
467        if (ring instanceof GenSolvablePolynomialRing) { // permute also solvable relations
468            sring = (GenSolvablePolynomialRing<GenPolynomial<C>>) ring;
469            psring = new GenSolvablePolynomialRing<GenPolynomial<C>>(pFac, sring);
470            List<GenPolynomial<GenPolynomial<C>>> ir = PolynomialList
471                            .<GenPolynomial<C>> castToList(sring.table.relationList());
472            ir = permutationOnCoefficients(perm, psring, ir);
473            psring.addRelations(ir);
474            pring = (GenPolynomialRing<GenPolynomial<C>>) psring;
475        } else {
476            pring = new GenPolynomialRing<GenPolynomial<C>>(pFac, ring);
477        }
478        List<GenPolynomial<GenPolynomial<C>>> ppolys;
479        ppolys = permutationOnCoefficients(perm, pring, L);
480
481        OptimizedPolynomialList<GenPolynomial<C>> op;
482        op = new OptimizedPolynomialList<GenPolynomial<C>>(perm, pring, ppolys);
483        return op;
484    }
485
486
487    /**
488     * Optimize variable order.
489     * @param P module list.
490     * @return optimized module list.
491     */
492    public static <C extends RingElem<C>> OptimizedModuleList<C> optimizeTermOrder(ModuleList<C> P) {
493        if (P == null) {
494            return null;
495        }
496        return optimizeTermOrderModule(P.ring, P.list);
497    }
498
499
500    /**
501     * Optimize variable order.
502     * @param R polynomial ring.
503     * @param L list of lists of polynomials.
504     * @return optimized module list.
505     */
506    public static <C extends RingElem<C>> OptimizedModuleList<C> optimizeTermOrderModule(
507                    GenPolynomialRing<C> R, List<List<GenPolynomial<C>>> L) {
508        List<GenPolynomial<C>> M = new ArrayList<GenPolynomial<C>>();
509        for (List<GenPolynomial<C>> ll : L) {
510            M.addAll(ll);
511        }
512        if (R instanceof GenSolvablePolynomialRing) { // look also on solvable relations
513            GenSolvablePolynomialRing<C> Rs = (GenSolvablePolynomialRing<C>) R;
514            M.addAll(Rs.table.relationList());
515        }
516        List<Integer> perm = optimalPermutation(degreeMatrix(M));
517        GenPolynomialRing<C> pring = R.permutation(perm);
518        List<List<GenPolynomial<C>>> mpolys = new ArrayList<List<GenPolynomial<C>>>();
519        List<GenPolynomial<C>> pp;
520        for (List<GenPolynomial<C>> ll : L) {
521            pp = permutation(perm, pring, ll);
522            mpolys.add(pp);
523        }
524        OptimizedModuleList<C> op = new OptimizedModuleList<C>(perm, pring, mpolys);
525        return op;
526    }
527
528
529    /**
530     * Optimize variable order on coefficients.
531     * @param P module list.
532     * @return optimized module list.
533     */
534    @SuppressWarnings("cast")
535    public static <C extends RingElem<C>> OptimizedModuleList<GenPolynomial<C>> optimizeTermOrderOnCoefficients(
536                    ModuleList<GenPolynomial<C>> P) {
537        if (P == null) {
538            return null;
539        }
540        GenPolynomialRing<GenPolynomial<C>> ring = P.ring;
541        List<GenPolynomial<GenPolynomial<C>>> M = new ArrayList<GenPolynomial<GenPolynomial<C>>>();
542        for (List<GenPolynomial<GenPolynomial<C>>> ll : P.list) {
543            M.addAll(ll);
544        }
545        if (ring instanceof GenSolvablePolynomialRing) { // look also on solvable relations
546            GenSolvablePolynomialRing<GenPolynomial<C>> Rs = (GenSolvablePolynomialRing<GenPolynomial<C>>) ring;
547            M.addAll(Rs.table.relationList());
548        }
549        List<Integer> perm = optimalPermutation(degreeMatrixOfCoefficients(M));
550
551        GenPolynomialRing<C> coFac = (GenPolynomialRing<C>) ring.coFac;
552        GenPolynomialRing<C> pFac = coFac.permutation(perm);
553        GenSolvablePolynomialRing<GenPolynomial<C>> sring, psring;
554        GenPolynomialRing<GenPolynomial<C>> pring;
555        if (ring instanceof GenSolvablePolynomialRing) { // permute also solvable relations
556            sring = (GenSolvablePolynomialRing<GenPolynomial<C>>) ring;
557            psring = new GenSolvablePolynomialRing<GenPolynomial<C>>(pFac, sring);
558            List<GenPolynomial<GenPolynomial<C>>> ir = PolynomialList
559                            .<GenPolynomial<C>> castToList(sring.table.relationList());
560            ir = permutationOnCoefficients(perm, psring, ir);
561            psring.addRelations(ir);
562            pring = (GenPolynomialRing<GenPolynomial<C>>) psring;
563        } else {
564            pring = new GenPolynomialRing<GenPolynomial<C>>(pFac, ring);
565        }
566        List<GenPolynomial<GenPolynomial<C>>> pp;
567        List<List<GenPolynomial<GenPolynomial<C>>>> mpolys;
568        mpolys = new ArrayList<List<GenPolynomial<GenPolynomial<C>>>>();
569        for (List<GenPolynomial<GenPolynomial<C>>> ll : P.list) {
570            pp = permutationOnCoefficients(perm, pring, ll);
571            mpolys.add(pp);
572        }
573        OptimizedModuleList<GenPolynomial<C>> op = new OptimizedModuleList<GenPolynomial<C>>(perm, pring,
574                        mpolys);
575        return op;
576    }
577
578}