001 /*
002 * $Id: TermOrderOptimization.java 3446 2010-12-25 21:57:09Z kredel $
003 */
004
005 package edu.jas.poly;
006
007 import java.util.List;
008 import java.util.ArrayList;
009 import java.util.Collection;
010 import java.util.Arrays;
011 import java.util.Map;
012 import java.util.SortedMap;
013 import java.util.TreeMap;
014
015 import org.apache.log4j.Logger;
016
017 import edu.jas.structure.RingElem;
018
019 import edu.jas.arith.BigInteger;
020
021 import edu.jas.poly.GenPolynomial;
022 import edu.jas.poly.GenPolynomialRing;
023
024 import edu.jas.vector.BasicLinAlg;
025
026
027 /**
028 * Term order optimization.
029 * See mas10/maspoly/DIPTOO.m{di}.
030 * @author Heinz Kredel
031 */
032
033 public 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 * Permutation of a list.
201 * @param L list.
202 * @param P permutation.
203 * @return P(L).
204 */
205 public static <T>
206 List<T> listPermutation( List<Integer> P, List<T> L ) {
207 if ( L == null || L.size() <= 1 ) {
208 return L;
209 }
210 List<T> pl = new ArrayList<T>( L.size() );
211 for ( Integer i : P ) {
212 pl.add( L.get( (int)i ) );
213 }
214 return pl;
215 }
216
217
218 /**
219 * Permutation of an array.
220 * Compiles, but does not work, requires JDK 1.6 to work.
221 * @param a array.
222 * @param P permutation.
223 * @return P(a).
224 */
225 @SuppressWarnings("unchecked")
226 public static <T>
227 T[] arrayPermutation( List<Integer> P, T[] a ) {
228 if ( a == null || a.length <= 1 ) {
229 return a;
230 }
231 T[] b = (T[]) new Object[a.length]; // jdk 1.5
232 //T[] b = Arrays.<T>copyOf( a, a.length ); // jdk 1.6, works
233 int j = 0;
234 for ( Integer i : P ) {
235 b[j] = a[ (int)i ];
236 j++;
237 }
238 return b;
239 }
240
241
242 /**
243 * Permutation of an array.
244 * @param a array.
245 * @param P permutation.
246 * @return P(a).
247 */
248 public static
249 String[] stringArrayPermutation( List<Integer> P, String[] a ) {
250 if ( a == null || a.length <= 1 ) {
251 return a;
252 }
253 String[] b = new String[a.length]; // jdk 1.5
254 //T[] b = Arrays.<T>copyOf( a, a.length ); // jdk 1.6
255 int j = 0;
256 for ( Integer i : P ) {
257 b[j] = a[ (int)i ];
258 j++;
259 }
260 return b;
261 }
262
263
264 /**
265 * Permutation of a long array.
266 * @param a array of long.
267 * @param P permutation.
268 * @return P(a).
269 */
270 public static
271 long[] longArrayPermutation( List<Integer> P, long[] a ) {
272 if ( a == null || a.length <= 1 ) {
273 return a;
274 }
275 long[] b = new long[ a.length ];
276 int j = 0;
277 for ( Integer i : P ) {
278 b[j] = a[ (int)i ];
279 j++;
280 }
281 return b;
282 }
283
284
285 /**
286 * Permutation of an exponent vector.
287 * @param e exponent vector.
288 * @param P permutation.
289 * @return P(e).
290 */
291 public static
292 ExpVector permutation( List<Integer> P, ExpVector e ) {
293 if ( e == null ) {
294 return e;
295 }
296 long[] u = longArrayPermutation( P, e.getVal() );
297 ExpVector f = ExpVector.create( u );
298 return f;
299 }
300
301
302 /**
303 * Permutation of polynomial exponent vectors.
304 * @param A polynomial.
305 * @param R polynomial ring.
306 * @param P permutation.
307 * @return P(A).
308 */
309 public static <C extends RingElem<C>>
310 GenPolynomial<C> permutation( List<Integer> P, GenPolynomialRing<C> R, GenPolynomial<C> A ) {
311 if ( A == null ) {
312 return A;
313 }
314 GenPolynomial<C> B = R.getZERO().clone();
315 Map<ExpVector,C> Bv = B.val; //getMap();
316 for ( Map.Entry<ExpVector,C> y: A.getMap().entrySet() ) {
317 ExpVector e = y.getKey();
318 C a = y.getValue();
319 //System.out.println("e = " + e);
320 ExpVector f = permutation(P,e);
321 //System.out.println("f = " + f);
322 Bv.put( f, a ); // assert f not in Bv
323 }
324 return B;
325 }
326
327
328 /**
329 * Permutation of polynomial exponent vectors.
330 * @param L list of polynomials.
331 * @param R polynomial ring.
332 * @param P permutation.
333 * @return P(L).
334 */
335 public static <C extends RingElem<C>>
336 List<GenPolynomial<C>>
337 permutation( List<Integer> P, GenPolynomialRing<C> R, List<GenPolynomial<C>> L ) {
338 if ( L == null || L.size() == 0 ) {
339 return L;
340 }
341 List<GenPolynomial<C>> K = new ArrayList<GenPolynomial<C>>( L.size() );
342 for ( GenPolynomial<C> a: L ) {
343 GenPolynomial<C> b = permutation( P, R, a );
344 K.add( b );
345 }
346 return K;
347 }
348
349
350 /**
351 * Permutation of polynomial exponent vectors of coefficient polynomials.
352 * @param A polynomial.
353 * @param R polynomial ring.
354 * @param P permutation.
355 * @return P(A).
356 */
357 public static <C extends RingElem<C>>
358 GenPolynomial<GenPolynomial<C>>
359 permutationOnCoefficients( List<Integer> P,
360 GenPolynomialRing<GenPolynomial<C>> R,
361 GenPolynomial<GenPolynomial<C>> A ) {
362 if ( A == null ) {
363 return A;
364 }
365 GenPolynomial<GenPolynomial<C>> B = R.getZERO().clone();
366 GenPolynomialRing<C> cf = (GenPolynomialRing<C>) R.coFac;
367 Map<ExpVector,GenPolynomial<C>> Bv = B.val; //getMap();
368 for ( Map.Entry<ExpVector,GenPolynomial<C>> y: A.getMap().entrySet() ) {
369 ExpVector e = y.getKey();
370 GenPolynomial<C> a = y.getValue();
371 //System.out.println("e = " + e);
372 GenPolynomial<C> b = permutation(P,cf,a);
373 //System.out.println("b = " + b);
374 Bv.put( e, b ); // assert e not in Bv
375 }
376 return B;
377 }
378
379
380 /**
381 * Permutation of polynomial exponent vectors of coefficients.
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<GenPolynomial<C>>>
389 permutationOnCoefficients( List<Integer> P,
390 GenPolynomialRing<GenPolynomial<C>> R,
391 List<GenPolynomial<GenPolynomial<C>>> L ) {
392 if ( L == null || L.size() == 0 ) {
393 return L;
394 }
395 List<GenPolynomial<GenPolynomial<C>>> K
396 = new ArrayList<GenPolynomial<GenPolynomial<C>>>( L.size() );
397 for ( GenPolynomial<GenPolynomial<C>> a: L ) {
398 GenPolynomial<GenPolynomial<C>> b = permutationOnCoefficients( P, R, a );
399 K.add( b );
400 }
401 return K;
402 }
403
404
405 /**
406 * Permutation of polynomial ring variables.
407 * @param R polynomial ring.
408 * @param P permutation.
409 * @return P(R).
410 */
411 public static <C extends RingElem<C>>
412 GenPolynomialRing<C>
413 permutation( List<Integer> P, GenPolynomialRing<C> R ) {
414 if ( R == null ) {
415 return R;
416 }
417 if ( R.vars == null || R.nvar <= 1 ) {
418 return R;
419 }
420 GenPolynomialRing<C> S;
421 TermOrder tord = R.tord;
422 if ( tord.getEvord2() != 0 ) {
423 //throw new IllegalArgumentException("split term orders not permutable");
424 logger.warn("split term orders not permutable, resetting to base term order");
425 tord = new TermOrder( tord.getEvord() );
426 }
427 long[][] weight = tord.getWeight();
428 if ( weight != null ) {
429 long[][] w = new long[ weight.length ][];
430 for ( int i = 0; i < weight.length; i++ ) {
431 w[i] = longArrayPermutation(P,weight[i]);
432 }
433 tord = new TermOrder( w );
434 }
435 String[] v1 = new String[R.vars.length];
436 for ( int i = 0; i < v1.length; i++ ) {
437 v1[i] = R.vars[ v1.length-1 - i ];
438 }
439 String[] vars = stringArrayPermutation( P, v1 );
440 String[] v2 = new String[R.vars.length];
441 for ( int i = 0; i < v1.length; i++ ) {
442 v2[i] = vars[ v2.length-1 - i ];
443 }
444 S = new GenPolynomialRing<C>( R.coFac, R.nvar, tord, v2 );
445 return S;
446 }
447
448
449 /**
450 * Optimize variable order.
451 * @param R polynomial ring.
452 * @param L list of polynomials.
453 * @return optimized polynomial list.
454 */
455 public static <C extends RingElem<C>>
456 OptimizedPolynomialList<C>
457 optimizeTermOrder( GenPolynomialRing<C> R, List<GenPolynomial<C>> L ) {
458 List<Integer> perm = optimalPermutation( degreeMatrix(L) );
459 GenPolynomialRing<C> pring;
460 pring = TermOrderOptimization.<C>permutation( perm, R );
461
462 List<GenPolynomial<C>> ppolys;
463 ppolys = TermOrderOptimization.<C>permutation( perm, pring, L );
464
465 OptimizedPolynomialList<C> op
466 = new OptimizedPolynomialList<C>(perm,pring,ppolys);
467 return op;
468 }
469
470
471 /**
472 * Optimize variable order.
473 * @param P polynomial list.
474 * @return optimized polynomial list.
475 */
476 public static <C extends RingElem<C>>
477 OptimizedPolynomialList<C> optimizeTermOrder( PolynomialList<C> P ) {
478 if ( P == null ) {
479 return null;
480 }
481 List<Integer> perm = optimalPermutation( degreeMatrix( P.list ) );
482 GenPolynomialRing<C> pring;
483 pring = TermOrderOptimization.<C>permutation( perm, P.ring );
484
485 List<GenPolynomial<C>> ppolys;
486 ppolys = TermOrderOptimization.<C>permutation( perm, pring, P.list );
487
488 OptimizedPolynomialList<C> op
489 = new OptimizedPolynomialList<C>(perm,pring,ppolys);
490 return op;
491 }
492
493
494 /**
495 * Optimize variable order on coefficients.
496 * @param P polynomial list.
497 * @return optimized polynomial list.
498 */
499 public static <C extends RingElem<C>>
500 OptimizedPolynomialList<GenPolynomial<C>>
501 optimizeTermOrderOnCoefficients( PolynomialList<GenPolynomial<C>> P ) {
502 if ( P == null ) {
503 return null;
504 }
505 List<Integer> perm = optimalPermutation( degreeMatrixOfCoefficients( P.list ) );
506
507 GenPolynomialRing<GenPolynomial<C>> ring = P.ring;
508 GenPolynomialRing<C> coFac = (GenPolynomialRing<C>) ring.coFac;
509 GenPolynomialRing<C> pFac;
510 pFac = TermOrderOptimization.<C>permutation( perm, coFac );
511
512 GenPolynomialRing<GenPolynomial<C>> pring;
513 pring = new GenPolynomialRing<GenPolynomial<C>>(pFac, ring.nvar, ring.tord, ring.vars);
514
515 List<GenPolynomial<GenPolynomial<C>>> ppolys;
516 ppolys = TermOrderOptimization.<C>permutationOnCoefficients( perm, pring, P.list );
517
518 OptimizedPolynomialList<GenPolynomial<C>> op
519 = new OptimizedPolynomialList<GenPolynomial<C>>(perm,pring,ppolys);
520 return op;
521 }
522
523 }