edu.jas.poly
Class PolyUtil

java.lang.Object
  edu.jas.poly.PolyUtil

public class PolyUtil
extends java.lang.Object

Polynomial utilities, e.g. conversion between different representations, evaluation and interpolation.

Author:

Heinz Kredel

Constructor Summary

PolyUtil()

Method Summary

static <C extends RingElem<C>> GenPolynomial<C>	baseDeriviative(GenPolynomial<C> P) GenPolynomial polynomial derivative main variable.
static <C extends RingElem<C>> GenPolynomial<C>	basePseudoDivide(GenPolynomial<C> P, GenPolynomial<C> S) GenPolynomial pseudo divide.
static <C extends RingElem<C>> GenPolynomial<C>	basePseudoRemainder(GenPolynomial<C> P, GenPolynomial<C> S) GenPolynomial sparse pseudo remainder.
static <C extends RingElem<C>> GenPolynomial<C>	baseRemainderPoly(GenPolynomial<C> P, C s) GenPolynomial coefficient wise remainder.
static GenPolynomial<ModInteger>	chineseRemainder(GenPolynomialRing<ModInteger> fac, GenPolynomial<ModInteger> A, ModInteger mi, GenPolynomial<ModInteger> B) ModInteger chinese remainder algorithm on coefficients.
static <C extends RingElem<C>> long	coeffMaxDegree(GenPolynomial<GenPolynomial<C>> A) Maximal degree in the coefficient polynomials.
static GenPolynomial<BigComplex>	complexFromRational(GenPolynomialRing<BigComplex> fac, GenPolynomial<BigRational> A) Complex from rational real part.
static <C extends RingElem<C>> GenPolynomial<C>	distribute(GenPolynomialRing<C> dfac, GenPolynomial<GenPolynomial<C>> B) Distribute a recursive polynomial to a generic polynomial.
static <C extends RingElem<C>> GenPolynomial<C>	evaluate(GenPolynomialRing<C> cfac, GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomialRing<GenPolynomial<C>> nfac, GenPolynomialRing<C> dfac, GenPolynomial<C> A, C a) Evaluate at k-th variable.
static <C extends RingElem<C>> GenPolynomial<C>	evaluateFirst(GenPolynomialRing<C> cfac, GenPolynomialRing<C> dfac, GenPolynomial<C> A, C a) Evaluate at first (lowest) variable.
static <C extends RingElem<C>> GenPolynomial<C>	evaluateFirstRec(GenPolynomialRing<C> cfac, GenPolynomialRing<C> dfac, GenPolynomial<GenPolynomial<C>> A, C a) Evaluate at first (lowest) variable.
static <C extends RingElem<C>> GenPolynomial<C>	evaluateMain(GenPolynomialRing<C> cfac, GenPolynomial<GenPolynomial<C>> A, C a) Evaluate at main variable.
static <C extends RingElem<C>> C	evaluateMain(RingFactory<C> cfac, GenPolynomial<C> A, C a) Evaluate at main variable.
static BigInteger	factorBound(ExpVector e) Factor coefficient bound.
static <C extends RingElem<C>> GenPolynomial<C>	fromIntegerCoefficients(GenPolynomialRing<C> fac, GenPolynomial<BigInteger> A) From BigInteger coefficients.
static <C extends RingElem<C>> java.util.List<GenPolynomial<C>>	fromIntegerCoefficients(GenPolynomialRing<C> fac, java.util.List<GenPolynomial<BigInteger>> L) From BigInteger coefficients.
static GenPolynomial<BigRational>	imaginaryPart(GenPolynomialRing<BigRational> fac, GenPolynomial<BigComplex> A) Imaginary part.
static GenPolynomial<BigInteger>	integerFromModularCoefficients(GenPolynomialRing<BigInteger> fac, GenPolynomial<ModInteger> A) BigInteger from ModInteger coefficients, symmetric.
static GenPolynomial<BigInteger>	integerFromModularCoefficientsPositive(GenPolynomialRing<BigInteger> fac, GenPolynomial<ModInteger> A) BigInteger from ModInteger coefficients, positive.
static GenPolynomial<BigInteger>	integerFromRationalCoefficients(GenPolynomialRing<BigInteger> fac, GenPolynomial<BigRational> A) BigInteger from BigRational coefficients.
static java.util.List<GenPolynomial<BigInteger>>	integerFromRationalCoefficients(GenPolynomialRing<BigInteger> fac, java.util.List<GenPolynomial<BigRational>> L) BigInteger from BigRational coefficients.
static <C extends RingElem<C>> GenPolynomial<C>	interpolate(GenPolynomialRing<C> fac, GenPolynomial<C> A, GenPolynomial<C> M, C mi, C a, C am) Univariate polynomial interpolation.
static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>>	interpolate(GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<GenPolynomial<C>> A, GenPolynomial<C> M, C mi, GenPolynomial<C> B, C am) ModInteger interpolate on first variable.
static GenPolynomial<BigInteger>[]	liftHensel(GenPolynomial<BigInteger> C, BigInteger M, GenPolynomial<ModInteger> A, GenPolynomial<ModInteger> B, GenPolynomial<ModInteger> S, GenPolynomial<ModInteger> T) ModInteger Hensel lifting algorithm on coefficients.
static GenPolynomial<BigInteger>[]	liftHenselQuadratic(GenPolynomial<BigInteger> C, BigInteger M, GenPolynomial<ModInteger> A, GenPolynomial<ModInteger> B, GenPolynomial<ModInteger> S, GenPolynomial<ModInteger> T) ModInteger Hensel lifting algorithm on coefficients.
static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>>	monic(GenPolynomial<GenPolynomial<C>> p) GenPolynomial monic, i.e. leadingBaseCoefficient == 1.
static GenPolynomial<BigRational>	realPart(GenPolynomialRing<BigRational> fac, GenPolynomial<BigComplex> A) Real part.
static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>>	recursive(GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A) Recursive representation.
static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>>	recursiveDeriviative(GenPolynomial<GenPolynomial<C>> P) GenPolynomial recursive polynomial derivative main variable.
static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>>	recursiveDivide(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<C> s) GenPolynomial pseudo divide.
static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>>	recursivePseudoDivide(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) GenPolynomial pseudo divide.
static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>>	recursivePseudoRemainder(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) GenPolynomial sparse pseudo remainder.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PolyUtil

