Internals of the Polynomial Manipulation Module¶

The implementation of the polynomials module is structured internally in “levels”. There are four levels, called L0, L1, L2 and L3. The levels three and four contain the user-facing functionality and were described in the previous section. This section focuses on levels zero and one.

Level zero provides core polynomial manipulation functionality with C-like, low-level interfaces. Level one wraps this low-level functionality into object oriented structures. These are not the classes seen by the user, but rather classes used internally throughout the polys module.

There is one additional complication in the implementation. This comes from the fact that all polynomial manipulations are relative to a ground domain. For example, when factoring a polynomial like \(x^{10} - 1\), one has to decide what ring the coefficients are supposed to belong to, or less trivially, what coefficients are allowed to appear in the factorization. This choice of coefficients is called a ground domain. Typical choices include the integers \(\mathbb{Z}\), the rational numbers \(\mathbb{Q}\) or various related rings and fields. But it is perfectly legitimate (although in this case uninteresting) to factorize over polynomial rings such as \(k[Y]\), where \(k\) is some fixed field.

Thus the polynomial manipulation algorithms (both complicated ones like factoring, and simpler ones like addition or multiplication) have to rely on other code to manipulate the coefficients. In the polynomial manipulation module, such code is encapsulated in so-called “domains”. A domain is basically a factory object: it takes various representations of data, and converts them into objects with unified interface. Every object created by a domain has to implement the arithmetic operations \(+\), \(-\) and \(\times\). Other operations are accessed through the domain, e.g. as in ZZ.quo(ZZ(4), ZZ(2)).

Note that there is some amount of circularity: the polynomial ring domains use the level one classes, the level one classes use the level zero functions, and level zero functions use domains. It is possible, in principle, but not in the current implementation, to work in rings like \(k[X][Y]\). This would create even more layers. For this reason, working in the isomorphic ring \(k[X, Y]\) is preferred.

Domains¶

Here we document the various implemented ground domains. There are three types: abstract domains, concrete domains, and “implementation domains”. Abstract domains cannot be (usefully) instantiated at all, and just collect together functionality shared by many other domains. Concrete domains are those meant to be instantiated and used in the polynomial manipulation algorithms. In some cases, there are various possible ways to implement the data type the domain provides. For example, depending on what libraries are available on the system, the integers are implemented either using the python built-in integers, or using gmpy. Note that various aliases are created automatically depending on the libraries available. As such e.g. ZZ always refers to the most efficient implementation of the integer ring available.

Abstract Domains¶

class sympy.polys.domains.domain.Domain[source]¶

Represents an abstract domain.

abs(a)[source]¶: Absolute value of a, implies __abs__.

add(a, b)[source]¶: Sum of a and b, implies __add__.

algebraic_field(*extension)[source]¶: Returns an algebraic field, i.e. \(K(\alpha, \ldots)\).

almosteq(a, b, tolerance=None)[source]¶: Check if a and b are almost equal.

characteristic()[source]¶: Return the characteristic of this domain.

cofactors(a, b)[source]¶: Returns GCD and cofactors of a and b.

convert(element, base=None)[source]¶: Convert element to self.dtype.

convert_from(element, base)[source]¶: Convert element to self.dtype given the base domain.

denom(a)[source]¶: Returns denominator of a.

div(a, b)[source]¶: Division of a and b, implies something.

evalf(a, prec=None, **options)[source]¶: Returns numerical approximation of a.

exquo(a, b)[source]¶: Exact quotient of a and b, implies something.

frac_field(*symbols, **kwargs)[source]¶: Returns a fraction field, i.e. \(K(X)\).

from_AlgebraicField(a, K0)[source]¶: Convert an algebraic number to dtype.

from_ComplexField(a, K0)[source]¶: Convert a complex element to dtype.

from_ExpressionDomain(a, K0)[source]¶: Convert a EX object to dtype.

from_FF_gmpy(a, K0)[source]¶: Convert ModularInteger(mpz) to dtype.

from_FF_python(a, K0)[source]¶: Convert ModularInteger(int) to dtype.

from_FractionField(a, K0)[source]¶: Convert a rational function to dtype.

from_GlobalPolynomialRing(a, K0)[source]¶: Convert a polynomial to dtype.

from_PolynomialRing(a, K0)[source]¶: Convert a polynomial to dtype.

from_QQ_gmpy(a, K0)[source]¶: Convert a GMPY mpq object to dtype.

from_QQ_python(a, K0)[source]¶: Convert a Python Fraction object to dtype.

from_RealField(a, K0)[source]¶: Convert a real element object to dtype.

from_ZZ_gmpy(a, K0)[source]¶: Convert a GMPY mpz object to dtype.

from_ZZ_python(a, K0)[source]¶: Convert a Python int object to dtype.

from_sympy(a)[source]¶: Convert a SymPy object to dtype.

gcd(a, b)[source]¶: Returns GCD of a and b.

gcdex(a, b)[source]¶: Extended GCD of a and b.

get_exact()[source]¶: Returns an exact domain associated with self.

get_field()[source]¶: Returns a field associated with self.

get_ring()[source]¶: Returns a ring associated with self.

half_gcdex(a, b)[source]¶: Half extended GCD of a and b.

inject(*symbols)[source]¶: Inject generators into this domain.

invert(a, b)[source]¶: Returns inversion of a mod b, implies something.

is_negative(a)[source]¶: Returns True if a is negative.

is_nonnegative(a)[source]¶: Returns True if a is non-negative.

is_nonpositive(a)[source]¶: Returns True if a is non-positive.

is_one(a)[source]¶: Returns True if a is one.

is_positive(a)[source]¶: Returns True if a is positive.

is_zero(a)[source]¶: Returns True if a is zero.

lcm(a, b)[source]¶: Returns LCM of a and b.

log(a, b)[source]¶: Returns b-base logarithm of a.

map(seq)[source]¶: Rersively apply self to all elements of seq.

mul(a, b)[source]¶: Product of a and b, implies __mul__.

n(a, prec=None, **options)[source]¶: Returns numerical approximation of a.

neg(a)[source]¶: Returns a negated, implies __neg__.

numer(a)[source]¶: Returns numerator of a.

of_type(element)[source]¶: Check if a is of type dtype.

old_frac_field(*symbols, **kwargs)[source]¶: Returns a fraction field, i.e. \(K(X)\).

old_poly_ring(*symbols, **kwargs)[source]¶: Returns a polynomial ring, i.e. \(K[X]\).

poly_ring(*symbols, **kwargs)[source]¶: Returns a polynomial ring, i.e. \(K[X]\).

pos(a)[source]¶: Returns a positive, implies __pos__.

pow(a, b)[source]¶: Raise a to power b, implies __pow__.

quo(a, b)[source]¶: Quotient of a and b, implies something.

rem(a, b)[source]¶: Remainder of a and b, implies __mod__.

revert(a)[source]¶: Returns a**(-1) if possible.

sqrt(a)[source]¶: Returns square root of a.

sub(a, b)[source]¶: Difference of a and b, implies __sub__.

to_sympy(a)[source]¶: Convert a to a SymPy object.

unify(K1, symbols=None)[source]¶

Construct a minimal domain that contains elements of K0 and K1.

Known domains (from smallest to largest):

GF(p)
ZZ
QQ
RR(prec, tol)
CC(prec, tol)
ALG(a, b, c)
K[x, y, z]
K(x, y, z)
EX

class sympy.polys.domains.field.Field[source]¶

Represents a field domain.

div(a, b)[source]¶: Division of a and b, implies __div__.

exquo(a, b)[source]¶: Exact quotient of a and b, implies __div__.

gcd(a, b)[source]¶

Returns GCD of a and b.

This definition of GCD over fields allows to clear denominators in \(primitive()\).

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy import S, gcd, primitive
>>> from sympy.abc import x

>>> QQ.gcd(QQ(2, 3), QQ(4, 9))
2/9
>>> gcd(S(2)/3, S(4)/9)
2/9
>>> primitive(2*x/3 + S(4)/9)
(2/9, 3*x + 2)

get_field()[source]¶: Returns a field associated with self.

get_ring()[source]¶: Returns a ring associated with self.

lcm(a, b)[source]¶

Returns LCM of a and b.

>>> from sympy.polys.domains import QQ
>>> from sympy import S, lcm

>>> QQ.lcm(QQ(2, 3), QQ(4, 9))
4/3
>>> lcm(S(2)/3, S(4)/9)
4/3

quo(a, b)[source]¶: Quotient of a and b, implies __div__.

rem(a, b)[source]¶: Remainder of a and b, implies nothing.

revert(a)[source]¶: Returns a**(-1) if possible.

class sympy.polys.domains.ring.Ring[source]¶

Represents a ring domain.

denom(a)[source]¶: Returns denominator of \(a\).

div(a, b)[source]¶: Division of a and b, implies __divmod__.

exquo(a, b)[source]¶: Exact quotient of a and b, implies __floordiv__.

free_module(rank)[source]¶

Generate a free module of rank rank over self.

>>> from sympy.abc import x
>>> from sympy import QQ
>>> QQ.old_poly_ring(x).free_module(2)
QQ[x]**2

get_ring()[source]¶: Returns a ring associated with self.

ideal(*gens)[source]¶

Generate an ideal of self.

>>> from sympy.abc import x
>>> from sympy import QQ
>>> QQ.old_poly_ring(x).ideal(x**2)
<x**2>

invert(a, b)[source]¶: Returns inversion of a mod b.

numer(a)[source]¶: Returns numerator of a.

quo(a, b)[source]¶: Quotient of a and b, implies __floordiv__.

quotient_ring(e)[source]¶

Form a quotient ring of self.

Here e can be an ideal or an iterable.

>>> from sympy.abc import x
>>> from sympy import QQ
>>> QQ.old_poly_ring(x).quotient_ring(QQ.old_poly_ring(x).ideal(x**2))
QQ[x]/<x**2>
>>> QQ.old_poly_ring(x).quotient_ring([x**2])
QQ[x]/<x**2>

The division operator has been overloaded for this:

>>> QQ.old_poly_ring(x)/[x**2]
QQ[x]/<x**2>

rem(a, b)[source]¶: Remainder of a and b, implies __mod__.

revert(a)[source]¶: Returns a**(-1) if possible.

class sympy.polys.domains.simpledomain.SimpleDomain[source]¶

Base class for simple domains, e.g. ZZ, QQ.

inject(*gens)[source]¶: Inject generators into this domain.

class sympy.polys.domains.compositedomain.CompositeDomain[source]¶

Base class for composite domains, e.g. ZZ[x], ZZ(X).

inject(*symbols)[source]¶: Inject generators into this domain.

Concrete Domains¶

class sympy.polys.domains.FiniteField(mod, dom=None, symmetric=True)[source]¶

General class for finite fields.

characteristic()[source]¶: Return the characteristic of this domain.

from_FF_gmpy(a, K0=None)[source]¶: Convert ModularInteger(mpz) to dtype.

from_FF_python(a, K0=None)[source]¶: Convert ModularInteger(int) to dtype.

from_QQ_gmpy(a, K0=None)[source]¶: Convert GMPY’s mpq to dtype.

from_QQ_python(a, K0=None)[source]¶: Convert Python’s Fraction to dtype.

from_RealField(a, K0)[source]¶: Convert mpmath’s mpf to dtype.

from_ZZ_gmpy(a, K0=None)[source]¶: Convert GMPY’s mpz to dtype.

from_ZZ_python(a, K0=None)[source]¶: Convert Python’s int to dtype.

from_sympy(a)[source]¶: Convert SymPy’s Integer to SymPy’s Integer.

get_field()[source]¶: Returns a field associated with self.

to_sympy(a)[source]¶: Convert a to a SymPy object.

class sympy.polys.domains.IntegerRing[source]¶

General class for integer rings.

algebraic_field(*extension)[source]¶: Returns an algebraic field, i.e. \(\mathbb{Q}(\alpha, \ldots)\).

from_AlgebraicField(a, K0)[source]¶: Convert a ANP object to dtype.

get_field()[source]¶: Returns a field associated with self.

log(a, b)[source]¶: Returns b-base logarithm of a.

class sympy.polys.domains.PolynomialRing(domain_or_ring, symbols=None, order=None)[source]¶

A class for representing multivariate polynomial rings.

factorial(a)[source]¶: Returns factorial of \(a\).

from_AlgebraicField(a, K0)[source]¶: Convert an algebraic number to dtype.

from_FractionField(a, K0)[source]¶: Convert a rational function to dtype.

from_PolynomialRing(a, K0)[source]¶: Convert a polynomial to dtype.

from_QQ_gmpy(a, K0)[source]¶: Convert a GMPY \(mpq\) object to \(dtype\).

from_QQ_python(a, K0)[source]¶: Convert a Python \(Fraction\) object to \(dtype\).

from_RealField(a, K0)[source]¶: Convert a mpmath \(mpf\) object to \(dtype\).

from_ZZ_gmpy(a, K0)[source]¶: Convert a GMPY \(mpz\) object to \(dtype\).

from_ZZ_python(a, K0)[source]¶: Convert a Python \(int\) object to \(dtype\).

from_sympy(a)[source]¶: Convert SymPy’s expression to \(dtype\).

gcd(a, b)[source]¶: Returns GCD of \(a\) and \(b\).

gcdex(a, b)[source]¶: Extended GCD of \(a\) and \(b\).

get_field()[source]¶: Returns a field associated with \(self\).

is_negative(a)[source]¶: Returns True if \(LC(a)\) is negative.

is_nonnegative(a)[source]¶: Returns True if \(LC(a)\) is non-negative.

is_nonpositive(a)[source]¶: Returns True if \(LC(a)\) is non-positive.

is_positive(a)[source]¶: Returns True if \(LC(a)\) is positive.

lcm(a, b)[source]¶: Returns LCM of \(a\) and \(b\).

to_sympy(a)[source]¶: Convert \(a\) to a SymPy object.

class sympy.polys.domains.RationalField[source]¶

General class for rational fields.

algebraic_field(*extension)[source]¶: Returns an algebraic field, i.e. \(\mathbb{Q}(\alpha, \ldots)\).

from_AlgebraicField(a, K0)[source]¶: Convert a ANP object to dtype.

class sympy.polys.domains.AlgebraicField(dom, *ext)[source]¶

A class for representing algebraic number fields.

algebraic_field(*extension)[source]¶: Returns an algebraic field, i.e. \(\mathbb{Q}(\alpha, \ldots)\).

denom(a)[source]¶: Returns denominator of a.

dtype[source]¶: alias of sympy.polys.polyclasses.ANP

from_QQ_gmpy(a, K0)[source]¶: Convert a GMPY mpq object to dtype.

from_QQ_python(a, K0)[source]¶: Convert a Python Fraction object to dtype.

from_RealField(a, K0)[source]¶: Convert a mpmath mpf object to dtype.

from_ZZ_gmpy(a, K0)[source]¶: Convert a GMPY mpz object to dtype.

from_ZZ_python(a, K0)[source]¶: Convert a Python int object to dtype.

from_sympy(a)[source]¶: Convert SymPy’s expression to dtype.

get_ring()[source]¶: Returns a ring associated with self.

is_negative(a)[source]¶: Returns True if a is negative.

is_nonnegative(a)[source]¶: Returns True if a is non-negative.

is_nonpositive(a)[source]¶: Returns True if a is non-positive.

is_positive(a)[source]¶: Returns True if a is positive.

numer(a)[source]¶: Returns numerator of a.

to_sympy(a)[source]¶: Convert a to a SymPy object.

class sympy.polys.domains.FractionField(domain_or_field, symbols=None, order=None)[source]¶

A class for representing multivariate rational function fields.

denom(a)[source]¶: Returns denominator of a.

