Package edu.jas.ufd
Class PolyUfdUtil
- java.lang.Object
-
- edu.jas.ufd.PolyUfdUtil
-
public class PolyUfdUtil extends java.lang.Object
Polynomial ufd utilities. For example conversion between different representations and Kronecker substitution.- Author:
- Heinz Kredel
-
-
Constructor Summary
Constructors Constructor Description PolyUfdUtil()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <C extends GcdRingElem<C>>
GenPolynomial<C>[]agcd(GenPolynomial<C> R, GenPolynomial<C> S, int n)
GenPolynomial approximate common divisor.static <C extends GcdRingElem<C>>
AlgebraicNumberRing<C>algebraicNumberField(GenPolynomialRing<C> ring, int degree)
Construct an algebraic number field of degree d.static <C extends GcdRingElem<C>>
AlgebraicNumberRing<C>algebraicNumberField(RingFactory<C> cfac, int degree)
Construct an algebraic number field of degree d.static <C extends GcdRingElem<C>>
Quotient<C>approximantOfPade(UnivPowerSeriesRing<C> upr, TaylorFunction<C> f, C a, int m, int n)
Pade approximant [m/n] of function f.static <C extends GcdRingElem<C>>
GenPolynomial<C>backSubstituteKronecker(GenPolynomialRing<C> fac, GenPolynomial<C> A, long d)
Kronecker back substitution.static <C extends GcdRingElem<C>>
java.util.List<GenPolynomial<C>>backSubstituteKronecker(GenPolynomialRing<C> fac, java.util.List<GenPolynomial<C>> A, long d)
Kronecker back substitution.static <C extends GcdRingElem<C>>
java.util.ArrayList<java.util.ArrayList<C>>constructQmatrix(GenPolynomial<C> A)
Construct Berlekamp Q matrix.static <C extends GcdRingElem<C>>
Quotient<C>derivative(Quotient<C> r)
Derivation of a univariate rational function.static <C extends GcdRingElem<C>>
Quotient<C>derivative(Quotient<C> Q, int r)
Polynomial quotient partial derivative variable r.static <C extends GcdRingElem<C>>
voidensureFieldProperty(AlgebraicNumberRing<C> afac)
Ensure that the field property is determined.static <C extends GcdRingElem<C>>
CevaluateAll(RingFactory<C> cfac, Quotient<C> A, java.util.List<C> a)
Evaluate all variables.static <C extends GcdRingElem<C>>
CevaluateMain(RingFactory<C> cfac, Quotient<C> A, C a)
Evaluate at main variable.static <C extends GcdRingElem<C>>
EvalPoints<C>evaluationPoints(GenPolynomial<C> A)
Polynomial suitable evaluation points. deg(B) = deg(A(x_1,...)) and B is also squarefree.static <C extends GcdRingElem<C>>
GenExteriorPolynomial<Quotient<C>>exteriorDerivativeQuot(GenExteriorPolynomial<Quotient<C>> P)
GenExteriorPolynomial over polynomial quotient exterior derivative.static <C extends GcdRingElem<C>>
java.util.SortedMap<Quotient<C>,java.lang.Long>factors(Quotient<C> A)
Factors of Quotient rational function.static <C extends RingElem<C>>
GenPolynomial<GenPolynomial<C>>fromIntegerCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<GenPolynomial<BigInteger>> A)
From BigInteger coefficients.static <C extends RingElem<C>>
java.util.List<GenPolynomial<GenPolynomial<C>>>fromIntegerCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, java.util.List<GenPolynomial<GenPolynomial<BigInteger>>> L)
From BigInteger coefficients.static GenPolynomial<GenPolynomial<BigInteger>>
integerFromRationalCoefficients(GenPolynomialRing<GenPolynomial<BigInteger>> fac, GenPolynomial<GenPolynomial<BigRational>> A)
BigInteger from BigRational coefficients.static java.util.List<GenPolynomial<GenPolynomial<BigInteger>>>
integerFromRationalCoefficients(GenPolynomialRing<GenPolynomial<BigInteger>> fac, java.util.List<GenPolynomial<GenPolynomial<BigRational>>> L)
BigInteger from BigRational coefficients.static <C extends GcdRingElem<C>>
GenPolynomial<GenPolynomial<C>>integralFromQuotientCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<Quotient<C>> A)
Integral polynomial from rational function coefficients.static <C extends GcdRingElem<C>>
java.util.List<GenPolynomial<GenPolynomial<C>>>integralFromQuotientCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, java.util.Collection<GenPolynomial<Quotient<C>>> L)
Integral polynomial from rational function coefficients.static <C extends GcdRingElem<C>>
GenPolynomial<GenPolynomial<C>>introduceLowerVariable(GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A)
Introduce lower variable.static <C extends GcdRingElem<C>>
booleanisFactorization(Quotient<C> P, java.util.SortedMap<Quotient<C>,java.lang.Long> F)
Quotient is (squarefree) factorization.static <C extends GcdRingElem<C>>
GenPolynomial<C>norm(GenPolynomial<AlgebraicNumber<C>> A)
Norm of a polynomial with AlgebraicNumber coefficients.static <C extends GcdRingElem<C>>
GenPolynomial<C>norm(GenPolynomial<AlgebraicNumber<C>> A, long k)
Norm of a polynomial with AlgebraicNumber coefficients.static <C extends GcdRingElem<C>>
GenPolynomial<Quotient<C>>quotientFromIntegralCoefficients(GenPolynomialRing<Quotient<C>> fac, GenPolynomial<GenPolynomial<C>> A)
Rational function from integral polynomial coefficients.static <C extends GcdRingElem<C>>
java.util.List<GenPolynomial<Quotient<C>>>quotientFromIntegralCoefficients(GenPolynomialRing<Quotient<C>> fac, java.util.Collection<GenPolynomial<GenPolynomial<C>>> L)
Rational function from integral polynomial coefficients.static <C extends GcdRingElem<C>>
GenPolynomial<C>randomIrreduciblePolynomial(GenPolynomialRing<C> ring, int degree)
Construct a random irreducible univariate polynomial of degree d.static <C extends GcdRingElem<C>>
GenPolynomial<C>randomIrreduciblePolynomial(RingFactory<C> cfac, int degree)
Construct a random irreducible univariate polynomial of degree d.static <C extends GcdRingElem<C>>
GenPolynomial<AlgebraicNumber<C>>substituteConvertToAlgebraicCoefficients(GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A, long k)
Convert to AlgebraicNumber coefficients.static <C extends GcdRingElem<C>>
GenPolynomial<GenPolynomial<C>>substituteFromAlgebraicCoefficients(GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<AlgebraicNumber<C>> A, long k)
From AlgebraicNumber coefficients.static <C extends GcdRingElem<C>>
GenPolynomial<C>substituteKronecker(GenPolynomial<C> A)
Kronecker substitution.static <C extends GcdRingElem<C>>
GenPolynomial<C>substituteKronecker(GenPolynomial<C> A, long d)
Kronecker substitution.static <C extends GcdRingElem<C>>
java.util.List<GenPolynomial<C>>substituteKronecker(java.util.List<GenPolynomial<C>> A, int d)
Kronecker substitution.
-
-
-
Constructor Detail
-
PolyUfdUtil
public PolyUfdUtil()
-
-
Method Detail
-
derivative
public static <C extends GcdRingElem<C>> Quotient<C> derivative(Quotient<C> r)
Derivation of a univariate rational function.- Parameters:
r
- rational function- Returns:
- dr/dx
-
derivative
public static <C extends GcdRingElem<C>> Quotient<C> derivative(Quotient<C> Q, int r)
Polynomial quotient partial derivative variable r.- Type Parameters:
C
- coefficient type.- Parameters:
Q
- Quotient.r
- variable for partial deriviate.- Returns:
- dq/dx_r = derivative(Q,r).
-
exteriorDerivativeQuot
public static <C extends GcdRingElem<C>> GenExteriorPolynomial<Quotient<C>> exteriorDerivativeQuot(GenExteriorPolynomial<Quotient<C>> P)
GenExteriorPolynomial over polynomial quotient exterior derivative.- Parameters:
P
- GenExteriorPolynomial<Quotient>.- Returns:
- exteriorDerivative(P).
-
evaluateMain
public static <C extends GcdRingElem<C>> C evaluateMain(RingFactory<C> cfac, Quotient<C> A, C a)
Evaluate at main variable.- Type Parameters:
C
- coefficient type.- Parameters:
cfac
- coefficient polynomial ring factory.A
- polynomial quotient to be evaluated.a
- value to evaluate at.- Returns:
- A( x_1, ..., x_{n-1}, a ).
-
evaluateAll
public static <C extends GcdRingElem<C>> C evaluateAll(RingFactory<C> cfac, Quotient<C> A, java.util.List<C> a)
Evaluate all variables.- Type Parameters:
C
- coefficient type.- Parameters:
cfac
- coefficient ring factory.A
- polynomial quotient to be evaluated.a
- = (a_1, a_2, ..., a_n) a tuple of values to evaluate at.- Returns:
- A(a_1, a_2, ..., a_n).
-
approximantOfPade
public static <C extends GcdRingElem<C>> Quotient<C> approximantOfPade(UnivPowerSeriesRing<C> upr, TaylorFunction<C> f, C a, int m, int n)
Pade approximant [m/n] of function f. Computed using Taylor power series expansion of f.- Parameters:
upr
- univariate power series ring.f
- function.a
- expansion point.m
- degree of approximant numerator.n
- degree of approximant denominator.- Returns:
- Pade approximation of f.
-
agcd
public static <C extends GcdRingElem<C>> GenPolynomial<C>[] agcd(GenPolynomial<C> R, GenPolynomial<C> S, int n)
GenPolynomial approximate common divisor. Only for univariate polynomials over fields.- Parameters:
R
- GenPolynomial.S
- GenPolynomial.n
- maximal degree of a.- Returns:
- [ agcd(R,S), a ] with a*R + b*S = agcd(R,S) and deg(a) ≤ n.
-
factors
public static <C extends GcdRingElem<C>> java.util.SortedMap<Quotient<C>,java.lang.Long> factors(Quotient<C> A)
Factors of Quotient rational function.- Parameters:
A
- rational function to be factored.- Returns:
- list of irreducible rational function parts.
-
isFactorization
public static <C extends GcdRingElem<C>> boolean isFactorization(Quotient<C> P, java.util.SortedMap<Quotient<C>,java.lang.Long> F)
Quotient is (squarefree) factorization.- Parameters:
P
- Quotient.F
- = [p_1 -> e_1, ..., p_k -> e_k].- Returns:
- true if P = prod_{i=1,...,k} p_i**e_i, else false.
-
integralFromQuotientCoefficients
public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> integralFromQuotientCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<Quotient<C>> A)
Integral polynomial from rational function coefficients. Represent as polynomial with integral polynomial coefficients by multiplication with the lcm of the numerators of the rational function coefficients.- Parameters:
fac
- result polynomial factory.A
- polynomial with rational function coefficients to be converted.- Returns:
- polynomial with integral polynomial coefficients.
-
integralFromQuotientCoefficients
public static <C extends GcdRingElem<C>> java.util.List<GenPolynomial<GenPolynomial<C>>> integralFromQuotientCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, java.util.Collection<GenPolynomial<Quotient<C>>> L)
Integral polynomial from rational function coefficients. Represent as polynomial with integral polynomial coefficients by multiplication with the lcm of the numerators of the rational function coefficients.- Parameters:
fac
- result polynomial factory.L
- list of polynomial with rational function coefficients to be converted.- Returns:
- list of polynomials with integral polynomial coefficients.
-
quotientFromIntegralCoefficients
public static <C extends GcdRingElem<C>> GenPolynomial<Quotient<C>> quotientFromIntegralCoefficients(GenPolynomialRing<Quotient<C>> fac, GenPolynomial<GenPolynomial<C>> A)
Rational function from integral polynomial coefficients. Represent as polynomial with type Quotientcoefficients. - Parameters:
fac
- result polynomial factory.A
- polynomial with integral polynomial coefficients to be converted.- Returns:
- polynomial with type Quotient
coefficients.
-
quotientFromIntegralCoefficients
public static <C extends GcdRingElem<C>> java.util.List<GenPolynomial<Quotient<C>>> quotientFromIntegralCoefficients(GenPolynomialRing<Quotient<C>> fac, java.util.Collection<GenPolynomial<GenPolynomial<C>>> L)
Rational function from integral polynomial coefficients. Represent as polynomial with type Quotientcoefficients. - Parameters:
fac
- result polynomial factory.L
- list of polynomials with integral polynomial coefficients to be converted.- Returns:
- list of polynomials with type Quotient
coefficients.
-
fromIntegerCoefficients
public static <C extends RingElem<C>> GenPolynomial<GenPolynomial<C>> fromIntegerCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, GenPolynomial<GenPolynomial<BigInteger>> A)
From BigInteger coefficients. Represent as polynomial with type GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.- Parameters:
fac
- result polynomial factory.A
- polynomial with GenPolynomial<BigInteger> coefficients to be converted.- Returns:
- polynomial with type GenPolynomial<C> coefficients.
-
fromIntegerCoefficients
public static <C extends RingElem<C>> java.util.List<GenPolynomial<GenPolynomial<C>>> fromIntegerCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, java.util.List<GenPolynomial<GenPolynomial<BigInteger>>> L)
From BigInteger coefficients. Represent as polynomial with type GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.- Parameters:
fac
- result polynomial factory.L
- polynomial list with GenPolynomial<BigInteger> coefficients to be converted.- Returns:
- polynomial list with polynomials with type GenPolynomial<C> coefficients.
-
integerFromRationalCoefficients
public static GenPolynomial<GenPolynomial<BigInteger>> integerFromRationalCoefficients(GenPolynomialRing<GenPolynomial<BigInteger>> fac, GenPolynomial<GenPolynomial<BigRational>> A)
BigInteger from BigRational coefficients. Represent as polynomial with type GenPolynomial<BigInteger> coefficients.- Parameters:
fac
- result polynomial factory.A
- polynomial with GenPolynomial<BigRational> coefficients to be converted.- Returns:
- polynomial with type GenPolynomial<BigInteger> coefficients.
-
integerFromRationalCoefficients
public static java.util.List<GenPolynomial<GenPolynomial<BigInteger>>> integerFromRationalCoefficients(GenPolynomialRing<GenPolynomial<BigInteger>> fac, java.util.List<GenPolynomial<GenPolynomial<BigRational>>> L)
BigInteger from BigRational coefficients. Represent as polynomial with type GenPolynomial<BigInteger> coefficients.- Parameters:
fac
- result polynomial factory.L
- polynomial list with GenPolynomial<BigRational> coefficients to be converted.- Returns:
- polynomial list with polynomials with type GenPolynomial<BigInteger> coefficients.
-
introduceLowerVariable
public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> introduceLowerVariable(GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<C> A)
Introduce lower variable. Represent as polynomial with type GenPolynomial<C> coefficients.- Parameters:
rfac
- result polynomial factory.A
- polynomial to be extended.- Returns:
- polynomial with type GenPolynomial<C> coefficients.
-
substituteFromAlgebraicCoefficients
public static <C extends GcdRingElem<C>> GenPolynomial<GenPolynomial<C>> substituteFromAlgebraicCoefficients(GenPolynomialRing<GenPolynomial<C>> rfac, GenPolynomial<AlgebraicNumber<C>> A, long k)
From AlgebraicNumber coefficients. Represent as polynomial with type GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.- Parameters:
rfac
- result polynomial factory.A
- polynomial with AlgebraicNumber coefficients to be converted.k
- for (y-k x) substitution.- Returns:
- polynomial with type GenPolynomial<C> coefficients.
-
substituteConvertToAlgebraicCoefficients
public static <C extends GcdRingElem<C>> GenPolynomial<AlgebraicNumber<C>> substituteConvertToAlgebraicCoefficients(GenPolynomialRing<AlgebraicNumber<C>> pfac, GenPolynomial<C> A, long k)
Convert to AlgebraicNumber coefficients. Represent as polynomial with AlgebraicNumbercoefficients, C is e.g. ModInteger or BigRational. - Parameters:
pfac
- result polynomial factory.A
- polynomial with GenPolynomial<BigInteger> coefficients to be converted.k
- for (y-k x) substitution.- Returns:
- polynomial with AlgebraicNumber<C> coefficients.
-
norm
public static <C extends GcdRingElem<C>> GenPolynomial<C> norm(GenPolynomial<AlgebraicNumber<C>> A, long k)
Norm of a polynomial with AlgebraicNumber coefficients.- Parameters:
A
- uni or multivariate polynomial from GenPolynomial<AlgebraicNumber<C>>.k
- for (y - k x) substitution.- Returns:
- norm(A) = res_x(A(x,y),m(x)) in GenPolynomialRing<C>.
-
norm
public static <C extends GcdRingElem<C>> GenPolynomial<C> norm(GenPolynomial<AlgebraicNumber<C>> A)
Norm of a polynomial with AlgebraicNumber coefficients.- Parameters:
A
- polynomial from GenPolynomial<AlgebraicNumber<C>>.- Returns:
- norm(A) = resultant_x( A(x,y), m(x) ) in K[y].
-
ensureFieldProperty
public static <C extends GcdRingElem<C>> void ensureFieldProperty(AlgebraicNumberRing<C> afac)
Ensure that the field property is determined. Checks if modul is irreducible and modifies the algebraic number ring.- Parameters:
afac
- algebraic number ring.
-
randomIrreduciblePolynomial
public static <C extends GcdRingElem<C>> GenPolynomial<C> randomIrreduciblePolynomial(RingFactory<C> cfac, int degree)
Construct a random irreducible univariate polynomial of degree d.- Parameters:
cfac
- coefficient polynomial ring.degree
- of random polynomial.- Returns:
- irreducible univariate polynomial.
-
randomIrreduciblePolynomial
public static <C extends GcdRingElem<C>> GenPolynomial<C> randomIrreduciblePolynomial(GenPolynomialRing<C> ring, int degree)
Construct a random irreducible univariate polynomial of degree d.- Parameters:
ring
- coefficient ring.degree
- of random polynomial.- Returns:
- irreducible univariate polynomial.
-
algebraicNumberField
public static <C extends GcdRingElem<C>> AlgebraicNumberRing<C> algebraicNumberField(RingFactory<C> cfac, int degree)
Construct an algebraic number field of degree d. Uses a random irreducible polynomial of degree d as modulus of the algebraic number ring.- Parameters:
cfac
- coefficient ring.degree
- of random polynomial.- Returns:
- algebraic number field.
-
algebraicNumberField
public static <C extends GcdRingElem<C>> AlgebraicNumberRing<C> algebraicNumberField(GenPolynomialRing<C> ring, int degree)
Construct an algebraic number field of degree d. Uses a random irreducible polynomial of degree d as modulus of the algebraic number ring.- Parameters:
ring
- coefficient polynomial ring.degree
- of random polynomial.- Returns:
- algebraic number field.
-
constructQmatrix
public static <C extends GcdRingElem<C>> java.util.ArrayList<java.util.ArrayList<C>> constructQmatrix(GenPolynomial<C> A)
Construct Berlekamp Q matrix.- Parameters:
A
- univariate modular polynomial.- Returns:
- Q matrix.
-
evaluationPoints
public static <C extends GcdRingElem<C>> EvalPoints<C> evaluationPoints(GenPolynomial<C> A)
Polynomial suitable evaluation points. deg(B) = deg(A(x_1,...)) and B is also squarefree.- Parameters:
A
- squarefree polynomial in r variables.- Returns:
- L list of evaluation points and a squarefree univariate Polynomial B = A(x_1,L_1,...L_{r-2}).
- See Also:
- "sacring.SACPFAC.mi#IPCEVP from SAC2/MAS"
-
substituteKronecker
public static <C extends GcdRingElem<C>> GenPolynomial<C> substituteKronecker(GenPolynomial<C> A)
Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a univariate polynomial.- Parameters:
A
- polynomial to be converted.- Returns:
- a univariate polynomial.
-
substituteKronecker
public static <C extends GcdRingElem<C>> GenPolynomial<C> substituteKronecker(GenPolynomial<C> A, long d)
Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a univariate polynomial.- Parameters:
A
- polynomial to be converted.- Returns:
- a univariate polynomial.
-
substituteKronecker
public static <C extends GcdRingElem<C>> java.util.List<GenPolynomial<C>> substituteKronecker(java.util.List<GenPolynomial<C>> A, int d)
Kronecker substitution. Substitute x_i by x**d**(i-1) to construct univariate polynomials.- Parameters:
A
- list of polynomials to be converted.- Returns:
- a list of univariate polynomials.
-
backSubstituteKronecker
public static <C extends GcdRingElem<C>> GenPolynomial<C> backSubstituteKronecker(GenPolynomialRing<C> fac, GenPolynomial<C> A, long d)
Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct a multivariate polynomial.- Parameters:
A
- polynomial to be converted.fac
- result polynomial factory.- Returns:
- a multivariate polynomial.
-
backSubstituteKronecker
public static <C extends GcdRingElem<C>> java.util.List<GenPolynomial<C>> backSubstituteKronecker(GenPolynomialRing<C> fac, java.util.List<GenPolynomial<C>> A, long d)
Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct multivariate polynomials.- Parameters:
A
- list of polynomials to be converted.fac
- result polynomial factory.- Returns:
- a list of multivariate polynomials.
-
-