/*
* $Id$
*/
package edu.jas.poly;
import java.util.List;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Arrays;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import org.apache.log4j.Logger;
import edu.jas.structure.RingElem;
import edu.jas.arith.BigInteger;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.vector.BasicLinAlg;
/**
* Term order optimization.
* See mas10/maspoly/DIPTOO.m{di}.
* @author Heinz Kredel
*/
public class TermOrderOptimization {
private static final Logger logger = Logger.getLogger(TermOrderOptimization.class);
//private static boolean debug = logger.isDebugEnabled();
/**
* Degree matrix.
* @param A polynomial to be considered.
* @return degree matrix.
*/
public static >
List> degreeMatrix( GenPolynomial A ) {
List> dem = null;
if ( A == null ) {
return dem;
}
BigInteger cfac = new BigInteger();
GenPolynomialRing ufac
= new GenPolynomialRing(cfac,1);
int nvar = A.numberOfVariables();
dem = new ArrayList>( nvar );
for ( int i = 0; i < nvar; i++ ) {
dem.add( ufac.getZERO() );
}
if ( A.isZERO() ) {
return dem;
}
for ( ExpVector e: A.getMap().keySet() ) {
dem = expVectorAdd(dem, e );
}
return dem;
}
/**
* Degree matrix exponent vector add.
* @param dm degree matrix.
* @param e exponent vector.
* @return degree matrix + e.
*/
public static
List> expVectorAdd(List> dm, ExpVector e) {
for ( int i = 0; i < dm.size() && i < e.length(); i++ ) {
GenPolynomial p = dm.get(i);
long u = e.getVal(i);
ExpVector f = ExpVector.create(1,0,u);
p = p.sum( p.ring.getONECoefficient(), f );
dm.set(i,p);
}
return dm;
}
/**
* Degree matrix of coefficient polynomials.
* @param A polynomial to be considered.
* @return degree matrix for the coeficients.
*/
public static >
List> degreeMatrixOfCoefficients( GenPolynomial> A ) {
if ( A == null ) {
throw new IllegalArgumentException("polynomial must not be null");
}
return degreeMatrix( A.getMap().values() );
}
/**
* Degree matrix.
* @param L list of polynomial to be considered.
* @return degree matrix.
*/
public static >
List> degreeMatrix( Collection> L ) {
if ( L == null ) {
throw new IllegalArgumentException("list must be non null");
}
BasicLinAlg> blas = new BasicLinAlg>();
List> dem = null;
for ( GenPolynomial p : L ) {
List> dm = degreeMatrix( p );
if ( dem == null ) {
dem = dm;
} else {
dem = blas.vectorAdd( dem, dm );
}
}
return dem;
}
/**
* Degree matrix of coefficient polynomials.
* @param L list of polynomial to be considered.
* @return degree matrix for the coeficients.
*/
public static >
List>
degreeMatrixOfCoefficients( Collection>> L ) {
if ( L == null ) {
throw new IllegalArgumentException("list must not be null");
}
BasicLinAlg> blas = new BasicLinAlg>();
List> dem = null;
for ( GenPolynomial> p : L ) {
List> dm = degreeMatrixOfCoefficients( p );
if ( dem == null ) {
dem = dm;
} else {
dem = blas.vectorAdd( dem, dm );
}
}
return dem;
}
/**
* Optimal permutation for the Degree matrix.
* @param D degree matrix.
* @return optimal permutation for D.
*/
public static
List optimalPermutation( List> D ) {
if ( D == null ) {
throw new IllegalArgumentException("list must be non null");
}
List P = new ArrayList( D.size() );
if ( D.size() == 0 ) {
return P;
}
if ( D.size() == 1 ) {
P.add(0);
return P;
}
SortedMap< GenPolynomial, List > map
= new TreeMap,List>();
int i = 0;
for ( GenPolynomial p : D ) {
List il = map.get(p);
if ( il == null ) {
il = new ArrayList(3);
}
il.add( i );
map.put( p, il );
i++;
}
List> V = new ArrayList>( map.values() );
//System.out.println("V = " + V);
//for ( int j = V.size()-1; j >= 0; j-- ) {
for ( int j = 0; j < V.size(); j++ ) {
List v = V.get(j);
for ( Integer k : v ) {
P.add( k );
}
}
return P;
}
/**
* Inverse of a permutation.
* @param P permutation.
* @return S with S*P = id.
*/
public static List inversePermutation( List P ) {
if ( P == null || P.size() <= 1 ) {
return P;
}
List ip = new ArrayList(P); // ensure size and content
for ( int i = 0; i < P.size(); i++ ) {
ip.set(P.get(i),i); // inverse
}
return ip;
}
/**
* Test for identity permutation.
* @param P permutation.
* @return true , if P = id, else false.
*/
public static boolean isIdentityPermutation( List P ) {
if ( P == null || P.size() <= 1 ) {
return true;
}
for ( int i = 0; i < P.size(); i++ ) {
if ( P.get(i).intValue() != i ) {
return false;
}
}
return true;
}
/**
* Multiplication permutations.
* @param P permutation.
* @param S permutation.
* @return P*S.
*/
public static List multiplyPermutation( List P, List S ) {
if ( P == null || S == null ) {
return null;
}
if ( P.size() != S.size() ) {
throw new IllegalArgumentException("#P != #S: P =" + P + ", S = " + S);
}
List ip = new ArrayList(P); // ensure size and content
for ( int i = 0; i < P.size(); i++ ) {
ip.set(i,S.get(P.get(i)));
}
return ip;
}
/**
* Permutation of a list.
* @param L list.
* @param P permutation.
* @return P(L).
*/
public static List listPermutation( List P, List L ) {
if ( L == null || L.size() <= 1 ) {
return L;
}
List pl = new ArrayList( L.size() );
for ( Integer i : P ) {
pl.add( L.get( (int)i ) );
}
return pl;
}
/**
* Permutation of an array.
* Compiles, but does not work, requires JDK 1.6 to work.
* @param a array.
* @param P permutation.
* @return P(a).
*/
@SuppressWarnings("unchecked")
public static T[] arrayPermutation( List P, T[] a ) {
if ( a == null || a.length <= 1 ) {
return a;
}
T[] b = (T[]) new Object[a.length]; // jdk 1.5
//T[] b = Arrays.copyOf( a, a.length ); // jdk 1.6, works
int j = 0;
for ( Integer i : P ) {
b[j] = a[ (int)i ];
j++;
}
return b;
}
/**
* Permutation of an array.
* @param a array.
* @param P permutation.
* @return P(a).
*/
public static String[] stringArrayPermutation( List P, String[] a ) {
if ( a == null || a.length <= 1 ) {
return a;
}
String[] b = new String[a.length]; // jdk 1.5
//T[] b = Arrays.copyOf( a, a.length ); // jdk 1.6
int j = 0;
for ( Integer i : P ) {
b[j] = a[ (int)i ];
j++;
}
return b;
}
/**
* Permutation of a long array.
* @param a array of long.
* @param P permutation.
* @return P(a).
*/
public static long[] longArrayPermutation( List P, long[] a ) {
if ( a == null || a.length <= 1 ) {
return a;
}
long[] b = new long[ a.length ];
int j = 0;
for ( Integer i : P ) {
b[j] = a[ (int)i ];
j++;
}
return b;
}
/**
* Permutation of an exponent vector.
* @param e exponent vector.
* @param P permutation.
* @return P(e).
*/
public static
ExpVector permutation( List P, ExpVector e ) {
if ( e == null ) {
return e;
}
long[] u = longArrayPermutation( P, e.getVal() );
ExpVector f = ExpVector.create( u );
return f;
}
/**
* Permutation of polynomial exponent vectors.
* @param A polynomial.
* @param R polynomial ring.
* @param P permutation.
* @return P(A).
*/
public static >
GenPolynomial permutation( List P, GenPolynomialRing R, GenPolynomial A ) {
if ( A == null ) {
return A;
}
GenPolynomial B = R.getZERO().copy();
Map Bv = B.val; //getMap();
for ( Map.Entry y: A.getMap().entrySet() ) {
ExpVector e = y.getKey();
C a = y.getValue();
//System.out.println("e = " + e);
ExpVector f = permutation(P,e);
//System.out.println("f = " + f);
Bv.put( f, a ); // assert f not in Bv
}
return B;
}
/**
* Permutation of polynomial exponent vectors.
* @param L list of polynomials.
* @param R polynomial ring.
* @param P permutation.
* @return P(L).
*/
public static >
List>
permutation( List P, GenPolynomialRing R, List> L ) {
if ( L == null || L.size() == 0 ) {
return L;
}
List> K = new ArrayList>( L.size() );
for ( GenPolynomial a: L ) {
GenPolynomial b = permutation( P, R, a );
K.add( b );
}
return K;
}
/**
* Permutation of polynomial exponent vectors of coefficient polynomials.
* @param A polynomial.
* @param R polynomial ring.
* @param P permutation.
* @return P(A).
*/
public static >
GenPolynomial>
permutationOnCoefficients( List P,
GenPolynomialRing> R,
GenPolynomial> A ) {
if ( A == null ) {
return A;
}
GenPolynomial> B = R.getZERO().copy();
GenPolynomialRing cf = (GenPolynomialRing) R.coFac;
Map> Bv = B.val; //getMap();
for ( Map.Entry> y: A.getMap().entrySet() ) {
ExpVector e = y.getKey();
GenPolynomial a = y.getValue();
//System.out.println("e = " + e);
GenPolynomial b = permutation(P,cf,a);
//System.out.println("b = " + b);
Bv.put( e, b ); // assert e not in Bv
}
return B;
}
/**
* Permutation of polynomial exponent vectors of coefficients.
* @param L list of polynomials.
* @param R polynomial ring.
* @param P permutation.
* @return P(L).
*/
public static >
List>>
permutationOnCoefficients( List P,
GenPolynomialRing> R,
List>> L ) {
if ( L == null || L.size() == 0 ) {
return L;
}
List>> K
= new ArrayList>>( L.size() );
for ( GenPolynomial> a: L ) {
GenPolynomial> b = permutationOnCoefficients( P, R, a );
K.add( b );
}
return K;
}
/**
* Permutation of polynomial ring variables.
* @param R polynomial ring.
* @param P permutation.
* @return P(R).
*/
public static >
GenPolynomialRing
permutation( List P, GenPolynomialRing R ) {
if ( R == null ) {
return R;
}
if ( R.vars == null || R.nvar <= 1 ) {
return R;
}
GenPolynomialRing S;
TermOrder tord = R.tord;
if ( tord.getEvord2() != 0 ) {
//throw new IllegalArgumentException("split term orders not permutable");
tord = new TermOrder( tord.getEvord2() );
logger.warn("split term order '" + R.tord + "' not permutable, resetting to most base term order " + tord);
}
long[][] weight = tord.getWeight();
if ( weight != null ) {
long[][] w = new long[ weight.length ][];
for ( int i = 0; i < weight.length; i++ ) {
w[i] = longArrayPermutation(P,weight[i]);
}
tord = new TermOrder( w );
}
String[] v1 = new String[R.vars.length];
for ( int i = 0; i < v1.length; i++ ) {
v1[i] = R.vars[ v1.length-1 - i ];
}
String[] vars = stringArrayPermutation( P, v1 );
String[] v2 = new String[R.vars.length];
for ( int i = 0; i < v1.length; i++ ) {
v2[i] = vars[ v2.length-1 - i ];
}
S = new GenPolynomialRing( R.coFac, R.nvar, tord, v2 );
return S;
}
/**
* Optimize variable order.
* @param R polynomial ring.
* @param L list of polynomials.
* @return optimized polynomial list.
*/
public static >
OptimizedPolynomialList
optimizeTermOrder( GenPolynomialRing R, List> L ) {
List perm = optimalPermutation( degreeMatrix(L) );
GenPolynomialRing pring = TermOrderOptimization.permutation( perm, R );
List> ppolys = TermOrderOptimization.permutation( perm, pring, L );
OptimizedPolynomialList op = new OptimizedPolynomialList(perm,pring,ppolys);
return op;
}
/**
* Optimize variable order.
* @param P polynomial list.
* @return optimized polynomial list.
*/
public static >
OptimizedPolynomialList optimizeTermOrder( PolynomialList P ) {
if ( P == null ) {
return null;
}
return optimizeTermOrder( P.ring, P.list );
}
/**
* Optimize variable order on coefficients.
* @param P polynomial list.
* @return optimized polynomial list.
*/
public static >
OptimizedPolynomialList>
optimizeTermOrderOnCoefficients( PolynomialList> P ) {
if ( P == null ) {
return null;
}
List perm = optimalPermutation( degreeMatrixOfCoefficients( P.list ) );
GenPolynomialRing> ring = P.ring;
GenPolynomialRing coFac = (GenPolynomialRing) ring.coFac;
GenPolynomialRing pFac;
pFac = TermOrderOptimization.permutation( perm, coFac );
GenPolynomialRing> pring;
pring = new GenPolynomialRing>(pFac, ring.nvar, ring.tord, ring.vars);
List>> ppolys;
ppolys = TermOrderOptimization.permutationOnCoefficients( perm, pring, P.list );
OptimizedPolynomialList> op
= new OptimizedPolynomialList>(perm,pring,ppolys);
return op;
}
}
Ads help maintain this website.