factorial(a)[source]¶: Returns factorial of \(a\).

from_AlgebraicField(a, K0)[source]¶: Convert an algebraic number to dtype.

from_FractionField(a, K0)[source]¶: Convert a rational function to dtype.

from_PolynomialRing(a, K0)[source]¶: Convert a polynomial to dtype.

from_QQ_gmpy(a, K0)[source]¶: Convert a GMPY \(mpq\) object to \(dtype\).

from_QQ_python(a, K0)[source]¶: Convert a Python \(Fraction\) object to \(dtype\).

from_RealField(a, K0)[source]¶: Convert a mpmath \(mpf\) object to \(dtype\).

from_ZZ_gmpy(a, K0)[source]¶: Convert a GMPY \(mpz\) object to \(dtype\).

from_ZZ_python(a, K0)[source]¶: Convert a Python \(int\) object to \(dtype\).

from_sympy(a)[source]¶: Convert SymPy’s expression to \(dtype\).

get_ring()[source]¶: Returns a field associated with \(self\).

is_negative(a)[source]¶: Returns True if \(LC(a)\) is negative.

is_nonnegative(a)[source]¶: Returns True if \(LC(a)\) is non-negative.

is_nonpositive(a)[source]¶: Returns True if \(LC(a)\) is non-positive.

is_positive(a)[source]¶: Returns True if \(LC(a)\) is positive.

numer(a)[source]¶: Returns numerator of a.

to_sympy(a)[source]¶: Convert \(a\) to a SymPy object.

class sympy.polys.domains.RealField(prec=53, dps=None, tol=None)[source]¶

Real numbers up to the given precision.

almosteq(a, b, tolerance=None)[source]¶: Check if a and b are almost equal.

from_sympy(expr)[source]¶: Convert SymPy’s number to dtype.

gcd(a, b)[source]¶: Returns GCD of a and b.

get_exact()[source]¶: Returns an exact domain associated with self.

get_ring()[source]¶: Returns a ring associated with self.

lcm(a, b)[source]¶: Returns LCM of a and b.

to_rational(element, limit=True)[source]¶: Convert a real number to rational number.

to_sympy(element)[source]¶: Convert element to SymPy number.

class sympy.polys.domains.ExpressionDomain[source]¶

A class for arbitrary expressions.

class Expression(ex)[source]¶: An arbitrary expression.

denom(a)[source]¶: Returns denominator of a.

dtype[source]¶: alias of sympy.polys.domains.expressiondomain.ExpressionDomain.Expression

from_ExpressionDomain(a, K0)[source]¶: Convert a EX object to dtype.

from_FractionField(a, K0)[source]¶: Convert a DMF object to dtype.

from_PolynomialRing(a, K0)[source]¶: Convert a DMP object to dtype.

from_QQ_gmpy(a, K0)[source]¶: Convert a GMPY mpq object to dtype.

from_QQ_python(a, K0)[source]¶: Convert a Python Fraction object to dtype.

from_RealField(a, K0)[source]¶: Convert a mpmath mpf object to dtype.

from_ZZ_gmpy(a, K0)[source]¶: Convert a GMPY mpz object to dtype.

from_ZZ_python(a, K0)[source]¶: Convert a Python int object to dtype.

from_sympy(a)[source]¶: Convert SymPy’s expression to dtype.

get_field()[source]¶: Returns a field associated with self.

get_ring()[source]¶: Returns a ring associated with self.

is_negative(a)[source]¶: Returns True if a is negative.

is_nonnegative(a)[source]¶: Returns True if a is non-negative.

is_nonpositive(a)[source]¶: Returns True if a is non-positive.

is_positive(a)[source]¶: Returns True if a is positive.

numer(a)[source]¶: Returns numerator of a.

to_sympy(a)[source]¶: Convert a to a SymPy object.

Implementation Domains¶

class sympy.polys.domains.PythonFiniteField(mod, symmetric=True)[source]¶: Finite field based on Python’s integers.

class sympy.polys.domains.GMPYFiniteField(mod, symmetric=True)[source]¶: Finite field based on GMPY integers.

class sympy.polys.domains.PythonIntegerRing[source]¶: Integer ring based on Python’s int type.

class sympy.polys.domains.GMPYIntegerRing[source]¶: Integer ring based on GMPY’s mpz type.

class sympy.polys.domains.PythonRationalField[source]¶: Rational field based on Python rational number type.

class sympy.polys.domains.GMPYRationalField[source]¶: Rational field based on GMPY mpq class.

Level One¶

class sympy.polys.polyclasses.DMP(rep, dom, lev=None, ring=None)[source]¶

Dense Multivariate Polynomials over \(K\).

LC()[source]¶: Returns the leading coefficient of f.

TC()[source]¶: Returns the trailing coefficient of f.

abs()[source]¶: Make all coefficients in f positive.

add(g)[source]¶: Add two multivariate polynomials f and g.

add_ground(c)[source]¶: Add an element of the ground domain to f.

all_coeffs()[source]¶: Returns all coefficients from f.

all_monoms()[source]¶: Returns all monomials from f.

all_terms()[source]¶: Returns all terms from a f.

cancel(g, include=True)[source]¶: Cancel common factors in a rational function f/g.

clear_denoms()[source]¶: Clear denominators, but keep the ground domain.

coeffs(order=None)[source]¶: Returns all non-zero coefficients from f in lex order.

cofactors(g)[source]¶: Returns GCD of f and g and their cofactors.

compose(g)[source]¶: Computes functional composition of f and g.

content()[source]¶: Returns GCD of polynomial coefficients.

convert(dom)[source]¶: Convert the ground domain of f.

count_complex_roots(inf=None, sup=None)[source]¶: Return the number of complex roots of f in [inf, sup].

count_real_roots(inf=None, sup=None)[source]¶: Return the number of real roots of f in [inf, sup].

decompose()[source]¶: Computes functional decomposition of f.

deflate()[source]¶: Reduce degree of \(f\) by mapping \(x_i^m\) to \(y_i\).

degree(j=0)[source]¶: Returns the leading degree of f in x_j.

degree_list()[source]¶: Returns a list of degrees of f.

diff(m=1, j=0)[source]¶: Computes the m-th order derivative of f in x_j.

discriminant()[source]¶: Computes discriminant of f.

div(g)[source]¶: Polynomial division with remainder of f and g.

eject(dom, front=False)[source]¶: Eject selected generators into the ground domain.

eval(a, j=0)[source]¶: Evaluates f at the given point a in x_j.

exclude()[source]¶

Remove useless generators from f.

Returns the removed generators and the new excluded f.

Examples

>>> from sympy.polys.polyclasses import DMP
>>> from sympy.polys.domains import ZZ

>>> DMP([[[ZZ(1)]], [[ZZ(1)], [ZZ(2)]]], ZZ).exclude()
([2], DMP([[1], [1, 2]], ZZ, None))

exquo(g)[source]¶: Computes polynomial exact quotient of f and g.

exquo_ground(c)[source]¶: Exact quotient of f by a an element of the ground domain.

factor_list()[source]¶: Returns a list of irreducible factors of f.

factor_list_include()[source]¶: Returns a list of irreducible factors of f.

classmethod from_dict(rep, lev, dom)[source]¶: Construct and instance of cls from a dict representation.

classmethod from_list(rep, lev, dom)[source]¶: Create an instance of cls given a list of native coefficients.

classmethod from_sympy_list(rep, lev, dom)[source]¶: Create an instance of cls given a list of SymPy coefficients.

gcd(g)[source]¶: Returns polynomial GCD of f and g.

gcdex(g)[source]¶: Extended Euclidean algorithm, if univariate.

gff_list()[source]¶: Computes greatest factorial factorization of f.

half_gcdex(g)[source]¶: Half extended Euclidean algorithm, if univariate.

homogeneous_order()[source]¶: Returns the homogeneous order of f.

homogenize(s)[source]¶: Return homogeneous polynomial of f

inject(front=False)[source]¶: Inject ground domain generators into f.

integrate(m=1, j=0)[source]¶: Computes the m-th order indefinite integral of f in x_j.

intervals(all=False, eps=None, inf=None, sup=None, fast=False, sqf=False)[source]¶: Compute isolating intervals for roots of f.

invert(g)[source]¶: Invert f modulo g, if possible.

property is_cyclotomic¶: Returns True if f is a cyclotomic polynomial.

property is_ground¶: Returns True if f is an element of the ground domain.

property is_homogeneous¶: Returns True if f is a homogeneous polynomial.

property is_irreducible¶: Returns True if f has no factors over its domain.

property is_linear¶: Returns True if f is linear in all its variables.

property is_monic¶: Returns True if the leading coefficient of f is one.

property is_monomial¶: Returns True if f is zero or has only one term.

property is_one¶: Returns True if f is a unit polynomial.

property is_primitive¶: Returns True if the GCD of the coefficients of f is one.

property is_quadratic¶: Returns True if f is quadratic in all its variables.

property is_sqf¶: Returns True if f is a square-free polynomial.

property is_zero¶: Returns True if f is a zero polynomial.

l1_norm()[source]¶: Returns l1 norm of f.

lcm(g)[source]¶: Returns polynomial LCM of f and g.

lift()[source]¶: Convert algebraic coefficients to rationals.

max_norm()[source]¶: Returns maximum norm of f.

monic()[source]¶: Divides all coefficients by LC(f).

monoms(order=None)[source]¶: Returns all non-zero monomials from f in lex order.

mul(g)[source]¶: Multiply two multivariate polynomials f and g.

mul_ground(c)[source]¶: Multiply f by a an element of the ground domain.

neg()[source]¶: Negate all coefficients in f.

norm()[source]¶: Computes Norm(f).

nth(*N)[source]¶: Returns the n-th coefficient of f.

pdiv(g)[source]¶: Polynomial pseudo-division of f and g.

per(rep, dom=None, kill=False, ring=None)[source]¶: Create a DMP out of the given representation.

permute(P)[source]¶

Returns a polynomial in \(K[x_{P(1)}, ..., x_{P(n)}]\).

Examples

>>> from sympy.polys.polyclasses import DMP
>>> from sympy.polys.domains import ZZ

>>> DMP([[[ZZ(2)], [ZZ(1), ZZ(0)]], [[]]], ZZ).permute([1, 0, 2])
DMP([[[2], []], [[1, 0], []]], ZZ, None)

>>> DMP([[[ZZ(2)], [ZZ(1), ZZ(0)]], [[]]], ZZ).permute([1, 2, 0])
DMP([[[1], []], [[2, 0], []]], ZZ, None)

pexquo(g)[source]¶: Polynomial exact pseudo-quotient of f and g.

pow(n)[source]¶: Raise f to a non-negative power n.

pquo(g)[source]¶: Polynomial pseudo-quotient of f and g.

prem(g)[source]¶: Polynomial pseudo-remainder of f and g.

primitive()[source]¶: Returns content and a primitive form of f.

quo(g)[source]¶: Computes polynomial quotient of f and g.

quo_ground(c)[source]¶: Quotient of f by a an element of the ground domain.

refine_root(s, t, eps=None, steps=None, fast=False)[source]¶

Refine an isolating interval to the given precision.

eps should be a rational number.

rem(g)[source]¶: Computes polynomial remainder of f and g.

resultant(g, includePRS=False)[source]¶: Computes resultant of f and g via PRS.

revert(n)[source]¶: Compute f**(-1) mod x**n.

shift(a)[source]¶: Efficiently compute Taylor shift f(x + a).

slice(m, n, j=0)[source]¶: Take a continuous subsequence of terms of f.

sqf_list(all=False)[source]¶: Returns a list of square-free factors of f.

sqf_list_include(all=False)[source]¶: Returns a list of square-free factors of f.

sqf_norm()[source]¶: Computes square-free norm of f.

sqf_part()[source]¶: Computes square-free part of f.

sqr()[source]¶: Square a multivariate polynomial f.

sturm()[source]¶: Computes the Sturm sequence of f.

sub(g)[source]¶: Subtract two multivariate polynomials f and g.

sub_ground(c)[source]¶: Subtract an element of the ground domain from f.

subresultants(g)[source]¶: Computes subresultant PRS sequence of f and g.

terms(order=None)[source]¶: Returns all non-zero terms from f in lex order.

terms_gcd()[source]¶: Remove GCD of terms from the polynomial f.

to_dict(zero=False)[source]¶: Convert f to a dict representation with native coefficients.

to_exact()[source]¶: Make the ground domain exact.

to_field()[source]¶: Make the ground domain a field.

to_list()[source]¶: Convert f to a list representation with native coefficients.

to_ring()[source]¶: Make the ground domain a ring.

to_sympy_dict(zero=False)[source]¶: Convert f to a dict representation with SymPy coefficients.

to_sympy_list()[source]¶: Convert f to a list representation with SymPy coefficients.

to_tuple()[source]¶

Convert f to a tuple representation with native coefficients.

This is needed for hashing.

total_degree()[source]¶: Returns the total degree of f.

transform(p, q)[source]¶: Evaluate functional transformation q**n * f(p/q).

trunc(p)[source]¶: Reduce f modulo a constant p.

unify(g)[source]¶: Unify representations of two multivariate polynomials.

class sympy.polys.polyclasses.DMF(rep, dom, lev=None, ring=None)[source]¶

Dense Multivariate Fractions over \(K\).

add(g)[source]¶: Add two multivariate fractions f and g.

cancel()[source]¶: Remove common factors from f.num and f.den.

denom()[source]¶: Returns the denominator of f.

exquo(g)[source]¶: Computes quotient of fractions f and g.

frac_unify(g)[source]¶: Unify representations of two multivariate fractions.

half_per(rep, kill=False)[source]¶: Create a DMP out of the given representation.

invert(check=True)[source]¶: Computes inverse of a fraction f.

property is_one¶: Returns True if f is a unit fraction.

property is_zero¶: Returns True if f is a zero fraction.

mul(g)[source]¶: Multiply two multivariate fractions f and g.

neg()[source]¶: Negate all coefficients in f.

numer()[source]¶: Returns the numerator of f.

per(num, den, cancel=True, kill=False, ring=None)[source]¶: Create a DMF out of the given representation.

poly_unify(g)[source]¶: Unify a multivariate fraction and a polynomial.

pow(n)[source]¶: Raise f to a non-negative power n.

quo(g)[source]¶: Computes quotient of fractions f and g.

sub(g)[source]¶: Subtract two multivariate fractions f and g.

class sympy.polys.polyclasses.ANP(rep, mod, dom)[source]¶

Dense Algebraic Number Polynomials over a field.

LC()[source]¶: Returns the leading coefficient of f.

TC()[source]¶: Returns the trailing coefficient of f.

property is_ground¶: Returns True if f is an element of the ground domain.

property is_one¶: Returns True if f is a unit algebraic number.

property is_zero¶: Returns True if f is a zero algebraic number.

pow(n)[source]¶: Raise f to a non-negative power n.

to_dict()[source]¶: Convert f to a dict representation with native coefficients.

to_list()[source]¶: Convert f to a list representation with native coefficients.

to_sympy_dict()[source]¶: Convert f to a dict representation with SymPy coefficients.

to_sympy_list()[source]¶: Convert f to a list representation with SymPy coefficients.

to_tuple()[source]¶

Convert f to a tuple representation with native coefficients.

This is needed for hashing.

unify(g)[source]¶: Unify representations of two algebraic numbers.

Level Zero¶

Level zero contains the bulk code of the polynomial manipulation module.

Manipulation of dense, multivariate polynomials¶

