Class UnivariateGCD


  • public final class UnivariateGCD
    extends Object
    Univariate polynomial GCD.
    Since:
    1.0
    • Method Detail

      • PolynomialGCD

        public static <T extends IUnivariatePolynomial<T>> T PolynomialGCD​(T a,
                                                                           T b)
        Calculates the GCD of two polynomials. Depending on the coefficient ring, the algorithm switches between Half-GCD (polys over finite fields), modular GCD (polys over Z and Q) and subresultant Euclid (other rings).
        Parameters:
        a - the first polynomial
        b - the second polynomial
        Returns:
        GCD of two polynomials
      • PolynomialExtendedGCD

        public static <T extends IUnivariatePolynomial<T>> T[] PolynomialExtendedGCD​(T a,
                                                                                     T b)
        Computes [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b). Half-GCD algorithm is used.
        Parameters:
        a - the polynomial
        b - the polynomial
        Returns:
        array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b) (gcd is monic)
        See Also:
        ExtendedHalfGCD(IUnivariatePolynomial, IUnivariatePolynomial)
      • PolynomialFirstBezoutCoefficient

        public static <T extends IUnivariatePolynomial<T>> T[] PolynomialFirstBezoutCoefficient​(T a,
                                                                                                T b)
        Returns array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)
        Parameters:
        a - the first poly for which the Bezout coefficient is computed
        b - the second poly
        Returns:
        array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)
      • PolynomialGCD

        public static <T extends IUnivariatePolynomial<T>> T PolynomialGCD​(T... polynomials)
        Returns GCD of a list of polynomials.
        Parameters:
        polynomials - a set of polynomials
        Returns:
        GCD of polynomials
      • PolynomialGCD

        public static <T extends IUnivariatePolynomial<T>> T PolynomialGCD​(Iterable<T> polynomials)
        Returns GCD of a list of polynomials.
        Parameters:
        polynomials - a set of polynomials
        Returns:
        GCD of polynomials
      • EuclidGCD

        public static <T extends IUnivariatePolynomial<T>> T EuclidGCD​(T a,
                                                                       T b)
        Returns the GCD calculated with Euclidean algorithm. If coefficient ring of the input is not a field (and thus polynomials does not form an integral ring), ArithmeticException may be thrown in case when some exact divisions are not possible.
        Parameters:
        a - poly
        b - poly
        Returns:
        the GCD (monic if a and b are over field)
      • ExtendedEuclidGCD

        public static <T extends IUnivariatePolynomial<T>> T[] ExtendedEuclidGCD​(T a,
                                                                                 T b)
        Runs extended Euclidean algorithm to compute [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b). If coefficient ring of the input is not a field (and thus polynomials does not form an integral ring), ArithmeticException may be thrown in case when some exact divisions are not possible.
        Parameters:
        a - the polynomial
        b - the polynomial
        Returns:
        array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b)
      • EuclidFirstBezoutCoefficient

        public static <T extends IUnivariatePolynomial<T>> T[] EuclidFirstBezoutCoefficient​(T a,
                                                                                            T b)
        Returns array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)
        Parameters:
        a - the first poly for which the Bezout coefficient is computed
        b - the second poly
        Returns:
        array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)
      • HalfGCD

        public static <T extends IUnivariatePolynomial<T>> T HalfGCD​(T a,
                                                                     T b)
        Half-GCD algorithm. The algorithm automatically switches to Euclidean algorithm for small input. If coefficient ring of the input is not a field (and thus polynomials does not form an integral ring), ArithmeticException may be thrown in case when some exact divisions are not possible.
        Parameters:
        a - poly
        b - poly
        Returns:
        the GCD (monic)
      • ExtendedHalfGCD

        public static <T extends IUnivariatePolynomial<T>> T[] ExtendedHalfGCD​(T a,
                                                                               T b)
        Runs extended Half-GCD algorithm to compute [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b). If coefficient ring of the input is not a field (and thus polynomials does not form an integral ring), ArithmeticException may be thrown in case when some exact divisions are not possible.
        Parameters:
        a - the polynomial
        b - the polynomial
        Returns:
        array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b) (gcd is monic)