Package edu.jas.ufd

Class PolyUfdUtil

  • public class PolyUfdUtil
extends java.lang.Object
    Polynomial ufd utilities. For example conversion between different representations and Kronecker substitution.
    Author:
    Heinz Kredel

    • 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).

      • 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>> 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.

      • 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>> 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.