These functions can be used to manipulate polynomials in \(K[X_0, \ldots, X_u]\). Functions for manipulating multivariate polynomials in the dense representation have the prefix dmp_. Functions which only apply to univariate polynomials (i.e. \(u = 0\)) have the prefix dup__. The ground domain \(K\) has to be passed explicitly. For many multivariate polynomial manipulation functions also the level \(u\), i.e. the number of generators minus one, has to be passed. (Note that, in many cases, dup_ versions of functions are available, which may be slightly more efficient.)

Basic manipulation:

sympy.polys.densebasic.dmp_LC(f, K)[source]¶

Return leading coefficient of f.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import poly_LC

>>> poly_LC([], ZZ)
0
>>> poly_LC([ZZ(1), ZZ(2), ZZ(3)], ZZ)
1

sympy.polys.densebasic.dmp_TC(f, K)[source]¶

Return trailing coefficient of f.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import poly_TC

>>> poly_TC([], ZZ)
0
>>> poly_TC([ZZ(1), ZZ(2), ZZ(3)], ZZ)
3

sympy.polys.densebasic.dmp_ground_LC(f, u, K)[source]¶

Return the ground leading coefficient.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_ground_LC

>>> f = ZZ.map([[[1], [2, 3]]])

>>> dmp_ground_LC(f, 2, ZZ)
1

sympy.polys.densebasic.dmp_ground_TC(f, u, K)[source]¶

Return the ground trailing coefficient.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_ground_TC

>>> f = ZZ.map([[[1], [2, 3]]])

>>> dmp_ground_TC(f, 2, ZZ)
3

sympy.polys.densebasic.dmp_true_LT(f, u, K)[source]¶

Return the leading term c * x_1**n_1 ... x_k**n_k.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_true_LT

>>> f = ZZ.map([[4], [2, 0], [3, 0, 0]])

>>> dmp_true_LT(f, 1, ZZ)
((2, 0), 4)

sympy.polys.densebasic.dmp_degree(f, u)[source]¶

Return the leading degree of f in x_0 in K[X].

Note that the degree of 0 is negative infinity (the SymPy object -oo).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_degree

>>> dmp_degree([[[]]], 2)
-oo

>>> f = ZZ.map([[2], [1, 2, 3]])

>>> dmp_degree(f, 1)
1

sympy.polys.densebasic.dmp_degree_in(f, j, u)[source]¶

Return the leading degree of f in x_j in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_degree_in

>>> f = ZZ.map([[2], [1, 2, 3]])

>>> dmp_degree_in(f, 0, 1)
1
>>> dmp_degree_in(f, 1, 1)
2

sympy.polys.densebasic.dmp_degree_list(f, u)[source]¶

Return a list of degrees of f in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_degree_list

>>> f = ZZ.map([[1], [1, 2, 3]])

>>> dmp_degree_list(f, 1)
(1, 2)

sympy.polys.densebasic.dmp_strip(f, u)[source]¶

Remove leading zeros from f in K[X].

Examples

>>> from sympy.polys.densebasic import dmp_strip

>>> dmp_strip([[], [0, 1, 2], [1]], 1)
[[0, 1, 2], [1]]

sympy.polys.densebasic.dmp_validate(f, K=None)[source]¶

Return the number of levels in f and recursively strip it.

Examples

>>> from sympy.polys.densebasic import dmp_validate

>>> dmp_validate([[], [0, 1, 2], [1]])
([[1, 2], [1]], 1)

>>> dmp_validate([[1], 1])
Traceback (most recent call last):
...
ValueError: invalid data structure for a multivariate polynomial

sympy.polys.densebasic.dup_reverse(f)[source]¶

Compute x**n * f(1/x), i.e.: reverse f in K[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dup_reverse

>>> f = ZZ.map([1, 2, 3, 0])

>>> dup_reverse(f)
[3, 2, 1]

sympy.polys.densebasic.dmp_copy(f, u)[source]¶

Create a new copy of a polynomial f in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_copy

>>> f = ZZ.map([[1], [1, 2]])

>>> dmp_copy(f, 1)
[[1], [1, 2]]

sympy.polys.densebasic.dmp_to_tuple(f, u)[source]¶

Convert \(f\) into a nested tuple of tuples.

This is needed for hashing. This is similar to dmp_copy().

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_to_tuple

>>> f = ZZ.map([[1], [1, 2]])

>>> dmp_to_tuple(f, 1)
((1,), (1, 2))

sympy.polys.densebasic.dmp_normal(f, u, K)[source]¶

Normalize a multivariate polynomial in the given domain.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_normal

>>> dmp_normal([[], [0, 1.5, 2]], 1, ZZ)
[[1, 2]]

sympy.polys.densebasic.dmp_convert(f, u, K0, K1)[source]¶

Convert the ground domain of f from K0 to K1.

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_convert

>>> R, x = ring("x", ZZ)

>>> dmp_convert([[R(1)], [R(2)]], 1, R.to_domain(), ZZ)
[[1], [2]]
>>> dmp_convert([[ZZ(1)], [ZZ(2)]], 1, ZZ, R.to_domain())
[[1], [2]]

sympy.polys.densebasic.dmp_from_sympy(f, u, K)[source]¶

Convert the ground domain of f from SymPy to K.

Examples

>>> from sympy import S
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_from_sympy

>>> dmp_from_sympy([[S(1)], [S(2)]], 1, ZZ) == [[ZZ(1)], [ZZ(2)]]
True

sympy.polys.densebasic.dmp_nth(f, n, u, K)[source]¶

Return the n-th coefficient of f in K[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_nth

>>> f = ZZ.map([[1], [2], [3]])

>>> dmp_nth(f, 0, 1, ZZ)
[3]
>>> dmp_nth(f, 4, 1, ZZ)
[]

sympy.polys.densebasic.dmp_ground_nth(f, N, u, K)[source]¶

Return the ground n-th coefficient of f in K[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_ground_nth

>>> f = ZZ.map([[1], [2, 3]])

>>> dmp_ground_nth(f, (0, 1), 1, ZZ)
2

sympy.polys.densebasic.dmp_zero_p(f, u)[source]¶

Return True if f is zero in K[X].

Examples

>>> from sympy.polys.densebasic import dmp_zero_p

>>> dmp_zero_p([[[[[]]]]], 4)
True
>>> dmp_zero_p([[[[[1]]]]], 4)
False

sympy.polys.densebasic.dmp_zero(u)[source]¶

Return a multivariate zero.

Examples

>>> from sympy.polys.densebasic import dmp_zero

>>> dmp_zero(4)
[[[[[]]]]]

sympy.polys.densebasic.dmp_one_p(f, u, K)[source]¶

Return True if f is one in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_one_p

>>> dmp_one_p([[[ZZ(1)]]], 2, ZZ)
True

sympy.polys.densebasic.dmp_one(u, K)[source]¶

Return a multivariate one over K.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_one

>>> dmp_one(2, ZZ)
[[[1]]]

sympy.polys.densebasic.dmp_ground_p(f, c, u)[source]¶

Return True if f is constant in K[X].

Examples

>>> from sympy.polys.densebasic import dmp_ground_p

>>> dmp_ground_p([[[3]]], 3, 2)
True
>>> dmp_ground_p([[[4]]], None, 2)
True

sympy.polys.densebasic.dmp_ground(c, u)[source]¶

Return a multivariate constant.

Examples

>>> from sympy.polys.densebasic import dmp_ground

>>> dmp_ground(3, 5)
[[[[[[3]]]]]]
>>> dmp_ground(1, -1)
1

sympy.polys.densebasic.dmp_zeros(n, u, K)[source]¶

Return a list of multivariate zeros.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_zeros

>>> dmp_zeros(3, 2, ZZ)
[[[[]]], [[[]]], [[[]]]]
>>> dmp_zeros(3, -1, ZZ)
[0, 0, 0]

sympy.polys.densebasic.dmp_grounds(c, n, u)[source]¶

Return a list of multivariate constants.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_grounds

>>> dmp_grounds(ZZ(4), 3, 2)
[[[[4]]], [[[4]]], [[[4]]]]
>>> dmp_grounds(ZZ(4), 3, -1)
[4, 4, 4]

sympy.polys.densebasic.dmp_negative_p(f, u, K)[source]¶

Return True if LC(f) is negative.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_negative_p

>>> dmp_negative_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ)
False
>>> dmp_negative_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ)
True

sympy.polys.densebasic.dmp_positive_p(f, u, K)[source]¶

Return True if LC(f) is positive.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_positive_p

>>> dmp_positive_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ)
True
>>> dmp_positive_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ)
False

sympy.polys.densebasic.dmp_from_dict(f, u, K)[source]¶

Create a K[X] polynomial from a dict.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_from_dict

>>> dmp_from_dict({(0, 0): ZZ(3), (0, 1): ZZ(2), (2, 1): ZZ(1)}, 1, ZZ)
[[1, 0], [], [2, 3]]
>>> dmp_from_dict({}, 0, ZZ)
[]

sympy.polys.densebasic.dmp_to_dict(f, u, K=None, zero=False)[source]¶

Convert a K[X] polynomial to a dict``.

Examples

>>> from sympy.polys.densebasic import dmp_to_dict

>>> dmp_to_dict([[1, 0], [], [2, 3]], 1)
{(0, 0): 3, (0, 1): 2, (2, 1): 1}
>>> dmp_to_dict([], 0)
{}

sympy.polys.densebasic.dmp_swap(f, i, j, u, K)[source]¶

Transform K[..x_i..x_j..] to K[..x_j..x_i..].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_swap

>>> f = ZZ.map([[[2], [1, 0]], []])

>>> dmp_swap(f, 0, 1, 2, ZZ)
[[[2], []], [[1, 0], []]]
>>> dmp_swap(f, 1, 2, 2, ZZ)
[[[1], [2, 0]], [[]]]
>>> dmp_swap(f, 0, 2, 2, ZZ)
[[[1, 0]], [[2, 0], []]]

sympy.polys.densebasic.dmp_permute(f, P, u, K)[source]¶

Return a polynomial in K[x_{P(1)},..,x_{P(n)}].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_permute

>>> f = ZZ.map([[[2], [1, 0]], []])

>>> dmp_permute(f, [1, 0, 2], 2, ZZ)
[[[2], []], [[1, 0], []]]
>>> dmp_permute(f, [1, 2, 0], 2, ZZ)
[[[1], []], [[2, 0], []]]

sympy.polys.densebasic.dmp_nest(f, l, K)[source]¶

Return a multivariate value nested l-levels.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_nest

>>> dmp_nest([[ZZ(1)]], 2, ZZ)
[[[[1]]]]

sympy.polys.densebasic.dmp_raise(f, l, u, K)[source]¶

Return a multivariate polynomial raised l-levels.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_raise

>>> f = ZZ.map([[], [1, 2]])

>>> dmp_raise(f, 2, 1, ZZ)
[[[[]]], [[[1]], [[2]]]]

sympy.polys.densebasic.dmp_deflate(f, u, K)[source]¶

Map x_i**m_i to y_i in a polynomial in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_deflate

>>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])

>>> dmp_deflate(f, 1, ZZ)
((2, 3), [[1, 2], [3, 4]])

sympy.polys.densebasic.dmp_multi_deflate(polys, u, K)[source]¶

Map x_i**m_i to y_i in a set of polynomials in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_multi_deflate

>>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])
>>> g = ZZ.map([[1, 0, 2], [], [3, 0, 4]])

>>> dmp_multi_deflate((f, g), 1, ZZ)
((2, 1), ([[1, 0, 0, 2], [3, 0, 0, 4]], [[1, 0, 2], [3, 0, 4]]))

sympy.polys.densebasic.dmp_inflate(f, M, u, K)[source]¶

Map y_i to x_i**k_i in a polynomial in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_inflate

>>> f = ZZ.map([[1, 2], [3, 4]])

>>> dmp_inflate(f, (2, 3), 1, ZZ)
[[1, 0, 0, 2], [], [3, 0, 0, 4]]

sympy.polys.densebasic.dmp_exclude(f, u, K)[source]¶

Exclude useless levels from f.

Return the levels excluded, the new excluded f, and the new u.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_exclude

>>> f = ZZ.map([[[1]], [[1], [2]]])

>>> dmp_exclude(f, 2, ZZ)
([2], [[1], [1, 2]], 1)

sympy.polys.densebasic.dmp_include(f, J, u, K)[source]¶

Include useless levels in f.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_include

>>> f = ZZ.map([[1], [1, 2]])

>>> dmp_include(f, [2], 1, ZZ)
[[[1]], [[1], [2]]]

sympy.polys.densebasic.dmp_inject(f, u, K, front=False)[source]¶

Convert f from K[X][Y] to K[X,Y].

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_inject

>>> R, x,y = ring("x,y", ZZ)

>>> dmp_inject([R(1), x + 2], 0, R.to_domain())
([[[1]], [[1], [2]]], 2)
>>> dmp_inject([R(1), x + 2], 0, R.to_domain(), front=True)
([[[1]], [[1, 2]]], 2)

sympy.polys.densebasic.dmp_eject(f, u, K, front=False)[source]¶

Convert f from K[X,Y] to K[X][Y].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_eject

>>> dmp_eject([[[1]], [[1], [2]]], 2, ZZ['x', 'y'])
[1, x + 2]

sympy.polys.densebasic.dmp_terms_gcd(f, u, K)[source]¶

Remove GCD of terms from f in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_terms_gcd

>>> f = ZZ.map([[1, 0], [1, 0, 0], [], []])

>>> dmp_terms_gcd(f, 1, ZZ)
((2, 1), [[1], [1, 0]])

sympy.polys.densebasic.dmp_list_terms(f, u, K, order=None)[source]¶

List all non-zero terms from f in the given order order.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_list_terms

>>> f = ZZ.map([[1, 1], [2, 3]])

>>> dmp_list_terms(f, 1, ZZ)
[((1, 1), 1), ((1, 0), 1), ((0, 1), 2), ((0, 0), 3)]
>>> dmp_list_terms(f, 1, ZZ, order='grevlex')
[((1, 1), 1), ((1, 0), 1), ((0, 1), 2), ((0, 0), 3)]

sympy.polys.densebasic.dmp_apply_pairs(f, g, h, args, u, K)[source]¶

Apply h to pairs of coefficients of f and g.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_apply_pairs

>>> h = lambda x, y, z: 2*x + y - z

>>> dmp_apply_pairs([[1], [2, 3]], [[3], [2, 1]], h, (1,), 1, ZZ)
[[4], [5, 6]]

sympy.polys.densebasic.dmp_slice(f, m, n, u, K)[source]¶: Take a continuous subsequence of terms of f in K[X].

sympy.polys.densebasic.dup_random(n, a, b, K)[source]¶

Return a polynomial of degree n with coefficients in [a, b].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dup_random

>>> dup_random(3, -10, 10, ZZ) 
[-2, -8, 9, -4]

Arithmetic operations:

sympy.polys.densearith.dmp_add_term(f, c, i, u, K)[source]¶

Add c(x_2..x_u)*x_0**i to f in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_add_term(x*y + 1, 2, 2)
2*x**2 + x*y + 1

sympy.polys.densearith.dmp_sub_term(f, c, i, u, K)[source]¶

Subtract c(x_2..x_u)*x_0**i from f in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_sub_term(2*x**2 + x*y + 1, 2, 2)
x*y + 1

sympy.polys.densearith.dmp_mul_term(f, c, i, u, K)[source]¶

Multiply f by c(x_2..x_u)*x_0**i in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_mul_term(x**2*y + x, 3*y, 2)
3*x**4*y**2 + 3*x**3*y

sympy.polys.densearith.dmp_add_ground(f, c, u, K)[source]¶

Add an element of the ground domain to f.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_add_ground(x**3 + 2*x**2 + 3*x + 4, ZZ(4))
x**3 + 2*x**2 + 3*x + 8

sympy.polys.densearith.dmp_sub_ground(f, c, u, K)[source]¶