public PolyUtil()

Method Detail

recursive

public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursive(GenPolynomialRing<GenPolynomial<C>> rfac,
                                                                                GenPolynomial<C> A)

Recursive representation. Represent as polynomial in i variables with coefficients in n-i variables. Works for arbitrary term orders.

Parameters:

rfac - recursive polynomial ring factory.

A - polynomial to be converted.

Returns:

Recursive represenations of this in the ring rfac.

distribute

public static <C extends RingElem<C>> GenPolynomial<C> distribute(GenPolynomialRing<C> dfac,
                                                                  GenPolynomial<GenPolynomial<C>> B)

Distribute a recursive polynomial to a generic polynomial. Works for arbitrary term orders.

Parameters:

dfac - combined polynomial ring factory of coefficients and this.

B - polynomial to be converted.

Returns:

distributed polynomial.

integerFromModularCoefficients

public static GenPolynomial<BigInteger> integerFromModularCoefficients(GenPolynomialRing<BigInteger> fac,
                                                                       GenPolynomial<ModInteger> A)

BigInteger from ModInteger coefficients, symmetric. Represent as polynomial with BigInteger coefficients by removing the modules and making coefficients symmetric to 0.

Parameters:

fac - result polynomial factory.

A - polynomial with ModInteger coefficients to be converted.

Returns:

polynomial with BigInteger coefficients.

integerFromModularCoefficientsPositive

public static GenPolynomial<BigInteger> integerFromModularCoefficientsPositive(GenPolynomialRing<BigInteger> fac,
                                                                               GenPolynomial<ModInteger> A)

BigInteger from ModInteger coefficients, positive. Represent as polynomial with BigInteger coefficients by removing the modules.

Parameters:

fac - result polynomial factory.

A - polynomial with ModInteger coefficients to be converted.

Returns:

polynomial with BigInteger coefficients.

integerFromRationalCoefficients

public static GenPolynomial<BigInteger> integerFromRationalCoefficients(GenPolynomialRing<BigInteger> fac,
                                                                        GenPolynomial<BigRational> A)

BigInteger from BigRational coefficients. Represent as polynomial with BigInteger coefficients by multiplication with the lcm of the numerators of the BigRational coefficients.

Parameters:

fac - result polynomial factory.

A - polynomial with BigRational coefficients to be converted.

Returns:

polynomial with BigInteger coefficients.

integerFromRationalCoefficients

public static java.util.List<GenPolynomial<BigInteger>> integerFromRationalCoefficients(GenPolynomialRing<BigInteger> fac,
                                                                                        java.util.List<GenPolynomial<BigRational>> L)

BigInteger from BigRational coefficients. Represent as list of polynomials with BigInteger coefficients by multiplication with the lcm of the numerators of the BigRational coefficients of each polynomial.

Parameters:

fac - result polynomial factory.

