Package edu.jas.ufd

Class PolyUfdUtil

java.lang.Object
edu.jas.ufd.PolyUfdUtil

public class PolyUfdUtil extends Object
Polynomial ufd utilities. For example conversion between different representations and 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

      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, 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>> SortedMap<Quotient<C>,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, 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 Quotient coefficients.
      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 Quotient coefficients.
      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

      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

      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 AlgebraicNumber coefficients, 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>> ArrayList<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>> 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.