Source code

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