L - list of polynomials with BigRational coefficients to be converted.

Returns:

polynomial list with BigInteger coefficients.

fromIntegerCoefficients

public static <C extends RingElem<C>> GenPolynomial<C> fromIntegerCoefficients(GenPolynomialRing<C> fac,
                                                                               GenPolynomial<BigInteger> A)

From BigInteger coefficients. Represent as polynomial with type C coefficients, e.g. ModInteger or BigRational.

Parameters:

fac - result polynomial factory.

A - polynomial with BigInteger coefficients to be converted.

Returns:

polynomial with type C coefficients.

fromIntegerCoefficients

public static <C extends RingElem<C>> java.util.List<GenPolynomial<C>> fromIntegerCoefficients(GenPolynomialRing<C> fac,
                                                                                               java.util.List<GenPolynomial<BigInteger>> L)

From BigInteger coefficients. Represent as list of polynomials with type C coefficients, e.g. ModInteger or BigRational.

Parameters:

fac - result polynomial factory.

L - list of polynomials with BigInteger coefficients to be converted.

Returns:

list of polynomials with type C coefficients.

realPart

public static GenPolynomial<BigRational> realPart(GenPolynomialRing<BigRational> fac,
                                                  GenPolynomial<BigComplex> A)

Real part.

Parameters:

fac - result polynomial factory.

A - polynomial with BigComplex coefficients to be converted.

Returns:

polynomial with real part of the coefficients.

imaginaryPart

public static GenPolynomial<BigRational> imaginaryPart(GenPolynomialRing<BigRational> fac,
                                                       GenPolynomial<BigComplex> A)

Imaginary part.

Parameters:

fac - result polynomial factory.

A - polynomial with BigComplex coefficients to be converted.

Returns:

polynomial with imaginary part of coefficients.

complexFromRational

public static GenPolynomial<BigComplex> complexFromRational(GenPolynomialRing<BigComplex> fac,
                                                            GenPolynomial<BigRational> A)

Complex from rational real part.

Parameters:

fac - result polynomial factory.

A - polynomial with BigRational coefficients to be converted.

Returns:

polynomial with BigComplex coefficients.

chineseRemainder

public static GenPolynomial<ModInteger> chineseRemainder(GenPolynomialRing<ModInteger> fac,
                                                         GenPolynomial<ModInteger> A,
                                                         ModInteger mi,
                                                         GenPolynomial<ModInteger> B)

ModInteger chinese remainder algorithm on coefficients.

Parameters:

fac - GenPolynomial result factory with A.coFac.modul*B.coFac.modul = C.coFac.modul.

A - GenPolynomial.

B - other GenPolynomial.

mi - inverse of A.coFac.modul in ring B.coFac.

Returns:

S = cra(A,B), with S mod A.coFac.modul == A and S mod B.coFac.modul == B.

monic

public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> monic(GenPolynomial<GenPolynomial<C>> p)

GenPolynomial monic, i.e. leadingBaseCoefficient == 1. If leadingBaseCoefficient is not invertible returns this unmodified.

Parameters:

p - recursive GenPolynomial>.

Returns:

monic(p).

baseRemainderPoly

public static <C extends RingElem<C>> GenPolynomial<C> baseRemainderPoly(GenPolynomial<C> P,
                                                                         C s)

GenPolynomial coefficient wise remainder.

See Also:

GenPolynomial.remainder(edu.jas.poly.GenPolynomial).

Parameters:

P - GenPolynomial.

s - nonzero coefficient.

Returns:

coefficient wise remainder.

basePseudoRemainder

public static <C extends RingElem<C>> GenPolynomial<C> basePseudoRemainder(GenPolynomial<C> P,
                                                                           GenPolynomial<C> S)

GenPolynomial sparse pseudo remainder. For univariate polynomials.

See Also:

GenPolynomial.remainder(edu.jas.poly.GenPolynomial).

Parameters:

P - GenPolynomial.

S - nonzero GenPolynomial.

Returns:

remainder with ldcf(S)^m' P = quotient * S + remainder.

basePseudoDivide

public static <C extends RingElem<C>> GenPolynomial<C> basePseudoDivide(GenPolynomial<C> P,
                                                                        GenPolynomial<C> S)

GenPolynomial pseudo divide. For univariate polynomials or exact division.

See Also:

GenPolynomial.divide(edu.jas.poly.GenPolynomial).

Parameters:

P - GenPolynomial.

S - nonzero GenPolynomial.

Returns:

quotient with ldcf(S)^m' P = quotient * S + remainder.

recursiveDivide

