Source code

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