Subtract an element of the ground domain from f.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_sub_ground(x**3 + 2*x**2 + 3*x + 4, ZZ(4))
x**3 + 2*x**2 + 3*x

sympy.polys.densearith.dmp_mul_ground(f, c, u, K)[source]¶

Multiply f by a constant value in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_mul_ground(2*x + 2*y, ZZ(3))
6*x + 6*y

sympy.polys.densearith.dmp_quo_ground(f, c, u, K)[source]¶

Quotient by a constant in K[X].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x,y = ring("x,y", ZZ)
>>> R.dmp_quo_ground(2*x**2*y + 3*x, ZZ(2))
x**2*y + x

>>> R, x,y = ring("x,y", QQ)
>>> R.dmp_quo_ground(2*x**2*y + 3*x, QQ(2))
x**2*y + 3/2*x

sympy.polys.densearith.dmp_exquo_ground(f, c, u, K)[source]¶

Exact quotient by a constant in K[X].

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> R.dmp_exquo_ground(x**2*y + 2*x, QQ(2))
1/2*x**2*y + x

sympy.polys.densearith.dup_lshift(f, n, K)[source]¶

Efficiently multiply f by x**n in K[x].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_lshift(x**2 + 1, 2)
x**4 + x**2

sympy.polys.densearith.dup_rshift(f, n, K)[source]¶

Efficiently divide f by x**n in K[x].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_rshift(x**4 + x**2, 2)
x**2 + 1
>>> R.dup_rshift(x**4 + x**2 + 2, 2)
x**2 + 1

sympy.polys.densearith.dmp_abs(f, u, K)[source]¶

Make all coefficients positive in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_abs(x**2*y - x)
x**2*y + x

sympy.polys.densearith.dmp_neg(f, u, K)[source]¶

Negate a polynomial in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_neg(x**2*y - x)
-x**2*y + x

sympy.polys.densearith.dmp_add(f, g, u, K)[source]¶

Add dense polynomials in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_add(x**2 + y, x**2*y + x)
x**2*y + x**2 + x + y

sympy.polys.densearith.dmp_sub(f, g, u, K)[source]¶

Subtract dense polynomials in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_sub(x**2 + y, x**2*y + x)
-x**2*y + x**2 - x + y

sympy.polys.densearith.dmp_add_mul(f, g, h, u, K)[source]¶

Returns f + g*h where f, g, h are in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_add_mul(x**2 + y, x, x + 2)
2*x**2 + 2*x + y

sympy.polys.densearith.dmp_sub_mul(f, g, h, u, K)[source]¶

Returns f - g*h where f, g, h are in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_sub_mul(x**2 + y, x, x + 2)
-2*x + y

sympy.polys.densearith.dmp_mul(f, g, u, K)[source]¶

Multiply dense polynomials in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_mul(x*y + 1, x)
x**2*y + x

sympy.polys.densearith.dmp_sqr(f, u, K)[source]¶

Square dense polynomials in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_sqr(x**2 + x*y + y**2)
x**4 + 2*x**3*y + 3*x**2*y**2 + 2*x*y**3 + y**4

sympy.polys.densearith.dmp_pow(f, n, u, K)[source]¶

Raise f to the n-th power in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_pow(x*y + 1, 3)
x**3*y**3 + 3*x**2*y**2 + 3*x*y + 1

sympy.polys.densearith.dmp_pdiv(f, g, u, K)[source]¶

Polynomial pseudo-division in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_pdiv(x**2 + x*y, 2*x + 2)
(2*x + 2*y - 2, -4*y + 4)

sympy.polys.densearith.dmp_prem(f, g, u, K)[source]¶

Polynomial pseudo-remainder in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_prem(x**2 + x*y, 2*x + 2)
-4*y + 4

sympy.polys.densearith.dmp_pquo(f, g, u, K)[source]¶

Polynomial exact pseudo-quotient in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x**2 + x*y
>>> g = 2*x + 2*y
>>> h = 2*x + 2

>>> R.dmp_pquo(f, g)
2*x

>>> R.dmp_pquo(f, h)
2*x + 2*y - 2

sympy.polys.densearith.dmp_pexquo(f, g, u, K)[source]¶

Polynomial pseudo-quotient in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x**2 + x*y
>>> g = 2*x + 2*y
>>> h = 2*x + 2

>>> R.dmp_pexquo(f, g)
2*x

>>> R.dmp_pexquo(f, h)
Traceback (most recent call last):
...
ExactQuotientFailed: [[2], [2]] does not divide [[1], [1, 0], []]

sympy.polys.densearith.dmp_rr_div(f, g, u, K)[source]¶

Multivariate division with remainder over a ring.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_rr_div(x**2 + x*y, 2*x + 2)
(0, x**2 + x*y)

sympy.polys.densearith.dmp_ff_div(f, g, u, K)[source]¶

Polynomial division with remainder over a field.

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> R.dmp_ff_div(x**2 + x*y, 2*x + 2)
(1/2*x + 1/2*y - 1/2, -y + 1)

sympy.polys.densearith.dmp_div(f, g, u, K)[source]¶

Polynomial division with remainder in K[X].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x,y = ring("x,y", ZZ)
>>> R.dmp_div(x**2 + x*y, 2*x + 2)
(0, x**2 + x*y)

>>> R, x,y = ring("x,y", QQ)
>>> R.dmp_div(x**2 + x*y, 2*x + 2)
(1/2*x + 1/2*y - 1/2, -y + 1)

sympy.polys.densearith.dmp_rem(f, g, u, K)[source]¶

Returns polynomial remainder in K[X].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x,y = ring("x,y", ZZ)
>>> R.dmp_rem(x**2 + x*y, 2*x + 2)
x**2 + x*y

>>> R, x,y = ring("x,y", QQ)
>>> R.dmp_rem(x**2 + x*y, 2*x + 2)
-y + 1

sympy.polys.densearith.dmp_quo(f, g, u, K)[source]¶

Returns exact polynomial quotient in K[X].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x,y = ring("x,y", ZZ)
>>> R.dmp_quo(x**2 + x*y, 2*x + 2)
0

>>> R, x,y = ring("x,y", QQ)
>>> R.dmp_quo(x**2 + x*y, 2*x + 2)
1/2*x + 1/2*y - 1/2

sympy.polys.densearith.dmp_exquo(f, g, u, K)[source]¶

Returns polynomial quotient in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x**2 + x*y
>>> g = x + y
>>> h = 2*x + 2

>>> R.dmp_exquo(f, g)
x

>>> R.dmp_exquo(f, h)
Traceback (most recent call last):
...
ExactQuotientFailed: [[2], [2]] does not divide [[1], [1, 0], []]

sympy.polys.densearith.dmp_max_norm(f, u, K)[source]¶

Returns maximum norm of a polynomial in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_max_norm(2*x*y - x - 3)
3

sympy.polys.densearith.dmp_l1_norm(f, u, K)[source]¶

Returns l1 norm of a polynomial in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_l1_norm(2*x*y - x - 3)
6

sympy.polys.densearith.dmp_expand(polys, u, K)[source]¶

Multiply together several polynomials in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_expand([x**2 + y**2, x + 1])
x**3 + x**2 + x*y**2 + y**2

Further tools:

sympy.polys.densetools.dmp_integrate(f, m, u, K)[source]¶

Computes the indefinite integral of f in x_0 in K[X].

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> R.dmp_integrate(x + 2*y, 1)
1/2*x**2 + 2*x*y
>>> R.dmp_integrate(x + 2*y, 2)
1/6*x**3 + x**2*y

sympy.polys.densetools.dmp_integrate_in(f, m, j, u, K)[source]¶

Computes the indefinite integral of f in x_j in K[X].

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> R.dmp_integrate_in(x + 2*y, 1, 0)
1/2*x**2 + 2*x*y
>>> R.dmp_integrate_in(x + 2*y, 1, 1)
x*y + y**2

sympy.polys.densetools.dmp_diff(f, m, u, K)[source]¶

m-th order derivative in x_0 of a polynomial in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1

>>> R.dmp_diff(f, 1)
y**2 + 2*y + 3
>>> R.dmp_diff(f, 2)
0

sympy.polys.densetools.dmp_diff_in(f, m, j, u, K)[source]¶

m-th order derivative in x_j of a polynomial in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1

>>> R.dmp_diff_in(f, 1, 0)
y**2 + 2*y + 3
>>> R.dmp_diff_in(f, 1, 1)
2*x*y + 2*x + 4*y + 3

sympy.polys.densetools.dmp_eval(f, a, u, K)[source]¶

Evaluate a polynomial at x_0 = a in K[X] using the Horner scheme.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_eval(2*x*y + 3*x + y + 2, 2)
5*y + 8

sympy.polys.densetools.dmp_eval_in(f, a, j, u, K)[source]¶

Evaluate a polynomial at x_j = a in K[X] using the Horner scheme.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = 2*x*y + 3*x + y + 2

>>> R.dmp_eval_in(f, 2, 0)
5*y + 8
>>> R.dmp_eval_in(f, 2, 1)
7*x + 4

sympy.polys.densetools.dmp_eval_tail(f, A, u, K)[source]¶

Evaluate a polynomial at x_j = a_j, ... in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = 2*x*y + 3*x + y + 2

>>> R.dmp_eval_tail(f, [2])
7*x + 4
>>> R.dmp_eval_tail(f, [2, 2])
18

sympy.polys.densetools.dmp_diff_eval_in(f, m, a, j, u, K)[source]¶

Differentiate and evaluate a polynomial in x_j at a in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1

>>> R.dmp_diff_eval_in(f, 1, 2, 0)
y**2 + 2*y + 3
>>> R.dmp_diff_eval_in(f, 1, 2, 1)
6*x + 11

sympy.polys.densetools.dmp_trunc(f, p, u, K)[source]¶

Reduce a K[X] polynomial modulo a polynomial p in K[Y].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3
>>> g = (y - 1).drop(x)

>>> R.dmp_trunc(f, g)
11*x**2 + 11*x + 5

sympy.polys.densetools.dmp_ground_trunc(f, p, u, K)[source]¶

Reduce a K[X] polynomial modulo a constant p in K.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3

>>> R.dmp_ground_trunc(f, ZZ(3))
-x**2 - x*y - y

sympy.polys.densetools.dup_monic(f, K)[source]¶

Divide all coefficients by LC(f) in K[x].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x = ring("x", ZZ)
>>> R.dup_monic(3*x**2 + 6*x + 9)
x**2 + 2*x + 3

>>> R, x = ring("x", QQ)
>>> R.dup_monic(3*x**2 + 4*x + 2)
x**2 + 4/3*x + 2/3

sympy.polys.densetools.dmp_ground_monic(f, u, K)[source]¶

Divide all coefficients by LC(f) in K[X].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x,y = ring("x,y", ZZ)
>>> f = 3*x**2*y + 6*x**2 + 3*x*y + 9*y + 3

>>> R.dmp_ground_monic(f)
x**2*y + 2*x**2 + x*y + 3*y + 1

>>> R, x,y = ring("x,y", QQ)
>>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3

>>> R.dmp_ground_monic(f)
x**2*y + 8/3*x**2 + 5/3*x*y + 2*x + 2/3*y + 1

sympy.polys.densetools.dup_content(f, K)[source]¶

Compute the GCD of coefficients of f in K[x].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x = ring("x", ZZ)
>>> f = 6*x**2 + 8*x + 12

>>> R.dup_content(f)
2

>>> R, x = ring("x", QQ)
>>> f = 6*x**2 + 8*x + 12

>>> R.dup_content(f)
2

sympy.polys.densetools.dmp_ground_content(f, u, K)[source]¶

Compute the GCD of coefficients of f in K[X].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x,y = ring("x,y", ZZ)
>>> f = 2*x*y + 6*x + 4*y + 12

>>> R.dmp_ground_content(f)
2

>>> R, x,y = ring("x,y", QQ)
>>> f = 2*x*y + 6*x + 4*y + 12

>>> R.dmp_ground_content(f)
2

sympy.polys.densetools.dup_primitive(f, K)[source]¶

Compute content and the primitive form of f in K[x].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x = ring("x", ZZ)
>>> f = 6*x**2 + 8*x + 12

>>> R.dup_primitive(f)
(2, 3*x**2 + 4*x + 6)

>>> R, x = ring("x", QQ)
>>> f = 6*x**2 + 8*x + 12

>>> R.dup_primitive(f)
(2, 3*x**2 + 4*x + 6)

sympy.polys.densetools.dmp_ground_primitive(f, u, K)[source]¶

Compute content and the primitive form of f in K[X].

Examples

>>> from sympy.polys import ring, ZZ, QQ

>>> R, x,y = ring("x,y", ZZ)
>>> f = 2*x*y + 6*x + 4*y + 12

>>> R.dmp_ground_primitive(f)
(2, x*y + 3*x + 2*y + 6)

>>> R, x,y = ring("x,y", QQ)
>>> f = 2*x*y + 6*x + 4*y + 12

>>> R.dmp_ground_primitive(f)
(2, x*y + 3*x + 2*y + 6)

sympy.polys.densetools.dup_extract(f, g, K)[source]¶

Extract common content from a pair of polynomials in K[x].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_extract(6*x**2 + 12*x + 18, 4*x**2 + 8*x + 12)
(2, 3*x**2 + 6*x + 9, 2*x**2 + 4*x + 6)

sympy.polys.densetools.dmp_ground_extract(f, g, u, K)[source]¶

Extract common content from a pair of polynomials in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_ground_extract(6*x*y + 12*x + 18, 4*x*y + 8*x + 12)
(2, 3*x*y + 6*x + 9, 2*x*y + 4*x + 6)

sympy.polys.densetools.dup_real_imag(f, K)[source]¶

Return bivariate polynomials f1 and f2, such that f = f1 + f2*I.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dup_real_imag(x**3 + x**2 + x + 1)
(x**3 + x**2 - 3*x*y**2 + x - y**2 + 1, 3*x**2*y + 2*x*y - y**3 + y)

sympy.polys.densetools.dup_mirror(f, K)[source]¶

Evaluate efficiently the composition f(-x) in K[x].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_mirror(x**3 + 2*x**2 - 4*x + 2)
-x**3 + 2*x**2 + 4*x + 2

sympy.polys.densetools.dup_scale(f, a, K)[source]¶

Evaluate efficiently composition f(a*x) in K[x].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_scale(x**2 - 2*x + 1, ZZ(2))
4*x**2 - 4*x + 1

sympy.polys.densetools.dup_shift(f, a, K)[source]¶

Evaluate efficiently Taylor shift f(x + a) in K[x].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_shift(x**2 - 2*x + 1, ZZ(2))
x**2 + 2*x + 1

sympy.polys.densetools.dup_transform(f, p, q, K)[source]¶

Evaluate functional transformation q**n * f(p/q) in K[x].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_transform(x**2 - 2*x + 1, x**2 + 1, x - 1)
x**4 - 2*x**3 + 5*x**2 - 4*x + 4

sympy.polys.densetools.dmp_compose(f, g, u, K)[source]¶

Evaluate functional composition f(g) in K[X].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_compose(x*y + 2*x + y, y)
y**2 + 3*y

sympy.polys.densetools.dup_decompose(f, K)[source]¶

Computes functional decomposition of f in K[x].

Given a univariate polynomial f with coefficients in a field of characteristic zero, returns list [f_1, f_2, ..., f_n], where:

f = f_1 o f_2 o ... f_n = f_1(f_2(... f_n))

and f_2, ..., f_n are monic and homogeneous polynomials of at least second degree.

Unlike factorization, complete functional decompositions of polynomials are not unique, consider examples:

f o g = f(x + b) o (g - b)
x**n o x**m = x**m o x**n
T_n o T_m = T_m o T_n

where T_n and T_m are Chebyshev polynomials.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_decompose(x**4 - 2*x**3 + x**2)
[x**2, x**2 - x]

References

R602: [Kozen89]

sympy.polys.densetools.dmp_lift(f, u, K)[source]¶

Convert algebraic coefficients to integers in K[X].

Examples

>>> from sympy.polys import ring, QQ
>>> from sympy import I

>>> K = QQ.algebraic_field(I)
>>> R, x = ring("x", K)

>>> f = x**2 + K([QQ(1), QQ(0)])*x + K([QQ(2), QQ(0)])

>>> R.dmp_lift(f)
x**8 + 2*x**6 + 9*x**4 - 8*x**2 + 16

sympy.polys.densetools.dup_sign_variations(f, K)[source]¶

Compute the number of sign variations of f in K[x].

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_sign_variations(x**4 - x**2 - x + 1)
2

sympy.polys.densetools.dmp_clear_denoms(f, u, K0, K1=None, convert=False)[source]¶

Clear denominators, i.e. transform K_0 to K_1.

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> f = QQ(1,2)*x + QQ(1,3)*y + 1

>>> R.dmp_clear_denoms(f, convert=False)
(6, 3*x + 2*y + 6)
>>> R.dmp_clear_denoms(f, convert=True)
(6, 3*x + 2*y + 6)

sympy.polys.densetools.dmp_revert(f, g, u, K)[source]¶

Compute f**(-1) mod x**n using Newton iteration.

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

Manipulation of dense, univariate polynomials with finite field coefficients¶

Functions in this module carry the prefix gf_, referring to the classical name “Galois Fields” for finite fields. Note that many polynomial factorization algorithms work by reduction to the finite field case, so having special implementations for this case is justified both by performance, and by the necessity of certain methods which do not even make sense over general fields.

sympy.polys.galoistools.gf_crt(U, M, K=None)[source]¶

Chinese Remainder Theorem.

Given a set of integer residues u_0,...,u_n and a set of co-prime integer moduli m_0,...,m_n, returns an integer u, such that u = u_i mod m_i for i = ``0,...,n.

Examples

Consider a set of residues U = [49, 76, 65] and a set of moduli M = [99, 97, 95]. Then we have:

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_crt
>>> from sympy.ntheory.modular import solve_congruence

>>> gf_crt([49, 76, 65], [99, 97, 95], ZZ)
639985

This is the correct result because:

>>> [639985 % m for m in [99, 97, 95]]
[49, 76, 65]

Note: this is a low-level routine with no error checking.

Manipulation of sparse, distributed polynomials and vectors¶

Dense representations quickly require infeasible amounts of storage and computation time if the number of variables increases. For this reason, there is code to manipulate polynomials in a sparse representation.

Sparse polynomials are represented as dictionaries.

sympy.polys.rings.ring(symbols, domain, order=LexOrder())[source]¶

Construct a polynomial ring returning (ring, x_1, ..., x_n).

Parameters

symbols : str

Symbol/Expr or sequence of str, Symbol/Expr (non-empty)

domain : Domain or coercible

order : MonomialOrder or coercible, optional, defaults to lex

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.orderings import lex

>>> R, x, y, z = ring("x,y,z", ZZ, lex)
>>> R
Polynomial ring in x, y, z over ZZ with lex order
>>> x + y + z
x + y + z
>>> type(_)
<class 'sympy.polys.rings.PolyElement'>

sympy.polys.rings.xring(symbols, domain, order=LexOrder())[source]¶

Construct a polynomial ring returning (ring, (x_1, ..., x_n)).

Parameters

symbols : str

Symbol/Expr or sequence of str, Symbol/Expr (non-empty)

domain : Domain or coercible

order : MonomialOrder or coercible, optional, defaults to lex

Examples

>>> from sympy.polys.rings import xring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.orderings import lex

>>> R, (x, y, z) = xring("x,y,z", ZZ, lex)
>>> R
Polynomial ring in x, y, z over ZZ with lex order
>>> x + y + z
x + y + z
>>> type(_)
<class 'sympy.polys.rings.PolyElement'>

sympy.polys.rings.vring(symbols, domain, order=LexOrder())[source]¶

Construct a polynomial ring and inject x_1, ..., x_n into the global namespace.

Parameters

symbols : str

Symbol/Expr or sequence of str, Symbol/Expr (non-empty)

domain : Domain or coercible

order : MonomialOrder or coercible, optional, defaults to lex

Examples

>>> from sympy.polys.rings import vring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.orderings import lex

>>> vring("x,y,z", ZZ, lex)
Polynomial ring in x, y, z over ZZ with lex order
>>> x + y + z
x + y + z
>>> type(_)
<class 'sympy.polys.rings.PolyElement'>

sympy.polys.rings.sring(exprs, *symbols, **options)[source]¶

Construct a ring deriving generators and domain from options and input expressions.

Parameters

exprs : Expr or sequence of Expr (sympifiable)

symbols : sequence of Symbol/Expr

options : keyword arguments understood by Options

Examples

>>> from sympy.core import symbols
>>> from sympy.polys.rings import sring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.orderings import lex

>>> x, y, z = symbols("x,y,z")
>>> R, f = sring(x + 2*y + 3*z)
>>> R
Polynomial ring in x, y, z over ZZ with lex order
>>> f
x + 2*y + 3*z
>>> type(_)
<class 'sympy.polys.rings.PolyElement'>

class sympy.polys.rings.PolyRing(symbols, domain, order=LexOrder())[source]¶

Multivariate distributed polynomial ring.

add(*objs)[source]¶

Add a sequence of polynomials or containers of polynomials.

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> R, x = ring("x", ZZ)
>>> R.add([ x**2 + 2*i + 3 for i in range(4) ])
4*x**2 + 24
>>> _.factor_list()
(4, [(x**2 + 6, 1)])

add_gens(symbols)[source]¶: Add the elements of symbols as generators to self

compose(other)[source]¶: Add the generators of other to self

drop(*gens)[source]¶: Remove specified generators from this ring.

drop_to_ground(*gens)[source]¶: Remove specified generators from the ring and inject them into its domain.

index(gen)[source]¶: Compute index of gen in self.gens.

monomial_basis(i)[source]¶: Return the ith-basis element.

mul(*objs)[source]¶

Multiply a sequence of polynomials or containers of polynomials.

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> R, x = ring("x", ZZ)
>>> R.mul([ x**2 + 2*i + 3 for i in range(4) ])
x**8 + 24*x**6 + 206*x**4 + 744*x**2 + 945
>>> _.factor_list()
(1, [(x**2 + 3, 1), (x**2 + 5, 1), (x**2 + 7, 1), (x**2 + 9, 1)])

class sympy.polys.rings.PolyElement[source]¶

Element of multivariate distributed polynomial ring.

almosteq(p2, tolerance=None)[source]¶: Approximate equality test for polynomials.

cancel(g)[source]¶

Cancel common factors in a rational function f/g.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> (2*x**2 - 2).cancel(x**2 - 2*x + 1)
(2*x + 2, x - 1)

coeff(element)[source]¶

Returns the coefficient that stands next to the given monomial.

Parameters: element : PolyElement (with is_monomial = True) or 1

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> _, x, y, z = ring("x,y,z", ZZ)
>>> f = 3*x**2*y - x*y*z + 7*z**3 + 23

>>> f.coeff(x**2*y)
3
>>> f.coeff(x*y)
0
>>> f.coeff(1)
23

coeffs(order=None)[source]¶

Ordered list of polynomial coefficients.

Parameters: order : MonomialOrder or coercible, optional

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.orderings import lex, grlex

>>> _, x, y = ring("x, y", ZZ, lex)
>>> f = x*y**7 + 2*x**2*y**3

>>> f.coeffs()
[2, 1]
>>> f.coeffs(grlex)
[1, 2]

const()[source]¶: Returns the constant coeffcient.

content()[source]¶: Returns GCD of polynomial’s coefficients.

copy()[source]¶

Return a copy of polynomial self.

Polynomials are mutable; if one is interested in preserving a polynomial, and one plans to use inplace operations, one can copy the polynomial. This method makes a shallow copy.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.rings import ring

>>> R, x, y = ring('x, y', ZZ)
>>> p = (x + y)**2
>>> p1 = p.copy()
>>> p2 = p
>>> p[R.zero_monom] = 3
>>> p
x**2 + 2*x*y + y**2 + 3
>>> p1
x**2 + 2*x*y + y**2
>>> p2
x**2 + 2*x*y + y**2 + 3

degree(x=None)[source]¶

The leading degree in x or the main variable.

Note that the degree of 0 is negative infinity (the SymPy object -oo).

degrees()[source]¶

A tuple containing leading degrees in all variables.

Note that the degree of 0 is negative infinity (the SymPy object -oo)

diff(x)[source]¶

Computes partial derivative in x.

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> _, x, y = ring("x,y", ZZ)
>>> p = x + x**2*y**3
>>> p.diff(x)
2*x*y**3 + 1

div(fv)[source]¶

Division algorithm, see [CLO] p64.

fv array of polynomials: return qv, r such that self = sum(fv[i]*qv[i]) + r

All polynomials are required not to be Laurent polynomials.

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> _, x, y = ring('x, y', ZZ)
>>> f = x**3
>>> f0 = x - y**2
>>> f1 = x - y
>>> qv, r = f.div((f0, f1))
>>> qv[0]
x**2 + x*y**2 + y**4
>>> qv[1]
0
>>> r
y**6

imul_num(c)[source]¶

multiply inplace the polynomial p by an element in the coefficient ring, provided p is not one of the generators; else multiply not inplace

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> _, x, y = ring('x, y', ZZ)
>>> p = x + y**2
>>> p1 = p.imul_num(3)
>>> p1
3*x + 3*y**2
>>> p1 is p
True
>>> p = x
>>> p1 = p.imul_num(3)
>>> p1
3*x
>>> p1 is p
False

itercoeffs()[source]¶: Iterator over coefficients of a polynomial.

itermonoms()[source]¶: Iterator over monomials of a polynomial.

iterterms()[source]¶: Iterator over terms of a polynomial.

leading_expv()[source]¶

Leading monomial tuple according to the monomial ordering.

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> _, x, y, z = ring('x, y, z', ZZ)
>>> p = x**4 + x**3*y + x**2*z**2 + z**7
>>> p.leading_expv()
(4, 0, 0)

leading_monom()[source]¶

Leading monomial as a polynomial element.

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> _, x, y = ring('x, y', ZZ)
>>> (3*x*y + y**2).leading_monom()
x*y

leading_term()[source]¶

Leading term as a polynomial element.

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> _, x, y = ring('x, y', ZZ)
>>> (3*x*y + y**2).leading_term()
3*x*y

listcoeffs()[source]¶: Unordered list of polynomial coefficients.

listmonoms()[source]¶: Unordered list of polynomial monomials.

listterms()[source]¶: Unordered list of polynomial terms.

monic()[source]¶: Divides all coefficients by the leading coefficient.

monoms(order=None)[source]¶

Ordered list of polynomial monomials.

Parameters: order : MonomialOrder or coercible, optional

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.orderings import lex, grlex

>>> _, x, y = ring("x, y", ZZ, lex)
>>> f = x*y**7 + 2*x**2*y**3

>>> f.monoms()
[(2, 3), (1, 7)]
>>> f.monoms(grlex)
[(1, 7), (2, 3)]

primitive()[source]¶: Returns content and a primitive polynomial.

square()[source]¶

square of a polynomial

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ

>>> _, x, y = ring('x, y', ZZ)
>>> p = x + y**2
>>> p.square()
x**2 + 2*x*y**2 + y**4

strip_zero()[source]¶: Eliminate monomials with zero coefficient.

tail_degree(x=None)[source]¶

The tail degree in x or the main variable.

Note that the degree of 0 is negative infinity (the SymPy object -oo)

tail_degrees()[source]¶

A tuple containing tail degrees in all variables.

Note that the degree of 0 is negative infinity (the SymPy object -oo)

terms(order=None)[source]¶

Ordered list of polynomial terms.

Parameters: order : MonomialOrder or coercible, optional

Examples

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.orderings import lex, grlex

>>> _, x, y = ring("x, y", ZZ, lex)
>>> f = x*y**7 + 2*x**2*y**3

>>> f.terms()
[((2, 3), 2), ((1, 7), 1)]
>>> f.terms(grlex)
[((1, 7), 1), ((2, 3), 2)]

In commutative algebra, one often studies not only polynomials, but also modules over polynomial rings. The polynomial manipulation module provides rudimentary low-level support for finitely generated free modules. This is mainly used for Groebner basis computations (see there), so manipulation functions are only provided to the extend needed. They carry the prefix sdm_. Note that in examples, the generators of the free module are called \(f_1, f_2, \ldots\).

sympy.polys.distributedmodules.sdm_monomial_mul(M, X)[source]¶

Multiply tuple X representing a monomial of \(K[X]\) into the tuple M representing a monomial of \(F\).

Examples

Multiplying \(xy^3\) into \(x f_1\) yields \(x^2 y^3 f_1\):

>>> from sympy.polys.distributedmodules import sdm_monomial_mul
>>> sdm_monomial_mul((1, 1, 0), (1, 3))
(1, 2, 3)

sympy.polys.distributedmodules.sdm_monomial_deg(M)[source]¶

Return the total degree of M.

Examples

For example, the total degree of \(x^2 y f_5\) is 3:

>>> from sympy.polys.distributedmodules import sdm_monomial_deg
>>> sdm_monomial_deg((5, 2, 1))
3

sympy.polys.distributedmodules.sdm_monomial_divides(A, B)[source]¶

Does there exist a (polynomial) monomial X such that XA = B?

Examples

Positive examples:

In the following examples, the monomial is given in terms of x, y and the generator(s), f_1, f_2 etc. The tuple form of that monomial is used in the call to sdm_monomial_divides. Note: the generator appears last in the expression but first in the tuple and other factors appear in the same order that they appear in the monomial expression.

\(A = f_1\) divides \(B = f_1\)

>>> from sympy.polys.distributedmodules import sdm_monomial_divides
>>> sdm_monomial_divides((1, 0, 0), (1, 0, 0))
True

\(A = f_1\) divides \(B = x^2 y f_1\)

>>> sdm_monomial_divides((1, 0, 0), (1, 2, 1))
True

\(A = xy f_5\) divides \(B = x^2 y f_5\)

>>> sdm_monomial_divides((5, 1, 1), (5, 2, 1))
True

Negative examples:

\(A = f_1\) does not divide \(B = f_2\)

>>> sdm_monomial_divides((1, 0, 0), (2, 0, 0))
False

\(A = x f_1\) does not divide \(B = f_1\)

>>> sdm_monomial_divides((1, 1, 0), (1, 0, 0))
False

\(A = xy^2 f_5\) does not divide \(B = y f_5\)

>>> sdm_monomial_divides((5, 1, 2), (5, 0, 1))
False

sympy.polys.distributedmodules.sdm_LC(f, K)[source]¶: Returns the leading coeffcient of f.

sympy.polys.distributedmodules.sdm_to_dict(f)[source]¶: Make a dictionary from a distributed polynomial.

sympy.polys.distributedmodules.sdm_from_dict(d, O)[source]¶

Create an sdm from a dictionary.

Here O is the monomial order to use.

Examples

>>> from sympy.polys.distributedmodules import sdm_from_dict
>>> from sympy.polys import QQ, lex
>>> dic = {(1, 1, 0): QQ(1), (1, 0, 0): QQ(2), (0, 1, 0): QQ(0)}
>>> sdm_from_dict(dic, lex)
[((1, 1, 0), 1), ((1, 0, 0), 2)]