public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursiveDivide(GenPolynomial<GenPolynomial<C>> P,
                                                                                      GenPolynomial<C> s)

GenPolynomial pseudo divide. For recursive polynomials. Division by coefficient ring element.

Parameters:

P - recursive GenPolynomial.

s - GenPolynomial.

Returns:

this/s.

recursivePseudoRemainder

public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursivePseudoRemainder(GenPolynomial<GenPolynomial<C>> P,
                                                                                               GenPolynomial<GenPolynomial<C>> S)

GenPolynomial sparse pseudo remainder. For recursive polynomials.

See Also:

GenPolynomial.remainder(edu.jas.poly.GenPolynomial).

Parameters:

P - recursive GenPolynomial.

S - nonzero recursive GenPolynomial.

Returns:

remainder with ldcf(S)^m' P = quotient * S + remainder.

recursivePseudoDivide

public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursivePseudoDivide(GenPolynomial<GenPolynomial<C>> P,
                                                                                            GenPolynomial<GenPolynomial<C>> S)

GenPolynomial pseudo divide. For recursive polynomials.

See Also:

GenPolynomial.remainder(edu.jas.poly.GenPolynomial).

Parameters:

P - recursive GenPolynomial.

S - nonzero recursive GenPolynomial.

Returns:

quotient with ldcf(S)^m P = quotient * S + remainder.

baseDeriviative

public static <C extends RingElem<C>> GenPolynomial<C> baseDeriviative(GenPolynomial<C> P)

GenPolynomial polynomial derivative main variable.

Parameters:

P - GenPolynomial.

Returns:

deriviative(P).

recursiveDeriviative

public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> recursiveDeriviative(GenPolynomial<GenPolynomial<C>> P)

GenPolynomial recursive polynomial derivative main variable.

Parameters:

P - recursive GenPolynomial.

Returns:

deriviative(P).

factorBound

public static BigInteger factorBound(ExpVector e)

Factor coefficient bound. See SACIPOL.IPFCB: the product of all maxNorms of potential factors is less than or equal to 2**b times the maxNorm of A.

Parameters:

e - degree vector of a GenPolynomial A.

Returns:

2**b.

evaluateMain

public static <C extends RingElem<C>> GenPolynomial<C> evaluateMain(GenPolynomialRing<C> cfac,
                                                                    GenPolynomial<GenPolynomial<C>> A,
                                                                    C a)

Evaluate at main variable.

Parameters:

cfac - coefficent polynomial ring factory.

A - polynomial to be evaluated.

a - value to evaluate at.

Returns:

A( x_1, ..., x_{n-1}, a ).

evaluateMain

public static <C extends RingElem<C>> C evaluateMain(RingFactory<C> cfac,
                                                     GenPolynomial<C> A,
                                                     C a)

Evaluate at main variable.

Parameters:

cfac - coefficent ring factory.

A - univariate polynomial to be evaluated.

a - value to evaluate at.

Returns:

A( a ).

evaluate

public static <C extends RingElem<C>> GenPolynomial<C> evaluate(GenPolynomialRing<C> cfac,
                                                                GenPolynomialRing<GenPolynomial<C>> rfac,
                                                                GenPolynomialRing<GenPolynomial<C>> nfac,
                                                                GenPolynomialRing<C> dfac,
                                                                GenPolynomial<C> A,
                                                                C a)

Evaluate at k-th variable.

Parameters:

cfac - coefficient polynomial ring in k variables C[x_1, ..., x_k] factory.

rfac - coefficient polynomial ring C[x_1, ..., x_{k-1}] [x_k] factory, a recursive polynomial ring in 1 variable with coefficients in k-1 variables.

nfac - polynomial ring in n-1 varaibles C[x_1, ..., x_{k-1}] [x_{k+1}, ..., x_n] factory, a recursive polynomial ring in n-k+1 variables with coefficients in k-1 variables.

dfac - polynomial ring in n-1 variables. C[x_1, ..., x_{k-1}, x_{k+1}, ..., x_n] factory.

A - polynomial to be evaluated.

a - value to evaluate at.

Returns:

A( x_1, ..., x_{k-1}, a, x_{k+1}, ..., x_n).

evaluateFirst

public static <C extends RingElem<C>> GenPolynomial<C> evaluateFirst(GenPolynomialRing<C> cfac,
                                                                     GenPolynomialRing<C> dfac,
                                                                     GenPolynomial<C> A,
                                                                     C a)

Evaluate at first (lowest) variable.

Parameters:

cfac - coefficient polynomial ring in first variable C[x_1] factory.

dfac - polynomial ring in n-1 variables. C[x_2, ..., x_n] factory.

