Package edu.jas.ufd
Class PolyUfdUtil
java.lang.Object
edu.jas.ufd.PolyUfdUtil
Polynomial ufd utilities. For example conversion between different
representations and Kronecker substitution.
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic <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>>
List<GenPolynomial<C>> backSubstituteKronecker
(GenPolynomialRing<C> fac, List<GenPolynomial<C>> A, long d) Kronecker back substitution.static <C extends GcdRingElem<C>>
ArrayList<ArrayList<C>> 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, 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> Polynomial suitable evaluation points.static <C extends GcdRingElem<C>>
GenExteriorPolynomial<Quotient<C>> GenExteriorPolynomial over polynomial quotient exterior derivative.static <C extends GcdRingElem<C>>
SortedMap<Quotient<C>, Long> 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>>
List<GenPolynomial<GenPolynomial<C>>> fromIntegerCoefficients
(GenPolynomialRing<GenPolynomial<C>> fac, 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 List
<GenPolynomial<GenPolynomial<BigInteger>>> integerFromRationalCoefficients
(GenPolynomialRing<GenPolynomial<BigInteger>> fac, 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>>
List<GenPolynomial<GenPolynomial<C>>> integralFromQuotientCoefficients
(GenPolynomialRing<GenPolynomial<C>> fac, 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, SortedMap<Quotient<C>, 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>>
List<GenPolynomial<Quotient<C>>> quotientFromIntegralCoefficients
(GenPolynomialRing<Quotient<C>> fac, 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> Kronecker substitution.static <C extends GcdRingElem<C>>
GenPolynomial<C> substituteKronecker
(GenPolynomial<C> A, long d) Kronecker substitution.static <C extends GcdRingElem<C>>
List<GenPolynomial<C>> substituteKronecker
(List<GenPolynomial<C>> A, int d) Kronecker substitution.
-
Field Details
-
logger
private static final org.apache.logging.log4j.Logger logger -
debug
private static final boolean debug
-
-
Constructor Details
-
PolyUfdUtil
public PolyUfdUtil()
-
-
Method Details
-
derivative
Derivation of a univariate rational function.- Parameters:
r
- rational function- Returns:
- dr/dx
-
derivative
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
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, 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
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, SortedMap<Quotient<C>, 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>> List<GenPolynomial<GenPolynomial<C>>> integralFromQuotientCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, 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>> List<GenPolynomial<Quotient<C>>> quotientFromIntegralCoefficients(GenPolynomialRing<Quotient<C>> fac, 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>> List<GenPolynomial<GenPolynomial<C>>> fromIntegerCoefficients(GenPolynomialRing<GenPolynomial<C>> fac, 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 List<GenPolynomial<GenPolynomial<BigInteger>>> integerFromRationalCoefficients(GenPolynomialRing<GenPolynomial<BigInteger>> fac, 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
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
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>> ArrayList<ArrayList<C>> constructQmatrix(GenPolynomial<C> A) Construct Berlekamp Q matrix.- Parameters:
A
- univariate modular polynomial.- Returns:
- Q matrix.
-
evaluationPoints
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:
-
substituteKronecker
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>> List<GenPolynomial<C>> substituteKronecker(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:
fac
- result polynomial factory.A
- polynomial to be converted.- Returns:
- a multivariate polynomial.
-
backSubstituteKronecker
public static <C extends GcdRingElem<C>> List<GenPolynomial<C>> backSubstituteKronecker(GenPolynomialRing<C> fac, List<GenPolynomial<C>> A, long d) Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct multivariate polynomials.- Parameters:
fac
- result polynomial factory.A
- list of polynomials to be converted.- Returns:
- a list of multivariate polynomials.
-