sympy.polys.distributedmodules.sdm_add(f, g, O, K)[source]¶

Add two module elements f, g.

Addition is done over the ground field K, monomials are ordered according to O.

Examples

All examples use lexicographic order.

\((xy f_1) + (f_2) = f_2 + xy f_1\)

>>> from sympy.polys.distributedmodules import sdm_add
>>> from sympy.polys import lex, QQ
>>> sdm_add([((1, 1, 1), QQ(1))], [((2, 0, 0), QQ(1))], lex, QQ)
[((2, 0, 0), 1), ((1, 1, 1), 1)]

\((xy f_1) + (-xy f_1)\) = 0`

>>> sdm_add([((1, 1, 1), QQ(1))], [((1, 1, 1), QQ(-1))], lex, QQ)
[]

\((f_1) + (2f_1) = 3f_1\)

>>> sdm_add([((1, 0, 0), QQ(1))], [((1, 0, 0), QQ(2))], lex, QQ)
[((1, 0, 0), 3)]

\((yf_1) + (xf_1) = xf_1 + yf_1\)

>>> sdm_add([((1, 0, 1), QQ(1))], [((1, 1, 0), QQ(1))], lex, QQ)
[((1, 1, 0), 1), ((1, 0, 1), 1)]

sympy.polys.distributedmodules.sdm_LM(f)[source]¶

Returns the leading monomial of f.

Only valid if \(f \ne 0\).

Examples

>>> from sympy.polys.distributedmodules import sdm_LM, sdm_from_dict
>>> from sympy.polys import QQ, lex
>>> dic = {(1, 2, 3): QQ(1), (4, 0, 0): QQ(1), (4, 0, 1): QQ(1)}
>>> sdm_LM(sdm_from_dict(dic, lex))
(4, 0, 1)

sympy.polys.distributedmodules.sdm_LT(f)[source]¶

Returns the leading term of f.

Only valid if \(f \ne 0\).

Examples

>>> from sympy.polys.distributedmodules import sdm_LT, sdm_from_dict
>>> from sympy.polys import QQ, lex
>>> dic = {(1, 2, 3): QQ(1), (4, 0, 0): QQ(2), (4, 0, 1): QQ(3)}
>>> sdm_LT(sdm_from_dict(dic, lex))
((4, 0, 1), 3)

sympy.polys.distributedmodules.sdm_mul_term(f, term, O, K)[source]¶

Multiply a distributed module element f by a (polynomial) term term.

Multiplication of coefficients is done over the ground field K, and monomials are ordered according to O.

Examples

\(0 f_1 = 0\)

>>> from sympy.polys.distributedmodules import sdm_mul_term
>>> from sympy.polys import lex, QQ
>>> sdm_mul_term([((1, 0, 0), QQ(1))], ((0, 0), QQ(0)), lex, QQ)
[]

\(x 0 = 0\)

>>> sdm_mul_term([], ((1, 0), QQ(1)), lex, QQ)
[]

\((x) (f_1) = xf_1\)

>>> sdm_mul_term([((1, 0, 0), QQ(1))], ((1, 0), QQ(1)), lex, QQ)
[((1, 1, 0), 1)]

\((2xy) (3x f_1 + 4y f_2) = 8xy^2 f_2 + 6x^2y f_1\)

>>> f = [((2, 0, 1), QQ(4)), ((1, 1, 0), QQ(3))]
>>> sdm_mul_term(f, ((1, 1), QQ(2)), lex, QQ)
[((2, 1, 2), 8), ((1, 2, 1), 6)]

sympy.polys.distributedmodules.sdm_zero()[source]¶: Return the zero module element.

sympy.polys.distributedmodules.sdm_deg(f)[source]¶

Degree of f.

This is the maximum of the degrees of all its monomials. Invalid if f is zero.

Examples

>>> from sympy.polys.distributedmodules import sdm_deg
>>> sdm_deg([((1, 2, 3), 1), ((10, 0, 1), 1), ((2, 3, 4), 4)])
7

sympy.polys.distributedmodules.sdm_from_vector(vec, O, K, **opts)[source]¶

Create an sdm from an iterable of expressions.

Coefficients are created in the ground field K, and terms are ordered according to monomial order O. Named arguments are passed on to the polys conversion code and can be used to specify for example generators.

Examples

>>> from sympy.polys.distributedmodules import sdm_from_vector
>>> from sympy.abc import x, y, z
>>> from sympy.polys import QQ, lex
>>> sdm_from_vector([x**2+y**2, 2*z], lex, QQ)
[((1, 0, 0, 1), 2), ((0, 2, 0, 0), 1), ((0, 0, 2, 0), 1)]

sympy.polys.distributedmodules.sdm_to_vector(f, gens, K, n=None)[source]¶

Convert sdm f into a list of polynomial expressions.

The generators for the polynomial ring are specified via gens. The rank of the module is guessed, or passed via n. The ground field is assumed to be K.

Examples

>>> from sympy.polys.distributedmodules import sdm_to_vector
>>> from sympy.abc import x, y, z
>>> from sympy.polys import QQ, lex
>>> f = [((1, 0, 0, 1), QQ(2)), ((0, 2, 0, 0), QQ(1)), ((0, 0, 2, 0), QQ(1))]
>>> sdm_to_vector(f, [x, y, z], QQ)
[x**2 + y**2, 2*z]

Polynomial factorization algorithms¶

Many variants of Euclid’s algorithm:

Classical remainder sequence¶

Let \(K\) be a field, and consider the ring \(K[X]\) of polynomials in a single indeterminate \(X\) with coefficients in \(K\). Given two elements \(f\) and \(g\) of \(K[X]\) with \(g\neq 0\) there are unique polynomials \(q\) and \(r\) such that \(f = qg + r\) and \(\deg(r) < \deg(g)\) or \(r = 0\). They are denoted by \(\mathrm{quo}(f,g)\) (quotient) and \(\mathrm{rem}(f,g)\) (remainder), so we have the division identity

\[f = \mathrm{quo}(f,g)g + \mathrm{rem}(f,g).\]

It follows that every ideal \(I\) of \(K[X]\) is a principal ideal, generated by any element \(\neq 0\) of minimum degree (assuming \(I\) non-zero). In fact, if \(g\) is such a polynomial and \(f\) is any element of \(I\), \(\mathrm{rem}(f,g)\) belongs to \(I\) as a linear combination of \(f\) and \(g\), hence must be zero; therefore \(f\) is a multiple of \(g\).

Using this result it is possible to find a greatest common divisor (gcd) of any polynomials \(f,g,\ldots\) in \(K[X]\). If \(I\) is the ideal formed by all linear combinations of the given polynomials with coefficients in \(K[X]\), and \(d\) is its generator, then every common divisor of the polynomials also divides \(d\). On the other hand, the given polynomials are multiples of the generator \(d\); hence \(d\) is a gcd of the polynomials, denoted \(\mathrm{gcd}(f,g,\ldots)\).

An algorithm for the gcd of two polynomials \(f\) and \(g\) in \(K[X]\) can now be obtained as follows. By the division identity, \(r = \mathrm{rem}(f,g)\) is in the ideal generated by \(f\) and \(g\), as well as \(f\) is in the ideal generated by \(g\) and \(r\). Hence the ideals generated by the pairs \((f,g)\) and \((g,r)\) are the same. Set \(f_0 = f\), \(f_1 = g\), and define recursively \(f_i = \mathrm{rem}(f_{i-2},f_{i-1})\) for \(i\ge 2\). The recursion ends after a finite number of steps with \(f_{k+1}=0\), since the degrees of the polynomials are strictly decreasing. By the above remark, all the pairs \((f_{i-1},f_i)\) generate the same ideal. In particular, the ideal generated by \(f\) and \(g\) is generated by \(f_k\) alone as \(f_{k+1} = 0\). Hence \(d = f_k\) is a gcd of \(f\) and \(g\).

The sequence of polynomials \(f_0\), \(f_1,\ldots, f_k\) is called the Euclidean polynomial remainder sequence determined by \((f,g)\) because of the analogy with the classical Euclidean algorithm for the gcd of natural numbers.

The algorithm may be extended to obtain an expression for \(d\) in terms of \(f\) and \(g\) by using the full division identities to write recursively each \(f_i\) as a linear combination of \(f\) and \(g\). This leads to an equation

\[d = uf + vg\qquad (u,v \in K[X])\]

analogous to Bézout’s identity in the case of integers.

sympy.polys.euclidtools.dmp_half_gcdex(f, g, u, K)[source]¶

Half extended Euclidean algorithm in \(F[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

sympy.polys.euclidtools.dmp_gcdex(f, g, u, K)[source]¶

Extended Euclidean algorithm in \(F[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

sympy.polys.euclidtools.dmp_invert(f, g, u, K)[source]¶

Compute multiplicative inverse of \(f\) modulo \(g\) in \(F[X]\).

Examples

>>> from sympy.polys import ring, QQ
>>> R, x = ring("x", QQ)

sympy.polys.euclidtools.dmp_euclidean_prs(f, g, u, K)[source]¶

Euclidean polynomial remainder sequence (PRS) in \(K[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

Simplified remainder sequences¶

Assume, as is usual, that the coefficient field \(K\) is the field of fractions of an integral domain \(A\). In this case the coefficients (numerators and denominators) of the polynomials in the Euclidean remainder sequence tend to grow very fast.

If \(A\) is a unique factorization domain, the coefficients may be reduced by cancelling common factors of numerators and denominators. Further reduction is possible noting that a gcd of polynomials in \(K[X]\) is not unique: it may be multiplied by any (non-zero) constant factor.

Any polynomial \(f\) in \(K[X]\) can be simplified by extracting the denominators and common factors of the numerators of its coefficients. This yields the representation \(f = cF\) where \(c\in K\) is the content of \(f\) and \(F\) is a primitive polynomial, i.e., a polynomial in \(A[X]\) with coprime coefficients.

It is possible to start the algorithm by replacing the given polynomials \(f\) and \(g\) with their primitive parts. This will only modify \(\mathrm{rem}(f,g)\) by a constant factor. Replacing it with its primitive part and continuing recursively we obtain all the primitive parts of the polynomials in the Euclidean remainder sequence, including the primitive \(\mathrm{gcd}(f,g)\).

This sequence is the primitive polynomial remainder sequence. It is an example of general polynomial remainder sequences where the computed remainders are modified by constant multipliers (or divisors) in order to simplify the results.

sympy.polys.euclidtools.dmp_primitive_prs(f, g, u, K)[source]¶

Primitive polynomial remainder sequence (PRS) in \(K[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

Subresultant sequence¶

The coefficients of the primitive polynomial sequence do not grow exceedingly, but the computation of the primitive parts requires extra processing effort. Besides, the method only works with fraction fields of unique factorization domains, excluding, for example, the general number fields.

Collins [Collins67] realized that the so-called subresultant polynomials of a pair of polynomials also form a generalized remainder sequence. The coefficients of these polynomials are expressible as determinants in the coefficients of the given polynomials. Hence (the logarithm of) their size only grows linearly. In addition, if the coefficients of the given polynomials are in the subdomain \(A\), so are those of the subresultant polynomials. This means that the subresultant sequence is comparable to the primitive remainder sequence without relying on unique factorization in \(A\).

To see how subresultants are associated with remainder sequences recall that all polynomials \(h\) in the sequence are linear combinations of the given polynomials \(f\) and \(g\)

\[h = uf+vg\]

with polynomials \(u\) and \(v\) in \(K[X]\). Moreover, as is seen from the extended Euclidean algorithm, the degrees of \(u\) and \(v\) are relatively low, with limited growth from step to step.

Let \(n = \deg(f)\), and \(m = \deg(g)\), and assume \(n\ge m\). If \(\deg(h) = j < m\), the coefficients of the powers \(X^k\) (\(k > j\)) in the products \(uf\) and \(vg\) cancel each other. In particular, the products must have the same degree, say, \(l\). Then \(\deg(u) = l - n\) and \(\deg(v) = l - m\) with a total of \(2l -n - m + 2\) coefficients to be determined.

On the other hand, the equality \(h = uf + vg\) implies that \(l - j\) linear combinations of the coefficients are zero, those associated with the powers \(X^i\) (\(j < i \leq l\)), and one has a given non-zero value, namely the leading coefficient of \(h\).

To satisfy these \(l - j + 1\) linear equations the total number of coefficients to be determined cannot be lower than \(l - j + 1\), in general. This leads to the inequality \(l \ge n + m - j - 1\). Taking \(l = n + m - j - 1\), we obtain \(\deg(u) = m - j - 1\) and \(\deg(v) = n - j - 1\).

In the case \(j = 0\) the matrix of the resulting system of linear equations is the Sylvester matrix \(S(f,g)\) associated to \(f\) and \(g\), an \((n+m)\times (n+m)\) matrix with coefficients of \(f\) and \(g\) as entries. Its determinant is the resultant \(\mathrm{res}(f,g)\) of the pair \((f,g)\). It is non-zero if and only if \(f\) and \(g\) are relatively prime.

For any \(j\) in the interval from \(0\) to \(m\) the matrix of the linear system is an \((n+m-2j)\times (n+m-2j)\) submatrix of the Sylvester matrix. Its determinant \(s_j(f,g)\) is called the \(j\) th scalar subresultant of \(f\) and \(g\).

If \(s_j(f,g)\) is not zero, the associated equation \(h = uf + vg\) has a unique solution where \(\deg(h) = j\) and the leading coefficient of \(h\) has any given value; the one with leading coefficient \(s_j(f,g)\) is the \(j\) th subresultant polynomial or, briefly, subresultant of the pair \((f,g)\), and denoted \(S_j(f,g)\). This choice guarantees that the remainining coefficients are also certain subdeterminants of the Sylvester matrix. In particular, if \(f\) and \(g\) are in \(A[X]\), so is \(S_j(f,g)\) as well. This construction of subresultants applies to any \(j\) between \(0\) and \(m\) regardless of the value of \(s_j(f,g)\); if it is zero, then \(\deg(S_j(f,g)) < j\).

The properties of subresultants are as follows. Let \(n_0 = \deg(f)\), \(n_1 = \deg(g)\), \(n_2, \ldots, n_k\) be the decreasing sequence of degrees of polynomials in a remainder sequence. Let \(0 \le j \le n_1\); then

\(s_j(f,g)\ne 0\) if and only if \(j = n_i\) for some \(i\).
\(S_j(f,g)\ne 0\) if and only if \(j = n_i\) or \(j = n_i - 1\) for some \(i\).

Normally, \(n_{i-1} - n_i = 1\) for \(1 < i \le k\). If \(n_{i-1} - n_i > 1\) for some \(i\) (the abnormal case), then \(S_{n_{i-1}-1}(f,g)\) and \(S_{n_i}(f,g)\) are constant multiples of each other. Hence either one could be included in the polynomial remainder sequence. The former is given by smaller determinants, so it is expected to have smaller coefficients.

Collins defined the subresultant remainder sequence by setting

\[f_i = S_{n_{i-1}-1}(f,g) \qquad (2\le i \le k).\]

In the normal case, these are the same as the \(S_{n_i}(f,g)\). He also derived expressions for the constants \(\gamma_i\) in the remainder formulas

\[\gamma_i f_i = \mathrm{rem}(f_{i-2},f_{i-1})\]

in terms of the leading coefficients of \(f_1,\ldots,f_{i-1}\), working in the field \(K\).

Brown and Traub [BrownTraub71] later developed a recursive procedure for computing the coefficients \(\gamma_i\). Their algorithm deals with elements of the domain \(A\) exclusively (assuming \(f,g\in A[X]\)). However, in the abnormal case there was a problem, a division in \(A\) which could only be conjectured to be exact.

This was subsequently justified by Brown [Brown78] who showed that the result of the division is, in fact, a scalar subresultant. More specifically, the constant appearing in the computation of \(f_i\) is \(s_{n_{i-2}}(f,g)\) (Theorem 3). The implication of this discovery is that the scalar subresultants are computed as by-products of the algorithm, all but \(s_{n_k}(f,g)\) which is not needed after finding \(f_{k+1} = 0\). Completing the last step we obtain all non-zero scalar subresultants, including the last one which is the resultant if this does not vanish.

sympy.polys.euclidtools.dmp_inner_subresultants(f, g, u, K)[source]¶

Subresultant PRS algorithm in \(K[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = 3*x**2*y - y**3 - 4
>>> g = x**2 + x*y**3 - 9

>>> a = 3*x*y**4 + y**3 - 27*y + 4
>>> b = -3*y**10 - 12*y**7 + y**6 - 54*y**4 + 8*y**3 + 729*y**2 - 216*y + 16

>>> prs = [f, g, a, b]
>>> sres = [[1], [1], [3, 0, 0, 0, 0], [-3, 0, 0, -12, 1, 0, -54, 8, 729, -216, 16]]

>>> R.dmp_inner_subresultants(f, g) == (prs, sres)
True

sympy.polys.euclidtools.dmp_subresultants(f, g, u, K)[source]¶

Computes subresultant PRS of two polynomials in \(K[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = 3*x**2*y - y**3 - 4
>>> g = x**2 + x*y**3 - 9

>>> a = 3*x*y**4 + y**3 - 27*y + 4
>>> b = -3*y**10 - 12*y**7 + y**6 - 54*y**4 + 8*y**3 + 729*y**2 - 216*y + 16

>>> R.dmp_subresultants(f, g) == [f, g, a, b]
True

sympy.polys.euclidtools.dmp_prs_resultant(f, g, u, K)[source]¶

Resultant algorithm in \(K[X]\) using subresultant PRS.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = 3*x**2*y - y**3 - 4
>>> g = x**2 + x*y**3 - 9

>>> a = 3*x*y**4 + y**3 - 27*y + 4
>>> b = -3*y**10 - 12*y**7 + y**6 - 54*y**4 + 8*y**3 + 729*y**2 - 216*y + 16

>>> res, prs = R.dmp_prs_resultant(f, g)

>>> res == b             # resultant has n-1 variables
False
>>> res == b.drop(x)
True
>>> prs == [f, g, a, b]
True

sympy.polys.euclidtools.dmp_zz_modular_resultant(f, g, p, u, K)[source]¶

Compute resultant of \(f\) and \(g\) modulo a prime \(p\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x + y + 2
>>> g = 2*x*y + x + 3

>>> R.dmp_zz_modular_resultant(f, g, 5)
-2*y**2 + 1

sympy.polys.euclidtools.dmp_zz_collins_resultant(f, g, u, K)[source]¶

Collins’s modular resultant algorithm in \(Z[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x + y + 2
>>> g = 2*x*y + x + 3

>>> R.dmp_zz_collins_resultant(f, g)
-2*y**2 - 5*y + 1

sympy.polys.euclidtools.dmp_qq_collins_resultant(f, g, u, K0)[source]¶

Collins’s modular resultant algorithm in \(Q[X]\).

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> f = QQ(1,2)*x + y + QQ(2,3)
>>> g = 2*x*y + x + 3

>>> R.dmp_qq_collins_resultant(f, g)
-2*y**2 - 7/3*y + 5/6

sympy.polys.euclidtools.dmp_resultant(f, g, u, K, includePRS=False)[source]¶

Computes resultant of two polynomials in \(K[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = 3*x**2*y - y**3 - 4
>>> g = x**2 + x*y**3 - 9

>>> R.dmp_resultant(f, g)
-3*y**10 - 12*y**7 + y**6 - 54*y**4 + 8*y**3 + 729*y**2 - 216*y + 16

sympy.polys.euclidtools.dmp_discriminant(f, u, K)[source]¶

Computes discriminant of a polynomial in \(K[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y,z,t = ring("x,y,z,t", ZZ)

>>> R.dmp_discriminant(x**2*y + x*z + t)
-4*y*t + z**2

sympy.polys.euclidtools.dmp_rr_prs_gcd(f, g, u, K)[source]¶

Computes polynomial GCD using subresultants over a ring.

Returns (h, cff, cfg) such that a = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y

>>> R.dmp_rr_prs_gcd(f, g)
(x + y, x + y, x)

sympy.polys.euclidtools.dmp_ff_prs_gcd(f, g, u, K)[source]¶

Computes polynomial GCD using subresultants over a field.

Returns (h, cff, cfg) such that a = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y, = ring("x,y", QQ)

>>> f = QQ(1,2)*x**2 + x*y + QQ(1,2)*y**2
>>> g = x**2 + x*y

>>> R.dmp_ff_prs_gcd(f, g)
(x + y, 1/2*x + 1/2*y, x)

sympy.polys.euclidtools.dmp_zz_heu_gcd(f, g, u, K)[source]¶

Heuristic polynomial GCD in \(Z[X]\).

Given univariate polynomials \(f\) and \(g\) in \(Z[X]\), returns their GCD and cofactors, i.e. polynomials h, cff and cfg such that:

h = gcd(f, g), cff = quo(f, h) and cfg = quo(g, h)

The algorithm is purely heuristic which means it may fail to compute the GCD. This will be signaled by raising an exception. In this case you will need to switch to another GCD method.

The algorithm computes the polynomial GCD by evaluating polynomials f and g at certain points and computing (fast) integer GCD of those evaluations. The polynomial GCD is recovered from the integer image by interpolation. The evaluation process reduces f and g variable by variable into a large integer. The final step is to verify if the interpolated polynomial is the correct GCD. This gives cofactors of the input polynomials as a side effect.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y

>>> R.dmp_zz_heu_gcd(f, g)
(x + y, x + y, x)

References

R611: [Liao95]

sympy.polys.euclidtools.dmp_qq_heu_gcd(f, g, u, K0)[source]¶

Heuristic polynomial GCD in \(Q[X]\).

Returns (h, cff, cfg) such that a = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

>>> from sympy.polys import ring, QQ
>>> R, x,y, = ring("x,y", QQ)

>>> f = QQ(1,4)*x**2 + x*y + y**2
>>> g = QQ(1,2)*x**2 + x*y

>>> R.dmp_qq_heu_gcd(f, g)
(x + 2*y, 1/4*x + 1/2*y, 1/2*x)

sympy.polys.euclidtools.dmp_inner_gcd(f, g, u, K)[source]¶

Computes polynomial GCD and cofactors of \(f\) and \(g\) in \(K[X]\).

Returns (h, cff, cfg) such that a = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y

>>> R.dmp_inner_gcd(f, g)
(x + y, x + y, x)

sympy.polys.euclidtools.dmp_gcd(f, g, u, K)[source]¶

Computes polynomial GCD of \(f\) and \(g\) in \(K[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y

>>> R.dmp_gcd(f, g)
x + y

sympy.polys.euclidtools.dmp_lcm(f, g, u, K)[source]¶

Computes polynomial LCM of \(f\) and \(g\) in \(K[X]\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y

>>> R.dmp_lcm(f, g)
x**3 + 2*x**2*y + x*y**2

sympy.polys.euclidtools.dmp_content(f, u, K)[source]¶

Returns GCD of multivariate coefficients.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

>>> R.dmp_content(2*x*y + 6*x + 4*y + 12)
2*y + 6

sympy.polys.euclidtools.dmp_primitive(f, u, K)[source]¶

Returns multivariate content and a primitive polynomial.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

>>> R.dmp_primitive(2*x*y + 6*x + 4*y + 12)
(2*y + 6, x + 2)

sympy.polys.euclidtools.dmp_cancel(f, g, u, K, include=True)[source]¶

Cancel common factors in a rational function \(f/g\).

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_cancel(2*x**2 - 2, x**2 - 2*x + 1)
(2*x + 2, x - 1)

Polynomial factorization in characteristic zero:

sympy.polys.factortools.dmp_trial_division(f, factors, u, K)[source]¶: Determine multiplicities of factors for a multivariate polynomial using trial division.

sympy.polys.factortools.dmp_zz_mignotte_bound(f, u, K)[source]¶: Mignotte bound for multivariate polynomials in \(K[X]\).

sympy.polys.factortools.dup_zz_hensel_step(m, f, g, h, s, t, K)[source]¶

One step in Hensel lifting in \(Z[x]\).

Given positive integer \(m\) and \(Z[x]\) polynomials \(f\), \(g\), \(h\), \(s\) and \(t\) such that:

f = g*h (mod m)
s*g + t*h = 1 (mod m)

lc(f) is not a zero divisor (mod m)
lc(h) = 1

deg(f) = deg(g) + deg(h)
deg(s) < deg(h)
deg(t) < deg(g)

returns polynomials \(G\), \(H\), \(S\) and \(T\), such that:

f = G*H (mod m**2)
S*G + T*H = 1 (mod m**2)

References

R612: [Gathen99]

sympy.polys.factortools.dup_zz_hensel_lift(p, f, f_list, l, K)[source]¶

Multifactor Hensel lifting in \(Z[x]\).

Given a prime \(p\), polynomial \(f\) over \(Z[x]\) such that \(lc(f)\) is a unit modulo \(p\), monic pair-wise coprime polynomials \(f_i\) over \(Z[x]\) satisfying:

f = lc(f) f_1 ... f_r (mod p)

and a positive integer \(l\), returns a list of monic polynomials \(F_1\), \(F_2\), …, \(F_r\) satisfying:

f = lc(f) F_1 ... F_r (mod p**l)

F_i = f_i (mod p), i = 1..r

References

R613: [Gathen99]

sympy.polys.factortools.dup_zz_zassenhaus(f, K)[source]¶: Factor primitive square-free polynomials in \(Z[x]\).

sympy.polys.factortools.dup_zz_irreducible_p(f, K)[source]¶: Test irreducibility using Eisenstein’s criterion.

sympy.polys.factortools.dup_cyclotomic_p(f, K, irreducible=False)[source]¶

Efficiently test if f is a cyclotomic polynomial.

Examples

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> f = x**16 + x**14 - x**10 + x**8 - x**6 + x**2 + 1
>>> R.dup_cyclotomic_p(f)
False

>>> g = x**16 + x**14 - x**10 - x**8 - x**6 + x**2 + 1
>>> R.dup_cyclotomic_p(g)
True

sympy.polys.factortools.dup_zz_cyclotomic_poly(n, K)[source]¶: Efficiently generate n-th cyclotomic polynomial.

sympy.polys.factortools.dup_zz_cyclotomic_factor(f, K)[source]¶

Efficiently factor polynomials \(x**n - 1\) and \(x**n + 1\) in \(Z[x]\).

Given a univariate polynomial \(f\) in \(Z[x]\) returns a list of factors of \(f\), provided that \(f\) is in the form \(x**n - 1\) or \(x**n + 1\) for \(n >= 1\). Otherwise returns None.

Factorization is performed using cyclotomic decomposition of \(f\), which makes this method much faster that any other direct factorization approach (e.g. Zassenhaus’s).

References

R614: [Weisstein09]

sympy.polys.factortools.dup_zz_factor_sqf(f, K)[source]¶: Factor square-free (non-primitive) polynomials in \(Z[x]\).

sympy.polys.factortools.dup_zz_factor(f, K)[source]¶

Factor (non square-free) polynomials in \(Z[x]\).

Given a univariate polynomial \(f\) in \(Z[x]\) computes its complete factorization \(f_1, ..., f_n\) into irreducibles over integers:

f = content(f) f_1**k_1 ... f_n**k_n

The factorization is computed by reducing the input polynomial into a primitive square-free polynomial and factoring it using Zassenhaus algorithm. Trial division is used to recover the multiplicities of factors.

The result is returned as a tuple consisting of:

(content(f), [(f_1, k_1), ..., (f_n, k_n))

Examples

Consider the polynomial \(f = 2*x**4 - 2\):

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_zz_factor(2*x**4 - 2)
(2, [(x - 1, 1), (x + 1, 1), (x**2 + 1, 1)])

In result we got the following factorization:

f = 2 (x - 1) (x + 1) (x**2 + 1)

Note that this is a complete factorization over integers, however over Gaussian integers we can factor the last term.

By default, polynomials \(x**n - 1\) and \(x**n + 1\) are factored using cyclotomic decomposition to speedup computations. To disable this behaviour set cyclotomic=False.

References

R615: [Gathen99]

sympy.polys.factortools.dmp_zz_wang_non_divisors(E, cs, ct, K)[source]¶: Wang/EEZ: Compute a set of valid divisors.

sympy.polys.factortools.dmp_zz_wang_test_points(f, T, ct, A, u, K)[source]¶: Wang/EEZ: Test evaluation points for suitability.

sympy.polys.factortools.dmp_zz_wang_lead_coeffs(f, T, cs, E, H, A, u, K)[source]¶: Wang/EEZ: Compute correct leading coefficients.

sympy.polys.factortools.dmp_zz_diophantine(F, c, A, d, p, u, K)[source]¶: Wang/EEZ: Solve multivariate Diophantine equations.

sympy.polys.factortools.dmp_zz_wang_hensel_lifting(f, H, LC, A, p, u, K)[source]¶: Wang/EEZ: Parallel Hensel lifting algorithm.

sympy.polys.factortools.dmp_zz_wang(f, u, K, mod=None, seed=None)[source]¶

Factor primitive square-free polynomials in \(Z[X]\).

Given a multivariate polynomial \(f\) in \(Z[x_1,...,x_n]\), which is primitive and square-free in \(x_1\), computes factorization of \(f\) into irreducibles over integers.

The procedure is based on Wang’s Enhanced Extended Zassenhaus algorithm. The algorithm works by viewing \(f\) as a univariate polynomial in \(Z[x_2,...,x_n][x_1]\), for which an evaluation mapping is computed:

x_2 -> a_2, ..., x_n -> a_n

where \(a_i\), for \(i = 2, ..., n\), are carefully chosen integers. The mapping is used to transform \(f\) into a univariate polynomial in \(Z[x_1]\), which can be factored efficiently using Zassenhaus algorithm. The last step is to lift univariate factors to obtain true multivariate factors. For this purpose a parallel Hensel lifting procedure is used.

The parameter seed is passed to _randint and can be used to seed randint (when an integer) or (for testing purposes) can be a sequence of numbers.

References

R616: [Wang78]
R617: [Geddes92]

sympy.polys.factortools.dmp_zz_factor(f, u, K)[source]¶

Factor (non square-free) polynomials in \(Z[X]\).

Given a multivariate polynomial \(f\) in \(Z[x]\) computes its complete factorization \(f_1, ..., f_n\) into irreducibles over integers:

f = content(f) f_1**k_1 ... f_n**k_n

The factorization is computed by reducing the input polynomial into a primitive square-free polynomial and factoring it using Enhanced Extended Zassenhaus (EEZ) algorithm. Trial division is used to recover the multiplicities of factors.

The result is returned as a tuple consisting of:

(content(f), [(f_1, k_1), ..., (f_n, k_n))

Consider polynomial \(f = 2*(x**2 - y**2)\):

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_zz_factor(2*x**2 - 2*y**2)
(2, [(x - y, 1), (x + y, 1)])

In result we got the following factorization:

f = 2 (x - y) (x + y)

References

R618: [Gathen99]

sympy.polys.factortools.dmp_ext_factor(f, u, K)[source]¶: Factor multivariate polynomials over algebraic number fields.

sympy.polys.factortools.dup_gf_factor(f, K)[source]¶: Factor univariate polynomials over finite fields.

sympy.polys.factortools.dmp_factor_list(f, u, K0)[source]¶: Factor multivariate polynomials into irreducibles in \(K[X]\).

sympy.polys.factortools.dmp_factor_list_include(f, u, K)[source]¶: Factor multivariate polynomials into irreducibles in \(K[X]\).

sympy.polys.factortools.dmp_irreducible_p(f, u, K)[source]¶: Returns True if a multivariate polynomial f has no factors over its domain.

Groebner basis algorithms¶

Groebner bases can be used to answer many problems in computational commutative algebra. Their computation in rather complicated, and very performance-sensitive. We present here various low-level implementations of Groebner basis computation algorithms; please see the previous section of the manual for usage.

sympy.polys.groebnertools.groebner(seq, ring, method=None)[source]¶

Computes Groebner basis for a set of polynomials in \(K[X]\).

Wrapper around the (default) improved Buchberger and the other algorithms for computing Groebner bases. The choice of algorithm can be changed via method argument or sympy.polys.polyconfig.setup(), where method can be either buchberger or f5b.

sympy.polys.groebnertools.spoly(p1, p2, ring)[source]¶: Compute LCM(LM(p1), LM(p2))/LM(p1)*p1 - LCM(LM(p1), LM(p2))/LM(p2)*p2 This is the S-poly provided p1 and p2 are monic

sympy.polys.groebnertools.red_groebner(G, ring)[source]¶

Compute reduced Groebner basis, from BeckerWeispfenning93, p. 216

Selects a subset of generators, that already generate the ideal and computes a reduced Groebner basis for them.

sympy.polys.groebnertools.is_groebner(G, ring)[source]¶: Check if G is a Groebner basis.

sympy.polys.groebnertools.is_minimal(G, ring)[source]¶: Checks if G is a minimal Groebner basis.

sympy.polys.groebnertools.is_reduced(G, ring)[source]¶: Checks if G is a reduced Groebner basis.

sympy.polys.fglmtools.matrix_fglm(F, ring, O_to)[source]¶

Converts the reduced Groebner basis F of a zero-dimensional ideal w.r.t. O_from to a reduced Groebner basis w.r.t. O_to.

References

R619: J.C. Faugere, P. Gianni, D. Lazard, T. Mora (1994). Efficient Computation of Zero-dimensional Groebner Bases by Change of Ordering

Groebner basis algorithms for modules are also provided:

sympy.polys.distributedmodules.sdm_spoly(f, g, O, K, phantom=None)[source]¶

Compute the generalized s-polynomial of f and g.

The ground field is assumed to be K, and monomials ordered according to O.

This is invalid if either of f or g is zero.

If the leading terms of \(f\) and \(g\) involve different basis elements of \(F\), their s-poly is defined to be zero. Otherwise it is a certain linear combination of \(f\) and \(g\) in which the leading terms cancel. See [SCA, defn 2.3.6] for details.

If phantom is not None, it should be a pair of module elements on which to perform the same operation(s) as on f and g. The in this case both results are returned.

Examples

>>> from sympy.polys.distributedmodules import sdm_spoly
>>> from sympy.polys import QQ, lex
>>> f = [((2, 1, 1), QQ(1)), ((1, 0, 1), QQ(1))]
>>> g = [((2, 3, 0), QQ(1))]
>>> h = [((1, 2, 3), QQ(1))]
>>> sdm_spoly(f, h, lex, QQ)
[]
>>> sdm_spoly(f, g, lex, QQ)
[((1, 2, 1), 1)]

sympy.polys.distributedmodules.sdm_ecart(f)[source]¶

Compute the ecart of f.

This is defined to be the difference of the total degree of \(f\) and the total degree of the leading monomial of \(f\) [SCA, defn 2.3.7].

Invalid if f is zero.

Examples

>>> from sympy.polys.distributedmodules import sdm_ecart
>>> sdm_ecart([((1, 2, 3), 1), ((1, 0, 1), 1)])
0
>>> sdm_ecart([((2, 2, 1), 1), ((1, 5, 1), 1)])
3

sympy.polys.distributedmodules.sdm_nf_mora(f, G, O, K, phantom=None)[source]¶

Compute a weak normal form of f with respect to G and order O.

The ground field is assumed to be K, and monomials ordered according to O.

Weak normal forms are defined in [SCA, defn 2.3.3]. They are not unique. This function deterministically computes a weak normal form, depending on the order of \(G\).

The most important property of a weak normal form is the following: if \(R\) is the ring associated with the monomial ordering (if the ordering is global, we just have \(R = K[x_1, \ldots, x_n]\), otherwise it is a certain localization thereof), \(I\) any ideal of \(R\) and \(G\) a standard basis for \(I\), then for any \(f \in R\), we have \(f \in I\) if and only if \(NF(f | G) = 0\).

This is the generalized Mora algorithm for computing weak normal forms with respect to arbitrary monomial orders [SCA, algorithm 2.3.9].

If phantom is not None, it should be a pair of “phantom” arguments on which to perform the same computations as on f, G, both results are then returned.

sympy.polys.distributedmodules.sdm_groebner(G, NF, O, K, extended=False)[source]¶

Compute a minimal standard basis of G with respect to order O.

The algorithm uses a normal form NF, for example sdm_nf_mora. The ground field is assumed to be K, and monomials ordered according to O.

Let \(N\) denote the submodule generated by elements of \(G\). A standard basis for \(N\) is a subset \(S\) of \(N\), such that \(in(S) = in(N)\), where for any subset \(X\) of \(F\), \(in(X)\) denotes the submodule generated by the initial forms of elements of \(X\). [SCA, defn 2.3.2]

A standard basis is called minimal if no subset of it is a standard basis.

One may show that standard bases are always generating sets.

Minimal standard bases are not unique. This algorithm computes a deterministic result, depending on the particular order of \(G\).

If extended=True, also compute the transition matrix from the initial generators to the groebner basis. That is, return a list of coefficient vectors, expressing the elements of the groebner basis in terms of the elements of G.

This functions implements the “sugar” strategy, see

Giovini et al: “One sugar cube, please” OR Selection strategies in Buchberger algorithm.

Options¶

Options manager for Poly and public API functions.

class sympy.polys.polyoptions.Options(gens, args, flags=None, strict=False)[source]¶

Options manager for polynomial manipulation module.

Examples

>>> from sympy.polys.polyoptions import Options
>>> from sympy.polys.polyoptions import build_options

>>> from sympy.abc import x, y, z

>>> Options((x, y, z), {'domain': 'ZZ'})
{'auto': False, 'domain': ZZ, 'gens': (x, y, z)}

>>> build_options((x, y, z), {'domain': 'ZZ'})
{'auto': False, 'domain': ZZ, 'gens': (x, y, z)}

Options

Expand — boolean option
Gens — option
Wrt — option
Sort — option
Order — option
Field — boolean option
Greedy — boolean option
Domain — option
Split — boolean option
Gaussian — boolean option
Extension — option
Modulus — option
Symmetric — boolean option
Strict — boolean option

Flags

Auto — boolean flag
Frac — boolean flag
Formal — boolean flag
Polys — boolean flag
Include — boolean flag
All — boolean flag
Gen — flag
Series — boolean flag

sympy.polys.polyoptions.build_options(gens, args=None)[source]¶: Construct options from keyword arguments or … options.

Configuration¶

Configuration utilities for polynomial manipulation algorithms.

sympy.polys.polyconfig.setup(key, value=None)[source]¶: Assign a value to (or reset) a configuration item.

Exceptions¶

These are exceptions defined by the polynomials module.

TODO sort and explain

class sympy.polys.polyerrors.BasePolynomialError[source]¶: Base class for polynomial related exceptions.

class sympy.polys.polyerrors.ExactQuotientFailed(f, g, dom=None)[source]¶

class sympy.polys.polyerrors.OperationNotSupported(poly, func)[source]¶

class sympy.polys.polyerrors.HeuristicGCDFailed[source]¶

class sympy.polys.polyerrors.HomomorphismFailed[source]¶

class sympy.polys.polyerrors.IsomorphismFailed[source]¶

class sympy.polys.polyerrors.ExtraneousFactors[source]¶

class sympy.polys.polyerrors.EvaluationFailed[source]¶

class sympy.polys.polyerrors.RefinementFailed[source]¶

class sympy.polys.polyerrors.CoercionFailed[source]¶

class sympy.polys.polyerrors.NotInvertible[source]¶

class sympy.polys.polyerrors.NotReversible[source]¶

class sympy.polys.polyerrors.NotAlgebraic[source]¶

class sympy.polys.polyerrors.DomainError[source]¶

class sympy.polys.polyerrors.PolynomialError[source]¶

class sympy.polys.polyerrors.UnificationFailed[source]¶

class sympy.polys.polyerrors.GeneratorsNeeded[source]¶

class sympy.polys.polyerrors.ComputationFailed(func, nargs, exc)[source]¶

class sympy.polys.polyerrors.GeneratorsError[source]¶

class sympy.polys.polyerrors.UnivariatePolynomialError[source]¶

class sympy.polys.polyerrors.MultivariatePolynomialError[source]¶

class sympy.polys.polyerrors.PolificationFailed(opt, origs, exprs, seq=False)[source]¶

class sympy.polys.polyerrors.OptionError[source]¶

class sympy.polys.polyerrors.FlagError[source]¶

Reference¶

Modular GCD¶

sympy.polys.modulargcd.modgcd_univariate(f, g)[source]¶

Computes the GCD of two polynomials in \(\mathbb{Z}[x]\) using a modular algorithm.

The algorithm computes the GCD of two univariate integer polynomials \(f\) and \(g\) by computing the GCD in \(\mathbb{Z}_p[x]\) for suitable primes \(p\) and then reconstructing the coefficients with the Chinese Remainder Theorem. Trial division is only made for candidates which are very likely the desired GCD.

Parameters

f : PolyElement

univariate integer polynomial

g : PolyElement

univariate integer polynomial

Returns

h : PolyElement

GCD of the polynomials \(f\) and \(g\)

cff : PolyElement

cofactor of \(f\), i.e. \(\frac{f}{h}\)

cfg : PolyElement

cofactor of \(g\), i.e. \(\frac{g}{h}\)

Examples

>>> from sympy.polys.modulargcd import modgcd_univariate
>>> from sympy.polys import ring, ZZ

>>> R, x = ring("x", ZZ)

>>> f = x**5 - 1
>>> g = x - 1

>>> h, cff, cfg = modgcd_univariate(f, g)
>>> h, cff, cfg
(x - 1, x**4 + x**3 + x**2 + x + 1, 1)

>>> cff * h == f
True
>>> cfg * h == g
True

>>> f = 6*x**2 - 6
>>> g = 2*x**2 + 4*x + 2

>>> h, cff, cfg = modgcd_univariate(f, g)
>>> h, cff, cfg
(2*x + 2, 3*x - 3, x + 1)

>>> cff * h == f
True
>>> cfg * h == g
True

References

[Monagan00]

sympy.polys.modulargcd.modgcd_bivariate(f, g)[source]¶

Computes the GCD of two polynomials in \(\mathbb{Z}[x, y]\) using a modular algorithm.

The algorithm computes the GCD of two bivariate integer polynomials \(f\) and \(g\) by calculating the GCD in \(\mathbb{Z}_p[x, y]\) for suitable primes \(p\) and then reconstructing the coefficients with the Chinese Remainder Theorem. To compute the bivariate GCD over \(\mathbb{Z}_p\), the polynomials \(f \; \mathrm{mod} \, p\) and \(g \; \mathrm{mod} \, p\) are evaluated at \(y = a\) for certain \(a \in \mathbb{Z}_p\) and then their univariate GCD in \(\mathbb{Z}_p[x]\) is computed. Interpolating those yields the bivariate GCD in \(\mathbb{Z}_p[x, y]\). To verify the result in \(\mathbb{Z}[x, y]\), trial division is done, but only for candidates which are very likely the desired GCD.

Parameters

f : PolyElement

bivariate integer polynomial

g : PolyElement

bivariate integer polynomial

Returns

h : PolyElement

GCD of the polynomials \(f\) and \(g\)

cff : PolyElement

cofactor of \(f\), i.e. \(\frac{f}{h}\)

cfg : PolyElement

cofactor of \(g\), i.e. \(\frac{g}{h}\)

Examples

>>> from sympy.polys.modulargcd import modgcd_bivariate
>>> from sympy.polys import ring, ZZ

>>> R, x, y = ring("x, y", ZZ)

>>> f = x**2 - y**2
>>> g = x**2 + 2*x*y + y**2

>>> h, cff, cfg = modgcd_bivariate(f, g)
>>> h, cff, cfg
(x + y, x - y, x + y)

>>> cff * h == f
True
>>> cfg * h == g
True

>>> f = x**2*y - x**2 - 4*y + 4
>>> g = x + 2

>>> h, cff, cfg = modgcd_bivariate(f, g)
>>> h, cff, cfg
(x + 2, x*y - x - 2*y + 2, 1)

>>> cff * h == f
True
>>> cfg * h == g
True

References

[Monagan00]

sympy.polys.modulargcd.modgcd_multivariate(f, g)[source]¶

Compute the GCD of two polynomials in \(\mathbb{Z}[x_0, \ldots, x_{k-1}]\) using a modular algorithm.

The algorithm computes the GCD of two multivariate integer polynomials \(f\) and \(g\) by calculating the GCD in \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\) for suitable primes \(p\) and then reconstructing the coefficients with the Chinese Remainder Theorem. To compute the multivariate GCD over \(\mathbb{Z}_p\) the recursive subroutine _modgcd_multivariate_p() is used. To verify the result in \(\mathbb{Z}[x_0, \ldots, x_{k-1}]\), trial division is done, but only for candidates which are very likely the desired GCD.

Parameters

f : PolyElement

multivariate integer polynomial

g : PolyElement

multivariate integer polynomial

Returns

h : PolyElement

GCD of the polynomials \(f\) and \(g\)

cff : PolyElement

cofactor of \(f\), i.e. \(\frac{f}{h}\)

cfg : PolyElement

cofactor of \(g\), i.e. \(\frac{g}{h}\)

Examples

>>> from sympy.polys.modulargcd import modgcd_multivariate
>>> from sympy.polys import ring, ZZ

>>> R, x, y = ring("x, y", ZZ)

>>> f = x**2 - y**2
>>> g = x**2 + 2*x*y + y**2

>>> h, cff, cfg = modgcd_multivariate(f, g)
>>> h, cff, cfg
(x + y, x - y, x + y)

>>> cff * h == f
True
>>> cfg * h == g
True

>>> R, x, y, z = ring("x, y, z", ZZ)

>>> f = x*z**2 - y*z**2
>>> g = x**2*z + z

>>> h, cff, cfg = modgcd_multivariate(f, g)
>>> h, cff, cfg
(z, x*z - y*z, x**2 + 1)

>>> cff * h == f
True
>>> cfg * h == g
True

Undocumented¶

Many parts of the polys module are still undocumented, and even where there is documentation it is scarce. Please contribute!

Internals of the Polynomial Manipulation Module¶

Domains¶

Abstract Domains¶

Concrete Domains¶

Implementation Domains¶

Level One¶

Level Zero¶

Manipulation of dense, multivariate polynomials¶

Manipulation of dense, univariate polynomials with finite field coefficients¶

Manipulation of sparse, distributed polynomials and vectors¶

Polynomial factorization algorithms¶

Classical remainder sequence¶

Simplified remainder sequences¶

Subresultant sequence¶

Groebner basis algorithms¶

Options¶

Configuration¶

Exceptions¶

Reference¶

Modular GCD¶

Undocumented¶

Table of Contents

Previous topic

Next topic

This Page