A - polynomial to be evaluated.

a - value to evaluate at.

Returns:

A( a, x_2, ..., x_n).

evaluateFirstRec

public static <C extends RingElem<C>> GenPolynomial<C> evaluateFirstRec(GenPolynomialRing<C> cfac,
                                                                        GenPolynomialRing<C> dfac,
                                                                        GenPolynomial<GenPolynomial<C>> A,
                                                                        C a)

Evaluate at first (lowest) variable. Could also be called evaluateFirst(), but type erasure of A parameter does not allow same name.

Parameters:

cfac - coefficient polynomial ring in first variable C[x_1] factory.

dfac - polynomial ring in n-1 variables. C[x_2, ..., x_n] factory.

A - recursive polynomial to be evaluated.

a - value to evaluate at.

Returns:

A( a, x_2, ..., x_n).

interpolate

public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> interpolate(GenPolynomialRing<GenPolynomial<C>> fac,
                                                                                  GenPolynomial<GenPolynomial<C>> A,
                                                                                  GenPolynomial<C> M,
                                                                                  C mi,
                                                                                  GenPolynomial<C> B,
                                                                                  C am)

ModInteger interpolate on first variable.

Parameters:

fac - GenPolynomial result factory.

A - GenPolynomial.

M - GenPolynomial interpolation modul of A.

mi - inverse of M(am) in ring fac.coFac.

B - evaluation of other GenPolynomial.

am - evaluation point (interpolation modul) of B, i.e. P(am) = B.

Returns:

S, with S mod M == A and S(am) == B.

interpolate

public static <C extends RingElem<C>> GenPolynomial<C> interpolate(GenPolynomialRing<C> fac,
                                                                   GenPolynomial<C> A,
                                                                   GenPolynomial<C> M,
                                                                   C mi,
                                                                   C a,
                                                                   C am)

Univariate polynomial interpolation.

Parameters:

fac - GenPolynomial result factory.

A - GenPolynomial.

M - GenPolynomial interpolation modul of A.

mi - inverse of M(am) in ring fac.coFac.

a - evaluation of other GenPolynomial.

am - evaluation point (interpolation modul) of a, i.e. P(am) = a.

Returns:

S, with S mod M == A and S(am) == a.

coeffMaxDegree

public static <C extends RingElem<C>> long coeffMaxDegree(GenPolynomial<GenPolynomial<C>> A)

Maximal degree in the coefficient polynomials.

Returns:

maximal degree in the coefficients.

liftHensel

public static GenPolynomial<BigInteger>[] liftHensel(GenPolynomial<BigInteger> C,
                                                     BigInteger M,
                                                     GenPolynomial<ModInteger> A,
                                                     GenPolynomial<ModInteger> B,
                                                     GenPolynomial<ModInteger> S,
                                                     GenPolynomial<ModInteger> T)

ModInteger Hensel lifting algorithm on coefficients. Let p = A.ring.coFac.modul() = B.ring.coFac.modul() and assume C == A*B mod p with ggt(A,B) == 1 mod p and S A + T B == 1 mod p. See Algorithm 6.1. in Geddes et.al.. Linear version, as it does not lift S A + T B == 1 mod p^{e+1}.

Parameters:

C - GenPolynomial.

A - GenPolynomial.

B - other GenPolynomial.

S - GenPolynomial.

T - GenPolynomial.

M - bound on the coefficients of A1 and B1 as factors of C.

Returns:

[A1,B1] = lift(C,A,B), with C = A1 * B1.

liftHenselQuadratic

public static GenPolynomial<BigInteger>[] liftHenselQuadratic(GenPolynomial<BigInteger> C,
                                                              BigInteger M,
                                                              GenPolynomial<ModInteger> A,
                                                              GenPolynomial<ModInteger> B,
                                                              GenPolynomial<ModInteger> S,
                                                              GenPolynomial<ModInteger> T)

ModInteger Hensel lifting algorithm on coefficients. Let p = A.ring.coFac.modul() = B.ring.coFac.modul() and assume C == A*B mod p with ggt(A,B) == 1 mod p and S A + T B == 1 mod p. See algorithm 6.1. in Geddes et.al. and algorithms 3.5.{5,6} in Cohen. Quadratic version, as it also lifts S A + T B == 1 mod p^{e+1}.

Parameters:

C - GenPolynomial.

A - GenPolynomial.

B - other GenPolynomial.

S - GenPolynomial.

T - GenPolynomial.

M - bound on the coefficients of A1 and B1 as factors of C.

Returns:

[A1,B1] = lift(C,A,B), with C = A1 * B1.