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

Represents an abstract domain.

Attributes

alias  
dtype  
one  
rep  
zero  
abs(a)

Absolute value of a, implies __abs__.

add(a, b)

Sum of a and b, implies __add__.

algebraic_field(*extension)

Returns an algebraic field, i.e. \(K(\alpha, \dots)\).

characteristic()

Return the characteristic of this domain.

convert(K1, a, K0=None)

Convert an object \(a\) from \(K_0\) to \(K_1\).

denom(a)

Returns denominator of a.

div(a, b)

Division of a and b, implies something.

evalf(a, prec=None, **args)

Returns numerical approximation of a.

exquo(a, b)

Exact quotient of a and b, implies something.

frac_field(*gens)

Returns a fraction field, i.e. K(X).

from_AlgebraicField(K1, a, K0)

Convert a ANP object to dtype.

from_ExpressionDomain(K1, a, K0)

Convert a EX object to dtype.

from_FF_gmpy(K1, a, K0)

Convert ModularInteger(mpz) to dtype.

from_FF_python(K1, a, K0)

Convert ModularInteger(int) to dtype.

from_FF_sympy(K1, a, K0)

Convert ModularInteger(Integer) to dtype.

from_FractionField(K1, a, K0)

Convert a DMF object to dtype.

from_GlobalPolynomialRing(K1, a, K0)

Convert a DMP object to dtype.

from_QQ_gmpy(K1, a, K0)

Convert a GMPY mpq object to dtype.

from_QQ_python(K1, a, K0)

Convert a Python Fraction object to dtype.

from_QQ_sympy(K1, a, K0)

Convert a SymPy Rational object to dtype.

from_RR_mpmath(K1, a, K0)

Convert a mpmath mpf object to dtype.

from_RR_sympy(K1, a, K0)

Convert a SymPy Float object to dtype.

from_ZZ_gmpy(K1, a, K0)

Convert a GMPY mpz object to dtype.

from_ZZ_python(K1, a, K0)

Convert a Python int object to dtype.

from_ZZ_sympy(K1, a, K0)

Convert a SymPy Integer object to dtype.

from_sympy(a)

Convert a SymPy object to dtype.

gcd(a, b)

Returns GCD of a and b.

gcdex(a, b)

Extended GCD of a and b.

get_exact()

Returns an exact domain associated with self.

get_field()

Returns a field associated with self.

get_ring()

Returns a ring associated with self.

inject(*gens)

Inject generators into this domain.

invert(a, b)

Returns inversion of a mod b, implies something.

is_negative(a)

Returns True if a is negative.

is_nonnegative(a)

Returns True if a is non-negative.

is_nonpositive(a)

Returns True if a is non-positive.

is_one(a)

Returns True if a is one.

is_positive(a)

Returns True if a is positive.

is_zero(a)

Returns True if a is zero.

lcm(a, b)

Returns LCM of a and b.

log(a, b)

Returns b-base logarithm of a.

map(seq)

Rersively apply self to all elements of seq.

mul(a, b)

Product of a and b, implies __mul__.

n(a, prec=None, **args)

Returns numerical approximation of a.

neg(a)

Returns a negated, implies __neg__.

numer(a)

Returns numerator of a.

of_type(a)

Check if a is of type dtype.

poly_ring(*gens, **opts)

Returns a polynomial ring, i.e. K[X].

pos(a)

Returns a positive, implies __pos__.

pow(a, b)

Raise a to power b, implies __pow__.

quo(a, b)

Quotient of a and b, implies something.

rem(a, b)

Remainder of a and b, implies __mod__.

revert(a)

Returns a**(-1) if possible.

sqrt(a)

Returns square root of a.

sub(a, b)

Difference of a and b, implies __sub__.

to_sympy(a)

Convert a to a SymPy object.

unify(K0, K1, gens=None)

Returns a maximal domain containing \(K_0\) and \(K_1\).

class sympy.polys.domains.Field

Represents a field domain.

Attributes

alias  
dtype  
one  
rep  
zero  
div(a, b)

Division of a and b, implies __div__.

exquo(a, b)

Exact quotient of a and b, implies __div__.

gcd(a, b)

Returns GCD of a and b that is consistent with the core implementation. In addition, this allows the primitive of an expression to be cleared of Rationals.

>>> from sympy.polys.domains import QQ
>>> from sympy import gcd, Rational, primitive
>>> from sympy.abc import x
>>> QQ.gcd(QQ(2, 3), QQ(4, 9))
2/9
>>> gcd(Rational(2, 3), Rational(4, 9))
2/9
>>> primitive(2*x/3 + Rational(4, 9))
(2/9, 3*x + 2)
get_field()

Returns a field associated with self.

get_ring()

Returns a ring associated with self.

lcm(a, b)

Returns LCM of a and b that is consistent with the core implementation.

>>> from sympy.polys.domains import QQ
>>> from sympy import lcm, Rational, primitive
>>> from sympy.abc import x
>>> QQ.lcm(QQ(2, 3), QQ(4, 9))
4/3
>>> lcm(Rational(2, 3), Rational(4, 9))
4/3
quo(a, b)

Quotient of a and b, implies __div__.

rem(a, b)

Remainder of a and b, implies nothing.

revert(a)

Returns a**(-1) if possible.

class sympy.polys.domains.Ring

Represents a ring domain.

Attributes

alias  
dtype  
one  
rep  
zero  
denom(a)

Returns denominator of \(a\).

div(a, b)

Division of a and b, implies __divmod__.

exquo(a, b)

Exact quotient of a and b, implies __floordiv__.

free_module(rank)

Generate a free module of rank rank over self.

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

Returns a ring associated with self.

ideal(*gens)

Generate an ideal of self.

>>> from sympy.abc import x
>>> from sympy import QQ
>>> QQ[x].ideal(x**2)
<x**2>
invert(a, b)

Returns inversion of a mod b.

numer(a)

Returns numerator of a.

quo(a, b)

Quotient of a and b, implies __floordiv__.

quotient_ring(e)

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[x].quotient_ring(QQ[x].ideal(x**2))
QQ[x]/<x**2>
>>> QQ[x].quotient_ring([x**2])
QQ[x]/<x**2>

The division operator has been overloaded for this:

>>> QQ[x]/[x**2]
QQ[x]/<x**2>
rem(a, b)

Remainder of a and b, implies __mod__.

revert(a)

Returns a**(-1) if possible.

class sympy.polys.domains.SimpleDomain

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

Attributes

alias  
dtype  
one  
rep  
zero  
inject(*gens)

Inject generators into this domain.

class sympy.polys.domains.CompositeDomain

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

Attributes

alias  
dtype  
one  
rep  
zero  
inject(*gens)

Inject generators into this domain.

Concrete Domains

class sympy.polys.domains.FiniteField(mod, symmetric=True)

General class for finite fields.

Attributes

alias  
dom  
dtype  
mod  
one  
zero  
characteristic()

Return the characteristic of this domain.

from_FF_gmpy(K1, a, K0=None)

Convert ModularInteger(mpz) to dtype.

from_FF_python(K1, a, K0=None)

Convert ModularInteger(int) to dtype.

from_FF_sympy(K1, a, K0=None)

Convert ModularInteger(Integer) to dtype.

from_QQ_gmpy(K1, a, K0=None)

Convert GMPY’s mpq to dtype.

from_QQ_python(K1, a, K0=None)

Convert Python’s Fraction to dtype.

from_QQ_sympy(K1, a, K0=None)

Convert SymPy’s Rational to dtype.

from_RR_mpmath(K1, a, K0)

Convert mpmath’s mpf to dtype.

from_RR_sympy(K1, a, K0=None)

Convert SymPy’s Float to dtype.

from_ZZ_gmpy(K1, a, K0=None)

Convert GMPY’s mpz to dtype.

from_ZZ_python(K1, a, K0=None)

Convert Python’s int to dtype.

from_ZZ_sympy(K1, a, K0=None)

Convert SymPy’s Integer to dtype.

from_sympy(a)

Convert SymPy’s Integer to SymPy’s Integer.

get_field()

Returns a field associated with self.

to_sympy(a)

Convert a to a SymPy object.

class sympy.polys.domains.IntegerRing

General class for integer rings.

Attributes

alias  
dtype  
one  
zero  
algebraic_field(*extension)

Returns an algebraic field, i.e. \(\mathbb{Q}(\alpha, \dots)\).

from_AlgebraicField(K1, a, K0)

Convert a ANP object to dtype.

get_field()

Returns a field associated with self.

log(a, b)

Returns b-base logarithm of a.

class sympy.polys.domains.PolynomialRing

Create a generalized multivariate polynomial ring.

A generalized polynomial ring is defined by a ground field \(K\), a set of generators (typically \(x_1, \dots, x_n\)) and a monomial order \(<\). The monomial order can be global, local or mixed. In any case it induces a total ordering on the monomials, and there exists for every (non-zero) polynomial \(f \in K[x_1, \dots, x_n]\) a well-defined “leading monomial” \(LM(f) = LM(f, >)\). One can then define a multiplicative subset \(S = S_> = \{f \in K[x_1, \dots, x_n] | LM(f) = 1\}\). The generalized polynomial ring corresponding to the monomial order is \(R = S^{-1}K[x_1, \dots, x_n]\).

If \(>\) is a so-called global order, that is \(1\) is the smallest monomial, then we just have \(S = K\) and \(R = K[x_1, \dots, x_n]\).

Examples

A few examples may make this clearer.

>>> from sympy.abc import x, y
>>> from sympy import QQ

Our first ring uses global lexicographic order.

>>> R1 = QQ.poly_ring(x, y, order=(("lex", x, y),))

The second ring uses local lexicographic order. Note that when using a single (non-product) order, you can just specify the name and omit the variables:

>>> R2 = QQ.poly_ring(x, y, order="ilex")

The third and fourth rings use a mixed orders:

>>> o1 = (("ilex", x), ("lex", y))
>>> o2 = (("lex", x), ("ilex", y))
>>> R3 = QQ.poly_ring(x, y, order=o1)
>>> R4 = QQ.poly_ring(x, y, order=o2)

We will investigate what elements of \(K(x, y)\) are contained in the various rings.

>>> L = [x, 1/x, y/(1 + x), 1/(1 + y), 1/(1 + x*y)]
>>> test = lambda R: [f in R for f in L]

The first ring is just \(K[x, y]\):

>>> test(R1)
[True, False, False, False, False]

The second ring is R1 localised at the maximal ideal (x, y):

>>> test(R2)
[True, False, True, True, True]

The third ring is R1 localised at the prime ideal (x):

>>> test(R3)
[True, False, True, False, True]

Finally the fourth ring is R1 localised at \(S = K[x, y] \setminus yK[y]\):

>>> test(R4)
[True, False, False, True, False]
class sympy.polys.domains.RationalField

General class for rational fields.

Attributes

alias  
dtype  
one  
zero  
algebraic_field(*extension)

Returns an algebraic field, i.e. \(\mathbb{Q}(\alpha, \dots)\).

from_AlgebraicField(K1, a, K0)

Convert a ANP object to dtype.

get_ring()

Returns a ring associated with self.

class sympy.polys.domains.AlgebraicField(dom, *ext)

A class for representing algebraic number fields.

Attributes

alias  
one  
rep  
zero  
algebraic_field(*extension)

Returns an algebraic field, i.e. \(\mathbb{Q}(\alpha, \dots)\).

denom(a)

Returns denominator of a.

dtype

alias of ANP

from_QQ_gmpy(K1, a, K0)

Convert a GMPY mpq object to dtype.

from_QQ_python(K1, a, K0)

Convert a Python Fraction object to dtype.

from_QQ_sympy(K1, a, K0)

Convert a SymPy Rational object to dtype.

from_RR_mpmath(K1, a, K0)

Convert a mpmath mpf object to dtype.

from_RR_sympy(K1, a, K0)

Convert a SymPy Float object to dtype.

from_ZZ_gmpy(K1, a, K0)

Convert a GMPY mpz object to dtype.

from_ZZ_python(K1, a, K0)

Convert a Python int object to dtype.

from_ZZ_sympy(K1, a, K0)

Convert a SymPy Integer object to dtype.

from_sympy(a)

Convert SymPy’s expression to dtype.

get_ring()

Returns a ring associated with self.

is_negative(a)

Returns True if a is negative.

is_nonnegative(a)

Returns True if a is non-negative.

is_nonpositive(a)

Returns True if a is non-positive.

is_positive(a)

Returns True if a is positive.

numer(a)

Returns numerator of a.

to_sympy(a)

Convert a to a SymPy object.

class sympy.polys.domains.FractionField(dom, *gens)

A class for representing rational function fields.

Attributes

alias  
one  
rep  
zero  
denom(a)

Returns denominator of a.

dtype

alias of DMF

factorial(a)

Returns factorial of a.

frac_field(*gens)

Returns a fraction field, i.e. \(K(X)\).

from_FractionField(K1, a, K0)

Convert a fraction field element to another fraction field.

Examples

>>> from sympy.polys.polyclasses import DMF
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.abc import x
>>> f = DMF(([ZZ(1), ZZ(2)], [ZZ(1), ZZ(1)]), ZZ)
>>> QQx = QQ.frac_field(x)
>>> ZZx = ZZ.frac_field(x)
>>> QQx.from_FractionField(f, ZZx)
(x + 2)/(x + 1)
from_GlobalPolynomialRing(K1, a, K0)

Convert a DMF object to dtype.

from_QQ_gmpy(K1, a, K0)

Convert a GMPY mpq object to dtype.

from_QQ_python(K1, a, K0)

Convert a Python Fraction object to dtype.

from_QQ_sympy(K1, a, K0)

Convert a SymPy Rational object to dtype.

from_RR_mpmath(K1, a, K0)

Convert a mpmath mpf object to dtype.

from_RR_sympy(K1, a, K0)

Convert a SymPy Float object to dtype.

from_ZZ_gmpy(K1, a, K0)

Convert a GMPY mpz object to dtype.

from_ZZ_python(K1, a, K0)

Convert a Python int object to dtype.

from_ZZ_sympy(K1, a, K0)

Convert a SymPy Integer object to dtype.

from_sympy(a)

Convert SymPy’s expression to dtype.

get_ring()

Returns a ring associated with self.

is_negative(a)

Returns True if a is negative.

is_nonnegative(a)

Returns True if a is non-negative.

is_nonpositive(a)

Returns True if a is non-positive.

is_positive(a)

Returns True if a is positive.

numer(a)

Returns numerator of a.

poly_ring(*gens)

Returns a polynomial ring, i.e. \(K[X]\).

to_sympy(a)

Convert a to a SymPy object.

class sympy.polys.domains.RealDomain

Abstract domain for real numbers.

Attributes

alias  
dtype  
one  
zero  
as_integer_ratio(a, **args)

Convert real number to a (numer, denom) pair.

div(a, b)

Division of a and b, implies __div__.

exquo(a, b)

Exact quotient of a and b, implies __div__.

from_sympy(a)

Convert SymPy’s number to dtype.

gcd(a, b)

Returns GCD of a and b.

get_exact()

Returns an exact domain associated with self.

get_field()

Returns a field associated with self.

get_ring()

Returns a ring associated with self.

lcm(a, b)

Returns LCM of a and b.

limit_denom(n, d, **args)

Find closest rational to \(n/d\) (up to max_denom).

quo(a, b)

Quotient of a and b, implies __div__.

rem(a, b)

Remainder of a and b, implies nothing.

to_sympy(a)

Convert a to SymPy number.

class sympy.polys.domains.ExpressionDomain

A class for arbitrary expressions.

Attributes

alias  
class Expression(ex)

An arbitrary expression.

ExpressionDomain.denom(a)

Returns denominator of a.

ExpressionDomain.dtype

alias of Expression

ExpressionDomain.from_ExpressionDomain(K1, a, K0)

Convert a EX object to dtype.

ExpressionDomain.from_FractionField(K1, a, K0)

Convert a DMF object to dtype.

ExpressionDomain.from_GlobalPolynomialRing(K1, a, K0)

Convert a DMP object to dtype.

ExpressionDomain.from_QQ_gmpy(K1, a, K0)

Convert a GMPY mpq object to dtype.

ExpressionDomain.from_QQ_python(K1, a, K0)

Convert a Python Fraction object to dtype.

ExpressionDomain.from_QQ_sympy(K1, a, K0)

Convert a SymPy Rational object to dtype.

ExpressionDomain.from_RR_mpmath(K1, a, K0)

Convert a mpmath mpf object to dtype.

ExpressionDomain.from_RR_sympy(K1, a, K0)

Convert a SymPy Float object to dtype.

ExpressionDomain.from_ZZ_gmpy(K1, a, K0)

Convert a GMPY mpz object to dtype.

ExpressionDomain.from_ZZ_python(K1, a, K0)

Convert a Python int object to dtype.

ExpressionDomain.from_ZZ_sympy(K1, a, K0)

Convert a SymPy Integer object to dtype.

ExpressionDomain.from_sympy(a)

Convert SymPy’s expression to dtype.

ExpressionDomain.get_field()

Returns a field associated with self.

ExpressionDomain.get_ring()

Returns a ring associated with self.

ExpressionDomain.is_negative(a)

Returns True if a is negative.

ExpressionDomain.is_nonnegative(a)

Returns True if a is non-negative.

ExpressionDomain.is_nonpositive(a)

Returns True if a is non-positive.

ExpressionDomain.is_positive(a)

Returns True if a is positive.

ExpressionDomain.numer(a)

Returns numerator of a.

ExpressionDomain.to_sympy(a)

Convert a to a SymPy object.

Implementation Domains

class sympy.polys.domains.PythonFiniteField(mod, symmetric=True)

Finite field based on Python’s integers.

Attributes

dtype  
mod  
one  
zero  
class sympy.polys.domains.SymPyFiniteField(mod, symmetric=True)

Finite field based on SymPy’s integers.

Attributes

dtype  
mod  
one  
zero  
class sympy.polys.domains.GMPYFiniteField(mod, symmetric=True)

Finite field based on Python’s integers.

Attributes

dtype  
mod  
one  
zero  
class sympy.polys.domains.PythonIntegerRing

Integer ring based on Python’s int type.

class sympy.polys.domains.SymPyIntegerRing

Integer ring based on SymPy’s Integer type.

class sympy.polys.domains.GMPYIntegerRing

Integer ring based on GMPY’s mpz type.

class sympy.polys.domains.PythonRationalField

Rational field based on Python rational number type.

class sympy.polys.domains.SymPyRationalField

Rational field based on SymPy Rational class.

class sympy.polys.domains.GMPYRationalField

Rational field based on GMPY mpq class.

class sympy.polys.domains.PythonRealDomain

Float domain.

class sympy.polys.domains.SymPyRealDomain

Domain for real numbers based on SymPy Float type.

class sympy.polys.domains.MPmathRealDomain

Domain for real numbers based on mpmath mpf type.

Level One

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

Dense Multivariate Polynomials over \(K\).

LC(f)[source]

Returns the leading coefficient of f.

TC(f)[source]

Returns the trailing coefficient of f.

abs(f)[source]

Make all coefficients in f positive.

add(f, g)[source]

Add two multivariate polynomials f and g.

add_ground(f, c)[source]

Add an element of the ground domain to f.

all_coeffs(f)[source]

Returns all coefficients from f.

all_monoms(f)[source]

Returns all monomials from f.

all_terms(f)[source]

Returns all terms from a f.

cancel(f, g, include=True)[source]

Cancel common factors in a rational function f/g.

clear_denoms(f)[source]

Clear denominators, but keep the ground domain.

coeffs(f, order=None)[source]

Returns all non-zero coefficients from f in lex order.

cofactors(f, g)[source]

Returns GCD of f and g and their cofactors.

compose(f, g)[source]

Computes functional composition of f and g.

content(f)[source]

Returns GCD of polynomial coefficients.

convert(f, dom)[source]

Convert the ground domain of f.

count_complex_roots(f, inf=None, sup=None)[source]

Return the number of complex roots of f in [inf, sup].

count_real_roots(f, inf=None, sup=None)[source]

Return the number of real roots of f in [inf, sup].

decompose(f)[source]

Computes functional decomposition of f.

deflate(f)[source]

Reduce degree of \(f\) by mapping \(x_i^m\) to \(y_i\).

degree(f, j=0)[source]

Returns the leading degree of \(f\) in \(x_j\).

degree_list(f)[source]

Returns a list of degrees of f.

diff(f, m=1, j=0)[source]

Computes \(m\)-th order derivative of \(f\) in \(x_j\).

discriminant(f)[source]

Computes discriminant of f.

div(f, g)[source]

Polynomial division with remainder of f and g.

eject(f, dom, front=False)[source]

Eject selected generators into the ground domain.

eval(f, a, j=0)[source]

Evaluates \(f\) at the given point \(a\) in \(x_j\).

exclude(f)[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(f, g)[source]

Computes polynomial exact quotient of f and g.

exquo_ground(f, c)[source]

Exact quotient of f by a an element of the ground domain.

factor_list(f)[source]

Returns a list of irreducible factors of f.

factor_list_include(f)[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(f, g)[source]

Returns polynomial GCD of f and g.

gcdex(f, g)[source]

Extended Euclidean algorithm, if univariate.

gff_list(f)[source]

Computes greatest factorial factorization of f.

half_gcdex(f, g)[source]

Half extended Euclidean algorithm, if univariate.

homogeneous_order(f)[source]

Returns the homogeneous order of f.

inject(f, front=False)[source]

Inject ground domain generators into f.

integrate(f, m=1, j=0)[source]

Computes indefinite integral of f.

intervals(f, all=False, eps=None, inf=None, sup=None, fast=False, sqf=False)[source]

Compute isolating intervals for roots of f.

invert(f, g)[source]

Invert f modulo g, if possible.

is_cyclotomic[source]

Returns True if f is a cyclotomic polynomial.

is_ground[source]

Returns True if f is an element of the ground domain.

is_homogeneous[source]

Returns True if f is a homogeneous polynomial.

is_irreducible[source]

Returns True if f has no factors over its domain.

is_linear[source]

Returns True if f is linear in all its variables.

is_monic[source]

Returns True if the leading coefficient of f is one.

is_monomial[source]

Returns True if f is zero or has only one term.

is_one[source]

Returns True if f is a unit polynomial.

is_primitive[source]

Returns True if GCD of coefficients of f is one.

is_quadratic[source]

Returns True if f is quadratic in all its variables.

is_sqf[source]

Returns True if f is a square-free polynomial.

is_zero[source]

Returns True if f is a zero polynomial.

l1_norm(f)[source]

Returns l1 norm of f.

lcm(f, g)[source]

Returns polynomial LCM of f and g.

lift(f)[source]

Convert algebraic coefficients to rationals.

max_norm(f)[source]

Returns maximum norm of f.

monic(f)[source]

Divides all coefficients by \(LC(f)\).

monoms(f, order=None)[source]

Returns all non-zero monomials from f in lex order.

mul(f, g)[source]

Multiply two multivariate polynomials f and g.

mul_ground(f, c)[source]

Multiply f by a an element of the ground domain.

neg(f)[source]

Negate all cefficients in f.

nth(f, *N)[source]

Returns the n-th coefficient of f.

pdiv(f, g)[source]

Polynomial pseudo-division of f and g.

per(f, rep, dom=None, kill=False, ring=None)[source]

Create a DMP out of the given representation.

permute(f, 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(f, g)[source]

Polynomial exact pseudo-quotient of f and g.

pow(f, n)[source]

Raise f to a non-negative power n.

pquo(f, g)[source]

Polynomial pseudo-quotient of f and g.

prem(f, g)[source]

Polynomial pseudo-remainder of f and g.

primitive(f)[source]

Returns content and a primitive form of f.

quo(f, g)[source]

Computes polynomial quotient of f and g.

quo_ground(f, c)[source]

Quotient of f by a an element of the ground domain.

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

Refine an isolating interval to the given precision.

rem(f, g)[source]

Computes polynomial remainder of f and g.

resultant(f, g)[source]

Computes resultant of f and g via PRS.

revert(f, n)[source]

Compute f**(-1) mod x**n.

shift(f, a)[source]

Efficiently compute Taylor shift f(x + a).

slice(f, m, n, j=0)[source]

Take a continuous subsequence of terms of f.

sqf_list(f, all=False)[source]

Returns a list of square-free factors of f.

sqf_list_include(f, all=False)[source]

Returns a list of square-free factors of f.

sqf_norm(f)[source]

Computes square-free norm of f.

sqf_part(f)[source]

Computes square-free part of f.

sqr(f)[source]

Square a multivariate polynomial f.

sturm(f)[source]

Computes the Sturm sequence of f.

sub(f, g)[source]

Subtract two multivariate polynomials f and g.

sub_ground(f, c)[source]

Subtract an element of the ground domain from f.

subresultants(f, g)[source]

Computes subresultant PRS sequence of f and g.

terms(f, order=None)[source]

Returns all non-zero terms from f in lex order.

terms_gcd(f)[source]

Remove GCD of terms from the polynomial f.

to_dict(f, zero=False)[source]

Convert f to a dict representation with native coefficients.

to_exact(f)[source]

Make the ground domain exact.

to_field(f)[source]

Make the ground domain a field.

to_ring(f)[source]

Make the ground domain a field.

to_sympy_dict(f, zero=False)[source]

Convert f to a dict representation with SymPy coefficients.

to_tuple(f)[source]

Convert f to a tuple representation with native coefficients.

This is needed for hashing.

total_degree(f)[source]

Returns the total degree of f.

trunc(f, p)[source]

Reduce f modulo a constant p.

unify(f, 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(f, g)[source]

Add two multivariate fractions f and g.

cancel(f)[source]

Remove common factors from f.num and f.den.

denom(f)[source]

Returns denominator of f.

exquo(f, g)

Computes quotient of fractions f and g.

frac_unify(f, g)[source]

Unify representations of two multivariate fractions.

half_per(f, rep, kill=False)[source]

Create a DMP out of the given representation.

invert(f, check=True)[source]

Computes inverse of a fraction f.

is_one[source]

Returns True if f is a unit fraction.

is_zero[source]

Returns True if f is a zero fraction.

mul(f, g)[source]

Multiply two multivariate fractions f and g.

neg(f)[source]

Negate all cefficients in f.

numer(f)[source]

Returns numerator of f.

per(f, num, den, cancel=True, kill=False, ring=None)[source]

Create a DMF out of the given representation.

poly_unify(f, g)[source]

Unify a multivariate fraction and a polynomial.

pow(f, n)[source]

Raise f to a non-negative power n.

quo(f, g)[source]

Computes quotient of fractions f and g.

sub(f, 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(f)[source]

Returns the leading coefficient of f.

TC(f)[source]

Returns the trailing coefficient of f.

is_ground[source]

Returns True if f is an element of the ground domain.

is_one[source]

Returns True if f is a unit algebraic number.

is_zero[source]

Returns True if f is a zero algebraic number.

pow(f, n)[source]

Raise f to a non-negative power n.

to_dict(f)[source]

Convert f to a dict representation with native coefficients.

to_list(f)[source]

Convert f to a list representation with native coefficients.

to_sympy_dict(f)[source]

Convert f to a dict representation with SymPy coefficients.

to_sympy_list(f)[source]

Convert f to a list representation with SymPy coefficients.

to_tuple(f)[source]

Convert f to a tuple representation with native coefficients.

This is needed for hashing.

unify(f, 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, \dots, 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)

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)

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 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 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 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 leading degree of f in x_0 in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_degree
>>> dmp_degree([[[]]], 2)
-1
>>> f = ZZ.map([[2], [1, 2, 3]])
>>> dmp_degree(f, 1)
1
sympy.polys.densebasic.dmp_degree_in(f, j, u)[source]

Return 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 number of levels in f and recursively strips 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 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 ground domain of f from K0 to K1.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.polyclasses import DMP
>>> from sympy.polys.densebasic import dmp_convert
>>> f = [[DMP([1], ZZ)], [DMP([2], ZZ)]]
>>> g = [[ZZ(1)], [ZZ(2)]]
>>> dmp_convert(f, 1, ZZ['x'], ZZ)
[[1], [2]]
>>> dmp_convert(g, 1, ZZ, ZZ['x'])
[[1], [2]]
sympy.polys.densebasic.dmp_from_sympy(f, u, K)[source]

Convert 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 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 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 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 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 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 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.domains import ZZ
>>> from sympy.polys.densebasic import dmp_inject
>>> K = ZZ['x', 'y']
>>> dmp_inject([K([[1]]), K([[1], [2]])], 0, K)
([[[1]], [[1], [2]]], 2)
>>> dmp_inject([K([[1]]), K([[1], [2]])], 0, K, 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
>>> K = ZZ['x', 'y']
>>> dmp_eject([[[1]], [[1], [2]]], 2, K)
[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.domains import ZZ
>>> from sympy.polys.densearith import dmp_add_term
>>> f = ZZ.map([[1, 0], [1]])
>>> c = ZZ.map([2])
>>> dmp_add_term(f, c, 2, 1, ZZ)
[[2], [1, 0], [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.domains import ZZ
>>> from sympy.polys.densearith import dmp_sub_term
>>> f = ZZ.map([[2], [1, 0], [1]])
>>> c = ZZ.map([2])
>>> dmp_sub_term(f, c, 2, 1, ZZ)
[[1, 0], [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.domains import ZZ
>>> from sympy.polys.densearith import dmp_mul_term
>>> f = ZZ.map([[1, 0], [1], []])
>>> c = ZZ.map([3, 0])
>>> dmp_mul_term(f, c, 2, 1, ZZ)
[[3, 0, 0], [3, 0], [], [], []]
sympy.polys.densearith.dmp_add_ground(f, c, u, K)[source]

Add an element of the ground domain to f.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_add_ground
>>> f = ZZ.map([[1], [2], [3], [4]])
>>> dmp_add_ground(f, ZZ(4), 1, ZZ)
[[1], [2], [3], [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.domains import ZZ
>>> from sympy.polys.densearith import dmp_sub_ground
>>> f = ZZ.map([[1], [2], [3], [4]])
>>> dmp_sub_ground(f, ZZ(4), 1, ZZ)
[[1], [2], [3], []]
sympy.polys.densearith.dmp_mul_ground(f, c, u, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_mul_ground
>>> f = ZZ.map([[2], [2, 0]])
>>> dmp_mul_ground(f, ZZ(3), 1, ZZ)
[[6], [6, 0]]
sympy.polys.densearith.dmp_quo_ground(f, c, u, K)[source]

Quotient by a constant in K[X].

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_quo_ground
>>> f = ZZ.map([[2, 0], [3], []])
>>> g = QQ.map([[2, 0], [3], []])
>>> dmp_quo_ground(f, ZZ(2), 1, ZZ)
[[1, 0], [1], []]
>>> dmp_quo_ground(g, QQ(2), 1, QQ)
[[1/1, 0/1], [3/2], []]
sympy.polys.densearith.dmp_exquo_ground(f, c, u, K)[source]

Exact quotient by a constant in K[X].

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_exquo_ground
>>> f = QQ.map([[1, 0], [2], []])
>>> dmp_exquo_ground(f, QQ(2), 1, QQ)
[[1/2, 0/1], [1/1], []]
sympy.polys.densearith.dup_lshift(f, n, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_lshift
>>> f = ZZ.map([1, 0, 1])
>>> dup_lshift(f, 2, ZZ)
[1, 0, 1, 0, 0]
sympy.polys.densearith.dup_rshift(f, n, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_rshift
>>> f = ZZ.map([1, 0, 1, 0, 0])
>>> g = ZZ.map([1, 0, 1, 0, 2])
>>> dup_rshift(f, 2, ZZ)
[1, 0, 1]
>>> dup_rshift(g, 2, ZZ)
[1, 0, 1]
sympy.polys.densearith.dmp_abs(f, u, K)[source]

Make all coefficients positive in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_abs
>>> f = ZZ.map([[1, 0], [-1], []])
>>> dmp_abs(f, 1, ZZ)
[[1, 0], [1], []]
sympy.polys.densearith.dmp_neg(f, u, K)[source]

Negate a polynomial in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_neg
>>> f = ZZ.map([[1, 0], [-1], []])
>>> dmp_neg(f, 1, ZZ)
[[-1, 0], [1], []]
sympy.polys.densearith.dmp_add(f, g, u, K)[source]

Add dense polynomials in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_add
>>> f = ZZ.map([[1], [], [1, 0]])
>>> g = ZZ.map([[1, 0], [1], []])
>>> dmp_add(f, g, 1, ZZ)
[[1, 1], [1], [1, 0]]
sympy.polys.densearith.dmp_sub(f, g, u, K)[source]

Subtract dense polynomials in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_sub
>>> f = ZZ.map([[1], [], [1, 0]])
>>> g = ZZ.map([[1, 0], [1], []])
>>> dmp_sub(f, g, 1, ZZ)
[[-1, 1], [-1], [1, 0]]
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.domains import ZZ
>>> from sympy.polys.densearith import dmp_add_mul
>>> f = ZZ.map([[1], [], [1, 0]])
>>> g = ZZ.map([[1], []])
>>> h = ZZ.map([[1], [2]])
>>> dmp_add_mul(f, g, h, 1, ZZ)
[[2], [2], [1, 0]]
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.domains import ZZ
>>> from sympy.polys.densearith import dmp_sub_mul
>>> f = ZZ.map([[1], [], [1, 0]])
>>> g = ZZ.map([[1], []])
>>> h = ZZ.map([[1], [2]])
>>> dmp_sub_mul(f, g, h, 1, ZZ)
[[-2], [1, 0]]
sympy.polys.densearith.dmp_mul(f, g, u, K)[source]

Multiply dense polynomials in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_mul
>>> f = ZZ.map([[1, 0], [1]])
>>> g = ZZ.map([[1], []])
>>> dmp_mul(f, g, 1, ZZ)
[[1, 0], [1], []]
sympy.polys.densearith.dmp_sqr(f, u, K)[source]

Square dense polynomials in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_sqr
>>> f = ZZ.map([[1], [1, 0], [1, 0, 0]])
>>> dmp_sqr(f, 1, ZZ)
[[1], [2, 0], [3, 0, 0], [2, 0, 0, 0], [1, 0, 0, 0, 0]]
sympy.polys.densearith.dmp_pow(f, n, u, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_pow
>>> f = ZZ.map([[1, 0], [1]])
>>> dmp_pow(f, 3, 1, ZZ)
[[1, 0, 0, 0], [3, 0, 0], [3, 0], [1]]
sympy.polys.densearith.dmp_pdiv(f, g, u, K)[source]

Polynomial pseudo-division in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_pdiv
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_pdiv(f, g, 1, ZZ)
([[2], [2, -2]], [[-4, 4]])
sympy.polys.densearith.dmp_prem(f, g, u, K)[source]

Polynomial pseudo-remainder in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_prem
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_prem(f, g, 1, ZZ)
[[-4, 4]]
sympy.polys.densearith.dmp_pquo(f, g, u, K)[source]

Polynomial exact pseudo-quotient in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_pquo
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2, 0]])
>>> h = ZZ.map([[2], [2]])
>>> dmp_pquo(f, g, 1, ZZ)
[[2], []]
>>> dmp_pquo(f, h, 1, ZZ)
[[2], [2, -2]]
sympy.polys.densearith.dmp_pexquo(f, g, u, K)[source]

Polynomial pseudo-quotient in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_pexquo
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2, 0]])
>>> h = ZZ.map([[2], [2]])
>>> dmp_pexquo(f, g, 1, ZZ)
[[2], []]
>>> dmp_pexquo(f, h, 1, ZZ)
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.domains import ZZ
>>> from sympy.polys.densearith import dmp_rr_div
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_rr_div(f, g, 1, ZZ)
([[]], [[1], [1, 0], []])
sympy.polys.densearith.dmp_ff_div(f, g, u, K)[source]

Polynomial division with remainder over a field.

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.densearith import dmp_ff_div
>>> f = QQ.map([[1], [1, 0], []])
>>> g = QQ.map([[2], [2]])
>>> dmp_ff_div(f, g, 1, QQ)
([[1/2], [1/2, -1/2]], [[-1/1, 1/1]])
sympy.polys.densearith.dmp_div(f, g, u, K)[source]

Polynomial division with remainder in K[X].

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_div
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_div(f, g, 1, ZZ)
([[]], [[1], [1, 0], []])
>>> f = QQ.map([[1], [1, 0], []])
>>> g = QQ.map([[2], [2]])
>>> dmp_div(f, g, 1, QQ)
([[1/2], [1/2, -1/2]], [[-1/1, 1/1]])
sympy.polys.densearith.dmp_rem(f, g, u, K)[source]

Returns polynomial remainder in K[X].

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_rem
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_rem(f, g, 1, ZZ)
[[1], [1, 0], []]
>>> f = QQ.map([[1], [1, 0], []])
>>> g = QQ.map([[2], [2]])
>>> dmp_rem(f, g, 1, QQ)
[[-1/1, 1/1]]
sympy.polys.densearith.dmp_quo(f, g, u, K)[source]

Returns exact polynomial quotient in K[X].

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_quo
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_quo(f, g, 1, ZZ)
[[]]
>>> f = QQ.map([[1], [1, 0], []])
>>> g = QQ.map([[2], [2]])
>>> dmp_quo(f, g, 1, QQ)
[[1/2], [1/2, -1/2]]
sympy.polys.densearith.dmp_exquo(f, g, u, K)[source]

Returns polynomial quotient in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_exquo
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[1], [1, 0]])
>>> h = ZZ.map([[2], [2]])
>>> dmp_exquo(f, g, 1, ZZ)
[[1], []]
>>> dmp_exquo(f, h, 1, ZZ)
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.domains import ZZ
>>> from sympy.polys.densearith import dmp_max_norm
>>> f = ZZ.map([[2, -1], [-3]])
>>> dmp_max_norm(f, 1, ZZ)
3
sympy.polys.densearith.dmp_l1_norm(f, u, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_l1_norm
>>> f = ZZ.map([[2, -1], [-3]])
>>> dmp_l1_norm(f, 1, ZZ)
6
sympy.polys.densearith.dmp_expand(polys, u, K)[source]

Multiply together several polynomials in K[X].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_expand
>>> f = ZZ.map([[1], [], [1, 0, 0]])
>>> g = ZZ.map([[1], [1]])
>>> dmp_expand([f, g], 1, ZZ)
[[1], [1], [1, 0, 0], [1, 0, 0]]

Further tools:

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

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

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.densetools import dmp_integrate
>>> dmp_integrate([[QQ(1)], [QQ(2), QQ(0)]], 1, 1, QQ)
[[1/2], [2/1, 0/1], []]
>>> dmp_integrate([[QQ(1)], [QQ(2), QQ(0)]], 2, 1, QQ)
[[1/6], [1/1, 0/1], [], []]
sympy.polys.densetools.dmp_integrate_in(f, m, j, u, K)[source]

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

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.densetools import dmp_integrate_in
>>> dmp_integrate_in([[QQ(1)], [QQ(2), QQ(0)]], 1, 0, 1, QQ)
[[1/2], [2/1, 0/1], []]
>>> dmp_integrate_in([[QQ(1)], [QQ(2), QQ(0)]], 1, 1, 1, QQ)
[[1/1, 0/1], [1/1, 0/1, 0/1]]
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.domains import ZZ
>>> from sympy.polys.densetools import dmp_diff
>>> f = ZZ.map([[1, 2, 3], [2, 3, 1]])
>>> dmp_diff(f, 1, 1, ZZ)
[[1, 2, 3]]
>>> dmp_diff(f, 2, 1, ZZ)
[[]]
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.domains import ZZ
>>> from sympy.polys.densetools import dmp_diff_in
>>> f = ZZ.map([[1, 2, 3], [2, 3, 1]])
>>> dmp_diff_in(f, 1, 0, 1, ZZ)
[[1, 2, 3]]
>>> dmp_diff_in(f, 1, 1, 1, ZZ)
[[2, 2], [4, 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.domains import ZZ
>>> from sympy.polys.densetools import dmp_eval
>>> f = ZZ.map([[2, 3], [1, 2]])
>>> dmp_eval(f, 2, 1, ZZ)
[5, 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.domains import ZZ
>>> from sympy.polys.densetools import dmp_eval_in
>>> f = ZZ.map([[2, 3], [1, 2]])
>>> dmp_eval_in(f, 2, 0, 1, ZZ)
[5, 8]
>>> dmp_eval_in(f, 2, 1, 1, ZZ)
[7, 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.domains import ZZ
>>> from sympy.polys.densetools import dmp_eval_tail
>>> f = ZZ.map([[2, 3], [1, 2]])
>>> dmp_eval_tail(f, (2, 2), 1, ZZ)
18
>>> dmp_eval_tail(f, (2,), 1, ZZ)
[7, 4]
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.domains import ZZ
>>> from sympy.polys.densetools import dmp_diff_eval_in
>>> f = ZZ.map([[1, 2, 3], [2, 3, 1]])
>>> dmp_diff_eval_in(f, 1, 2, 0, 1, ZZ)
[1, 2, 3]
>>> dmp_diff_eval_in(f, 1, 2, 1, 1, ZZ)
[6, 11]
sympy.polys.densetools.dmp_trunc(f, p, u, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dmp_trunc
>>> f = ZZ.map([[3, 8], [5, 6], [2, 3]])
>>> g = ZZ.map([1, -1])
>>> dmp_trunc(f, g, 1, ZZ)
[[11], [11], [5]]
sympy.polys.densetools.dmp_ground_trunc(f, p, u, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dmp_ground_trunc
>>> f = ZZ.map([[3, 8], [5, 6], [2, 3]])
>>> dmp_ground_trunc(f, ZZ(3), 1, ZZ)
[[-1], [-1, 0], [-1, 0]]
sympy.polys.densetools.dup_monic(f, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densetools import dup_monic
>>> dup_monic([ZZ(3), ZZ(6), ZZ(9)], ZZ)
[1, 2, 3]
>>> dup_monic([QQ(3), QQ(4), QQ(2)], QQ)
[1/1, 4/3, 2/3]
sympy.polys.densetools.dmp_ground_monic(f, u, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densetools import dmp_ground_monic
>>> f = ZZ.map([[3, 6], [3, 0], [9, 3]])
>>> g = QQ.map([[3, 8], [5, 6], [2, 3]])
>>> dmp_ground_monic(f, 1, ZZ)
[[1, 2], [1, 0], [3, 1]]
>>> dmp_ground_monic(g, 1, QQ)
[[1/1, 8/3], [5/3, 2/1], [2/3, 1/1]]
sympy.polys.densetools.dup_content(f, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densetools import dup_content
>>> f = ZZ.map([6, 8, 12])
>>> g = QQ.map([6, 8, 12])
>>> dup_content(f, ZZ)
2
>>> dup_content(g, QQ)
2/1
sympy.polys.densetools.dmp_ground_content(f, u, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densetools import dmp_ground_content
>>> f = ZZ.map([[2, 6], [4, 12]])
>>> g = QQ.map([[2, 6], [4, 12]])
>>> dmp_ground_content(f, 1, ZZ)
2
>>> dmp_ground_content(g, 1, QQ)
2/1
sympy.polys.densetools.dup_primitive(f, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densetools import dup_primitive
>>> f = ZZ.map([6, 8, 12])
>>> g = QQ.map([6, 8, 12])
>>> dup_primitive(f, ZZ)
(2, [3, 4, 6])
>>> dup_primitive(g, QQ)
(2/1, [3/1, 4/1, 6/1])
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.domains import ZZ, QQ
>>> from sympy.polys.densetools import dmp_ground_primitive
>>> f = ZZ.map([[2, 6], [4, 12]])
>>> g = QQ.map([[2, 6], [4, 12]])
>>> dmp_ground_primitive(f, 1, ZZ)
(2, [[1, 3], [2, 6]])
>>> dmp_ground_primitive(g, 1, QQ)
(2/1, [[1/1, 3/1], [2/1, 6/1]])
sympy.polys.densetools.dup_extract(f, g, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dup_extract
>>> f = ZZ.map([6, 12, 18])
>>> g = ZZ.map([4, 8, 12])
>>> dup_extract(f, g, ZZ)
(2, [3, 6, 9], [2, 4, 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.domains import ZZ
>>> from sympy.polys.densetools import dmp_ground_extract
>>> f = ZZ.map([[6, 12], [18]])
>>> g = ZZ.map([[4, 8], [12]])
>>> dmp_ground_extract(f, g, 1, ZZ)
(2, [[3, 6], [9]], [[2, 4], [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.domains import ZZ
>>> from sympy.polys.densetools import dup_real_imag
>>> dup_real_imag([ZZ(1), ZZ(1), ZZ(1), ZZ(1)], ZZ)
([[1], [1], [-3, 0, 1], [-1, 0, 1]], [[3, 0], [2, 0], [-1, 0, 1, 0]])
sympy.polys.densetools.dup_mirror(f, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dup_mirror
>>> dup_mirror([ZZ(1), ZZ(2), -ZZ(4), ZZ(2)], ZZ)
[-1, 2, 4, 2]
sympy.polys.densetools.dup_scale(f, a, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dup_scale
>>> dup_scale([ZZ(1), -ZZ(2), ZZ(1)], ZZ(2), ZZ)
[4, -4, 1]
sympy.polys.densetools.dup_shift(f, a, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dup_shift
>>> dup_shift([ZZ(1), -ZZ(2), ZZ(1)], ZZ(2), ZZ)
[1, 2, 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.domains import ZZ
>>> from sympy.polys.densetools import dup_transform
>>> f = ZZ.map([1, -2, 1])
>>> p = ZZ.map([1, 0, 1])
>>> q = ZZ.map([1, -1])
>>> dup_transform(f, p, q, ZZ)
[1, -2, 5, -4, 4]
sympy.polys.densetools.dmp_compose(f, g, u, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dmp_compose
>>> f = ZZ.map([[1, 2], [1, 0]])
>>> g = ZZ.map([[1, 0]])
>>> dmp_compose(f, g, 1, ZZ)
[[1, 3, 0]]
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:

  1. f o g = f(x + b) o (g - b)
  2. x**n o x**m = x**m o x**n
  3. T_n o T_m = T_m o T_n

where T_n and T_m are Chebyshev polynomials.

References

  1. [Kozen89]

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dup_decompose
>>> f = ZZ.map([1, -2, 1, 0, 0])
>>> dup_decompose(f, ZZ)
[[1, 0, 0], [1, -1, 0]]
sympy.polys.densetools.dmp_lift(f, u, K)[source]

Convert algebraic coefficients to integers in K[X].

Examples

>>> from sympy import I
>>> from sympy.polys.domains import QQ
>>> from sympy.polys.densetools import dmp_lift
>>> K = QQ.algebraic_field(I)
>>> f = [K(1), K([QQ(1), QQ(0)]), K([QQ(2), QQ(0)])]
>>> dmp_lift(f, 0, K)
[1/1, 0/1, 2/1, 0/1, 9/1, 0/1, -8/1, 0/1, 16/1]
sympy.polys.densetools.dup_sign_variations(f, K)[source]

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

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densetools import dup_sign_variations
>>> f = ZZ.map([1, 0, -1, -1, 1])
>>> dup_sign_variations(f, ZZ)
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.domains import QQ, ZZ
>>> from sympy.polys.densetools import dmp_clear_denoms
>>> f = [[QQ(1,2)], [QQ(1,3), QQ(1)]]
>>> dmp_clear_denoms(f, 1, QQ, convert=False)
(6, [[3/1], [2/1, 6/1]])
>>> f = [[QQ(1,2)], [QQ(1,3), QQ(1)]]
>>> dmp_clear_denoms(f, 1, QQ, convert=True)
(6, [[3], [2, 6]])
sympy.polys.densetools.dmp_revert(f, g, u, K)[source]

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

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.densetools import dmp_revert

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.

As an example 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.

sympy.polys.galoistools.gf_crt1(M, K)[source]

First part of the Chinese Remainder Theorem.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_crt1
>>> gf_crt1([99, 97, 95], ZZ)
(912285, [9215, 9405, 9603], [62, 24, 12])
sympy.polys.galoistools.gf_crt2(U, M, p, E, S, K)[source]

Second part of the Chinese Remainder Theorem.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_crt2
>>> U = [49, 76, 65]
>>> M = [99, 97, 95]
>>> p = 912285
>>> E = [9215, 9405, 9603]
>>> S = [62, 24, 12]
>>> gf_crt2(U, M, p, E, S, ZZ)
639985
sympy.polys.galoistools.gf_int(a, p)[source]

Coerce a mod p to an integer in [-p/2, p/2] range.

Examples

>>> from sympy.polys.galoistools import gf_int
>>> gf_int(2, 7)
2
>>> gf_int(5, 7)
-2
sympy.polys.galoistools.gf_degree(f)[source]

Return leading degree of f.

Examples

>>> from sympy.polys.galoistools import gf_degree
>>> gf_degree([1, 1, 2, 0])
3
>>> gf_degree([])
-1
sympy.polys.galoistools.gf_LC(f, K)[source]

Return leading coefficient of f.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_LC
>>> gf_LC([3, 0, 1], ZZ)
3
sympy.polys.galoistools.gf_TC(f, K)[source]

Return trailing coefficient of f.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_TC
>>> gf_TC([3, 0, 1], ZZ)
1
sympy.polys.galoistools.gf_strip(f)[source]

Remove leading zeros from f.

Examples

>>> from sympy.polys.galoistools import gf_strip
>>> gf_strip([0, 0, 0, 3, 0, 1])
[3, 0, 1]
sympy.polys.galoistools.gf_trunc(f, p)[source]

Reduce all coefficients modulo p.

Examples

>>> from sympy.polys.galoistools import gf_trunc
>>> gf_trunc([7, -2, 3], 5)
[2, 3, 3]
sympy.polys.galoistools.gf_normal(f, p, K)[source]

Normalize all coefficients in K.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_normal
>>> gf_normal([5, 10, 21, -3], 5, ZZ)
[1, 2]
sympy.polys.galoistools.gf_convert(f, p, K0, K1)[source]

Normalize all coefficients in K.

Examples

>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.galoistools import gf_convert
>>> gf_convert([QQ(1), QQ(4), QQ(0)], 3, QQ, ZZ)
[1, 1, 0]
sympy.polys.galoistools.gf_from_dict(f, p, K)[source]

Create GF(p)[x] polynomial from a dict.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_from_dict
>>> gf_from_dict({10: 4, 4: 33, 0: -1}, 5, ZZ)
[4, 0, 0, 0, 0, 0, 3, 0, 0, 0, 4]
sympy.polys.galoistools.gf_to_dict(f, p, symmetric=True)[source]

Convert GF(p)[x] polynomial to a dict.

Examples

>>> from sympy.polys.galoistools import gf_to_dict
>>> gf_to_dict([4, 0, 0, 0, 0, 0, 3, 0, 0, 0, 4], 5)
{0: -1, 4: -2, 10: -1}
>>> gf_to_dict([4, 0, 0, 0, 0, 0, 3, 0, 0, 0, 4], 5, symmetric=False)
{0: 4, 4: 3, 10: 4}
sympy.polys.galoistools.gf_from_int_poly(f, p)[source]

Create GF(p)[x] polynomial from Z[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_from_int_poly
>>> gf_from_int_poly([7, -2, 3], 5)
[2, 3, 3]
sympy.polys.galoistools.gf_to_int_poly(f, p, symmetric=True)[source]

Convert GF(p)[x] polynomial to Z[x].

Examples

>>> from sympy.polys.galoistools import gf_to_int_poly
>>> gf_to_int_poly([2, 3, 3], 5)
[2, -2, -2]
>>> gf_to_int_poly([2, 3, 3], 5, symmetric=False)
[2, 3, 3]
sympy.polys.galoistools.gf_neg(f, p, K)[source]

Negate a polynomial in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_neg
>>> gf_neg([3, 2, 1, 0], 5, ZZ)
[2, 3, 4, 0]
sympy.polys.galoistools.gf_add_ground(f, a, p, K)[source]

Compute f + a where f in GF(p)[x] and a in GF(p).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_add_ground
>>> gf_add_ground([3, 2, 4], 2, 5, ZZ)
[3, 2, 1]
sympy.polys.galoistools.gf_sub_ground(f, a, p, K)[source]

Compute f - a where f in GF(p)[x] and a in GF(p).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sub_ground
>>> gf_sub_ground([3, 2, 4], 2, 5, ZZ)
[3, 2, 2]
sympy.polys.galoistools.gf_mul_ground(f, a, p, K)[source]

Compute f * a where f in GF(p)[x] and a in GF(p).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_mul_ground
>>> gf_mul_ground([3, 2, 4], 2, 5, ZZ)
[1, 4, 3]
sympy.polys.galoistools.gf_quo_ground(f, a, p, K)[source]

Compute f/a where f in GF(p)[x] and a in GF(p).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_quo_ground
>>> gf_quo_ground([3, 2, 4], 2, 5, ZZ)
[4, 1, 2]
sympy.polys.galoistools.gf_add(f, g, p, K)[source]

Add polynomials in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_add
>>> gf_add([3, 2, 4], [2, 2, 2], 5, ZZ)
[4, 1]
sympy.polys.galoistools.gf_sub(f, g, p, K)[source]

Subtract polynomials in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sub
>>> gf_sub([3, 2, 4], [2, 2, 2], 5, ZZ)
[1, 0, 2]
sympy.polys.galoistools.gf_mul(f, g, p, K)[source]

Multiply polynomials in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_mul
>>> gf_mul([3, 2, 4], [2, 2, 2], 5, ZZ)
[1, 0, 3, 2, 3]
sympy.polys.galoistools.gf_sqr(f, p, K)[source]

Square polynomials in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sqr
>>> gf_sqr([3, 2, 4], 5, ZZ)
[4, 2, 3, 1, 1]
sympy.polys.galoistools.gf_add_mul(f, g, h, p, K)[source]

Returns f + g*h where f, g, h in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_add_mul
>>> gf_add_mul([3, 2, 4], [2, 2, 2], [1, 4], 5, ZZ)
[2, 3, 2, 2]
sympy.polys.galoistools.gf_sub_mul(f, g, h, p, K)[source]

Compute f - g*h where f, g, h in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sub_mul
>>> gf_sub_mul([3, 2, 4], [2, 2, 2], [1, 4], 5, ZZ)
[3, 3, 2, 1]
sympy.polys.galoistools.gf_expand(F, p, K)[source]

Expand results of factor() in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_expand
>>> gf_expand([([3, 2, 4], 1), ([2, 2], 2), ([3, 1], 3)], 5, ZZ)
[4, 3, 0, 3, 0, 1, 4, 1]
sympy.polys.galoistools.gf_div(f, g, p, K)[source]

Division with remainder in GF(p)[x].

Given univariate polynomials f and g with coefficients in a finite field with p elements, returns polynomials q and r (quotient and remainder) such that f = q*g + r.

Consider polynomials x**3 + x + 1 and x**2 + x in GF(2):

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_div, gf_add_mul

>>> gf_div([1, 0, 1, 1], [1, 1, 0], 2, ZZ)
([1, 1], [1])

As result we obtained quotient x + 1 and remainder 1, thus:

>>> gf_add_mul([1], [1, 1], [1, 1, 0], 2, ZZ)
[1, 0, 1, 1]

References

  1. [Monagan93]
  2. [Gathen99]
sympy.polys.galoistools.gf_rem(f, g, p, K)[source]

Compute polynomial remainder in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_rem
>>> gf_rem([1, 0, 1, 1], [1, 1, 0], 2, ZZ)
[1]
sympy.polys.galoistools.gf_quo(f, g, p, K)[source]

Compute exact quotient in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_quo
>>> gf_quo([1, 0, 1, 1], [1, 1, 0], 2, ZZ)
[1, 1]
>>> gf_quo([1, 0, 3, 2, 3], [2, 2, 2], 5, ZZ)
[3, 2, 4]
sympy.polys.galoistools.gf_exquo(f, g, p, K)[source]

Compute polynomial quotient in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_exquo
>>> gf_exquo([1, 0, 3, 2, 3], [2, 2, 2], 5, ZZ)
[3, 2, 4]
>>> gf_exquo([1, 0, 1, 1], [1, 1, 0], 2, ZZ)
Traceback (most recent call last):
...
ExactQuotientFailed: [1, 1, 0] does not divide [1, 0, 1, 1]
sympy.polys.galoistools.gf_lshift(f, n, K)[source]

Efficiently multiply f by x**n.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_lshift
>>> gf_lshift([3, 2, 4], 4, ZZ)
[3, 2, 4, 0, 0, 0, 0]
sympy.polys.galoistools.gf_rshift(f, n, K)[source]

Efficiently divide f by x**n.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_rshift
>>> gf_rshift([1, 2, 3, 4, 0], 3, ZZ)
([1, 2], [3, 4, 0])
sympy.polys.galoistools.gf_pow(f, n, p, K)[source]

Compute f**n in GF(p)[x] using repeated squaring.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_pow
>>> gf_pow([3, 2, 4], 3, 5, ZZ)
[2, 4, 4, 2, 2, 1, 4]
sympy.polys.galoistools.gf_pow_mod(f, n, g, p, K)[source]

Compute f**n in GF(p)[x]/(g) using repeated squaring.

Given polynomials f and g in GF(p)[x] and a non-negative integer n, efficiently computes f**n (mod g) i.e. remainder from division f**n by g using repeated squaring algorithm.

References

  1. [Gathen99]

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_pow_mod
>>> gf_pow_mod([3, 2, 4], 3, [1, 1], 5, ZZ)
[]
sympy.polys.galoistools.gf_gcd(f, g, p, K)[source]

Euclidean Algorithm in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_gcd
>>> gf_gcd([3, 2, 4], [2, 2, 3], 5, ZZ)
[1, 3]
sympy.polys.galoistools.gf_lcm(f, g, p, K)[source]

Compute polynomial LCM in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_lcm
>>> gf_lcm([3, 2, 4], [2, 2, 3], 5, ZZ)
[1, 2, 0, 4]
sympy.polys.galoistools.gf_cofactors(f, g, p, K)[source]

Compute polynomial GCD and cofactors in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_cofactors
>>> gf_cofactors([3, 2, 4], [2, 2, 3], 5, ZZ)
([1, 3], [3, 3], [2, 1])
sympy.polys.galoistools.gf_gcdex(f, g, p, K)[source]

Extended Euclidean Algorithm in GF(p)[x].

Given polynomials f and g in GF(p)[x], computes polynomials s, t and h, such that h = gcd(f, g) and s*f + t*g = h. The typical application of EEA is solving polynomial diophantine equations.

Consider polynomials f = (x + 7) (x + 1), g = (x + 7) (x**2 + 1) in GF(11)[x]. Application of Extended Euclidean Algorithm gives:

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_gcdex, gf_mul, gf_add

>>> s, t, g = gf_gcdex([1,8,7], [1,7,1,7], 11, ZZ)
>>> s, t, g
([5, 6], [6], [1, 7])

As result we obtained polynomials s = 5*x + 6 and t = 6, and additionally gcd(f, g) = x + 7. This is correct because:

>>> S = gf_mul(s,   [1,8,7], 11, ZZ)
>>> T = gf_mul(t, [1,7,1,7], 11, ZZ)

>>> gf_add(S, T, 11, ZZ) == [1, 7]
True

References

  1. [Gathen99]
sympy.polys.galoistools.gf_monic(f, p, K)[source]

Compute LC and a monic polynomial in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_monic
>>> gf_monic([3, 2, 4], 5, ZZ)
(3, [1, 4, 3])
sympy.polys.galoistools.gf_diff(f, p, K)[source]

Differentiate polynomial in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_diff
>>> gf_diff([3, 2, 4], 5, ZZ)
[1, 2]
sympy.polys.galoistools.gf_eval(f, a, p, K)[source]

Evaluate f(a) in GF(p) using Horner scheme.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_eval
>>> gf_eval([3, 2, 4], 2, 5, ZZ)
0
sympy.polys.galoistools.gf_multi_eval(f, A, p, K)[source]

Evaluate f(a) for a in [a_1, ..., a_n].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_multi_eval
>>> gf_multi_eval([3, 2, 4], [0, 1, 2, 3, 4], 5, ZZ)
[4, 4, 0, 2, 0]
sympy.polys.galoistools.gf_compose(f, g, p, K)[source]

Compute polynomial composition f(g) in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_compose
>>> gf_compose([3, 2, 4], [2, 2, 2], 5, ZZ)
[2, 4, 0, 3, 0]
sympy.polys.galoistools.gf_compose_mod(g, h, f, p, K)[source]

Compute polynomial composition g(h) in GF(p)[x]/(f).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_compose_mod
>>> gf_compose_mod([3, 2, 4], [2, 2, 2], [4, 3], 5, ZZ)
[4]
sympy.polys.galoistools.gf_trace_map(a, b, c, n, f, p, K)[source]

Compute polynomial trace map in GF(p)[x]/(f).

Given a polynomial f in GF(p)[x], polynomials a, b, c in the quotient ring GF(p)[x]/(f) such that b = c**t (mod f) for some positive power t of p, and a positive integer n, returns a mapping:

a -> a**t**n, a + a**t + a**t**2 + ... + a**t**n (mod f)

In factorization context, b = x**p mod f and c = x mod f. This way we can efficiently compute trace polynomials in equal degree factorization routine, much faster than with other methods, like iterated Frobenius algorithm, for large degrees.

References

  1. [Gathen92]

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_trace_map
>>> gf_trace_map([1, 2], [4, 4], [1, 1], 4, [3, 2, 4], 5, ZZ)
([1, 3], [1, 3])
sympy.polys.galoistools.gf_random(n, p, K)[source]

Generate a random polynomial in GF(p)[x] of degree n.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_random
>>> gf_random(10, 5, ZZ) 
[1, 2, 3, 2, 1, 1, 1, 2, 0, 4, 2]
sympy.polys.galoistools.gf_irreducible(n, p, K)[source]

Generate random irreducible polynomial of degree n in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_irreducible
>>> gf_irreducible(10, 5, ZZ) 
[1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4]
sympy.polys.galoistools.gf_irreducible_p(f, p, K)[source]

Test irreducibility of a polynomial f in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_irreducible_p
>>> gf_irreducible_p([1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4], 5, ZZ)
True
>>> gf_irreducible_p([3, 2, 4], 5, ZZ)
False
sympy.polys.galoistools.gf_sqf_p(f, p, K)[source]

Return True if f is square-free in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sqf_p
>>> gf_sqf_p([3, 2, 4], 5, ZZ)
True
>>> gf_sqf_p([2, 4, 4, 2, 2, 1, 4], 5, ZZ)
False
sympy.polys.galoistools.gf_sqf_part(f, p, K)[source]

Return square-free part of a GF(p)[x] polynomial.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sqf_part
>>> gf_sqf_part([1, 1, 3, 0, 1, 0, 2, 2, 1], 5, ZZ)
[1, 4, 3]
sympy.polys.galoistools.gf_sqf_list(f, p, K, all=False)[source]

Return square-free decomposition of a GF(p)[x] polynomial.

Given a polynomial f in GF(p)[x], returns the leading coefficient of f and a square-free decomposition f_1**e_1 f_2**e_2 ... f_k**e_k such that all f_i are monic polynomials and (f_i, f_j) for i != j are co-prime and e_1 ... e_k are given in increasing order. All trivial terms (i.e. f_i = 1) aren’t included in the output.

Consider polynomial f = x**11 + 1 over GF(11)[x]:

>>> from sympy.polys.domains import ZZ

>>> from sympy.polys.galoistools import (
...     gf_from_dict, gf_diff, gf_sqf_list, gf_pow,
... )
... 

>>> f = gf_from_dict({11: 1, 0: 1}, 11, ZZ)

Note that f'(x) = 0:

>>> gf_diff(f, 11, ZZ)
[]

This phenomenon doesn’t happen in characteristic zero. However we can still compute square-free decomposition of f using gf_sqf():

>>> gf_sqf_list(f, 11, ZZ)
(1, [([1, 1], 11)])

We obtained factorization f = (x + 1)**11. This is correct because:

>>> gf_pow([1, 1], 11, 11, ZZ) == f
True

References

  1. [Geddes92]
sympy.polys.galoistools.gf_Qmatrix(f, p, K)[source]

Calculate Berlekamp’s Q matrix.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_Qmatrix
>>> gf_Qmatrix([3, 2, 4], 5, ZZ)
[[1, 0],
 [3, 4]]
>>> gf_Qmatrix([1, 0, 0, 0, 1], 5, ZZ)
[[1, 0, 0, 0],
 [0, 4, 0, 0],
 [0, 0, 1, 0],
 [0, 0, 0, 4]]
sympy.polys.galoistools.gf_Qbasis(Q, p, K)[source]

Compute a basis of the kernel of Q.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_Qmatrix, gf_Qbasis
>>> gf_Qbasis(gf_Qmatrix([1, 0, 0, 0, 1], 5, ZZ), 5, ZZ)
[[1, 0, 0, 0], [0, 0, 1, 0]]
>>> gf_Qbasis(gf_Qmatrix([3, 2, 4], 5, ZZ), 5, ZZ)
[[1, 0]]
sympy.polys.galoistools.gf_berlekamp(f, p, K)[source]

Factor a square-free f in GF(p)[x] for small p.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_berlekamp
>>> gf_berlekamp([1, 0, 0, 0, 1], 5, ZZ)
[[1, 0, 2], [1, 0, 3]]
sympy.polys.galoistools.gf_zassenhaus(f, p, K)[source]

Factor a square-free f in GF(p)[x] for medium p.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_zassenhaus
>>> gf_zassenhaus([1, 4, 3], 5, ZZ)
[[1, 1], [1, 3]]
sympy.polys.galoistools.gf_shoup(f, p, K)[source]

Factor a square-free f in GF(p)[x] for large p.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_shoup
>>> gf_shoup([1, 4, 3], 5, ZZ)
[[1, 1], [1, 3]]
sympy.polys.galoistools.gf_factor_sqf(f, p, K, method=None)[source]

Factor a square-free polynomial f in GF(p)[x].

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_factor_sqf
>>> gf_factor_sqf([3, 2, 4], 5, ZZ)
(3, [[1, 1], [1, 3]])
sympy.polys.galoistools.gf_factor(f, p, K)[source]

Factor (non square-free) polynomials in GF(p)[x].

Given a possibly non square-free polynomial f in GF(p)[x], returns its complete factorization into irreducibles:

f_1(x)**e_1 f_2(x)**e_2 ... f_d(x)**e_d

where each f_i is a monic polynomial and gcd(f_i, f_j) == 1, for i != j. The result is given as a tuple consisting of the leading coefficient of f and a list of factors of f with their multiplicities.

The algorithm proceeds by first computing square-free decomposition of f and then iteratively factoring each of square-free factors.

Consider a non square-free polynomial f = (7*x + 1) (x + 2)**2 in GF(11)[x]. We obtain its factorization into irreducibles as follows:

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_factor

>>> gf_factor([5, 2, 7, 2], 11, ZZ)
(5, [([1, 2], 1), ([1, 8], 2)])

We arrived with factorization f = 5 (x + 2) (x + 8)**2. We didn’t recover the exact form of the input polynomial because we requested to get monic factors of f and its leading coefficient separately.

Square-free factors of f can be factored into irreducibles over GF(p) using three very different methods:

Berlekamp
efficient for very small values of p (usually p < 25)
Cantor-Zassenhaus
efficient on average input and with “typical” p
Shoup-Kaltofen-Gathen
efficient with very large inputs and modulus

If you want to use a specific factorization method, instead of the default one, set GF_FACTOR_METHOD with one of berlekamp, zassenhaus or shoup values.

References

  1. [Gathen99]
sympy.polys.galoistools.gf_value(f, a)[source]

Value of polynomial ‘f’ at ‘a’ in field R.

Examples

>>> from sympy.polys.galoistools import gf_value
>>> gf_value([1, 7, 2, 4], 11)
2204
sympy.polys.galoistools.gf_csolve(f, n)[source]

To solve f(x) congruent 0 mod(n).

n is divided into canonical factors and f(x) cong 0 mod(p**e) will be solved for each factor. Applying the Chinese Remainder Theorem to the results returns the final answers.

References

[1] ‘An introduction to the Theory of Numbers’ 5th Edition by Ivan Niven,
Zuckerman and Montgomery.

Examples

Solve [1, 1, 7] congruent 0 mod(189):

>>> from sympy.polys.galoistools import gf_csolve
>>> gf_csolve([1, 1, 7], 189)
[13, 49, 76, 112, 139, 175]

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. These functions carry the sdp_ prefix. As in the sdm_ case, the ground domain \(K\) and level \(u\) often have to be passed explicitly. Furthermore, sparse representations are relative to a monomial order \(O\), which also has to be passed.

sympy.polys.distributedpolys.sdp_LC(f, K)[source]

Returns the leading coeffcient of \(f\).

sympy.polys.distributedpolys.sdp_LM(f, u)[source]

Returns the leading monomial of \(f\).

sympy.polys.distributedpolys.sdp_LT(f, u, K)[source]

Returns the leading term of \(f\).

sympy.polys.distributedpolys.sdp_del_LT(f)[source]

Removes the leading from \(f\).

sympy.polys.distributedpolys.sdp_monoms(f)[source]

Returns a list of monomials in \(f\).

sympy.polys.distributedpolys.sdp_sort(f, O)[source]

Sort terms in \(f\) using the given monomial order \(O\).

sympy.polys.distributedpolys.sdp_strip(f)[source]

Remove terms with zero coefficients from \(f\) in \(K[X]\).

sympy.polys.distributedpolys.sdp_normal(f, K)[source]

Normalize distributed polynomial in the given domain.

sympy.polys.distributedpolys.sdp_from_dict(f, O)[source]

Make a distributed polynomial from a dictionary.

sympy.polys.distributedpolys.sdp_to_dict(f)[source]

Make a dictionary from a distributed polynomial.

sympy.polys.distributedpolys.sdp_indep_p(f, j, u)[source]

Returns \(True\) if a polynomial is independent of \(x_j\).

sympy.polys.distributedpolys.sdp_one_p(f, u, K)[source]

Returns True if \(f\) is a multivariate one in \(K[X]\).

sympy.polys.distributedpolys.sdp_one(u, K)[source]

Returns a multivariate one in \(K[X]\).

sympy.polys.distributedpolys.sdp_term_p(f)[source]

Returns True if \(f\) has a single term or is zero.

sympy.polys.distributedpolys.sdp_abs(f, u, O, K)[source]

Make all coefficients positive in \(K[X]\).

sympy.polys.distributedpolys.sdp_neg(f, u, O, K)[source]

Negate a polynomial in \(K[X]\).

sympy.polys.distributedpolys.sdp_add_term(f, term, u, O, K)[source]

Add a single term using bisection method.

sympy.polys.distributedpolys.sdp_sub_term(f, term, u, O, K)[source]

Sub a single term using bisection method.

sympy.polys.distributedpolys.sdp_mul_term(f, term, u, O, K)[source]

Multiply a distributed polynomial by a term.

sympy.polys.distributedpolys.sdp_add(f, g, u, O, K)[source]

Add distributed polynomials in \(K[X]\).

sympy.polys.distributedpolys.sdp_sub(f, g, u, O, K)[source]

Subtract distributed polynomials in \(K[X]\).

sympy.polys.distributedpolys.sdp_mul(f, g, u, O, K)[source]

Multiply distributed polynomials in \(K[X]\).

sympy.polys.distributedpolys.sdp_sqr(f, u, O, K)[source]

Square a distributed polynomial in \(K[X]\).

sympy.polys.distributedpolys.sdp_pow(f, n, u, O, K)[source]

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

sympy.polys.distributedpolys.sdp_monic(f, K)[source]

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

sympy.polys.distributedpolys.sdp_content(f, K)[source]

Returns GCD of coefficients in \(K[X]\).

sympy.polys.distributedpolys.sdp_primitive(f, K)[source]

Returns content and a primitive polynomial in \(K[X]\).

sympy.polys.distributedpolys.sdp_div(f, G, u, O, K)[source]

Generalized polynomial division with remainder in \(K[X]\).

Given polynomial \(f\) and a set of polynomials \(g = (g_1, ..., g_n)\) compute a set of quotients \(q = (q_1, ..., q_n)\) and remainder \(r\) such that \(f = q_1*f_1 + ... + q_n*f_n + r\), where \(r = 0\) or \(r\) is a completely reduced polynomial with respect to \(g\).

References

  1. [Cox97]
  2. [Ajwa95]
sympy.polys.distributedpolys.sdp_rem(f, G, u, O, K)[source]

Returns polynomial remainder in \(K[X]\).

sympy.polys.distributedpolys.sdp_quo(f, g, u, O, K)[source]

Returns polynomial quotient in \(K[x]\).

sympy.polys.distributedpolys.sdp_exquo(f, g, u, O, K)[source]

Returns exact polynomial quotient in \(K[X]\).

sympy.polys.distributedpolys.sdp_lcm(f, g, u, O, K)[source]

Computes LCM of two polynomials in \(K[X]\).

The LCM is computed as the unique generater of the intersection of the two ideals generated by \(f\) and \(g\). The approach is to compute a Groebner basis with respect to lexicographic ordering of \(t*f\) and \((1 - t)*g\), where \(t\) is an unrelated variable and then filtering out the solution that doesn’t contain \(t\).

References

  1. [Cox97]
sympy.polys.distributedpolys.sdp_gcd(f, g, u, O, K)[source]

Compute GCD of two polynomials in \(K[X]\) via LCM.

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, \dots\).

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)

Returns the leading coeffcient of \(f\).

sympy.polys.distributedmodules.sdm_to_dict(f)

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.

>>> 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), ((1, 0, 0), 2/1)]
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), 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/1)]

\((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), ((1, 0, 1), 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/1)
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/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), ((1, 2, 1), 6/1)]
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/1), ((0, 2, 0, 0), 1/1), ((0, 0, 2, 0), 1/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:

sympy.polys.euclidtools.dmp_half_gcdex(f, g, u, K)[source]

Half extended Euclidean algorithm in \(F[X]\).

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.euclidtools import dmp_half_gcdex
sympy.polys.euclidtools.dmp_gcdex(f, g, u, K)[source]

Extended Euclidean algorithm in \(F[X]\).

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.euclidtools import dmp_gcdex
sympy.polys.euclidtools.dmp_invert(f, g, u, K)[source]

Compute multiplicative inverse of \(f\) modulo \(g\) in \(F[X]\).

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.euclidtools import dmp_invert
sympy.polys.euclidtools.dmp_euclidean_prs(f, g, u, K)[source]

Euclidean polynomial remainder sequence (PRS) in \(K[X]\).

Examples

>>> from sympy.polys.domains import QQ
>>> from sympy.polys.euclidtools import dmp_euclidean_prs
sympy.polys.euclidtools.dmp_primitive_prs(f, g, u, K)[source]

Primitive polynomial remainder sequence (PRS) in \(K[X]\).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_primitive_prs
sympy.polys.euclidtools.dmp_inner_subresultants(f, g, u, K)[source]

Subresultant PRS algorithm in \(K[X]\).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_inner_subresultants
>>> f = ZZ.map([[3, 0], [], [-1, 0, 0, -4]])
>>> g = ZZ.map([[1], [1, 0, 0, 0], [-9]])
>>> a = [[3, 0, 0, 0, 0], [1, 0, -27, 4]]
>>> b = [[-3, 0, 0, -12, 1, 0, -54, 8, 729, -216, 16]]
>>> R = ZZ.map([f, g, a, b])
>>> B = ZZ.map([[-1], [1], [9, 0, 0, 0, 0, 0, 0, 0, 0]])
>>> D = ZZ.map([0, 1, 1])
>>> dmp_inner_subresultants(f, g, 1, ZZ) == (R, B, D)
True
sympy.polys.euclidtools.dmp_subresultants(f, g, u, K)[source]

Computes subresultant PRS of two polynomials in \(K[X]\).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_subresultants
>>> f = [[3, 0], [], [-1, 0, 0, -4]]
>>> g = [[1], [1, 0, 0, 0], [-9]]
>>> a = [[3, 0, 0, 0, 0], [1, 0, -27, 4]]
>>> b = [[-3, 0, 0, -12, 1, 0, -54, 8, 729, -216, 16]]
>>> dmp_subresultants(f, g, 1, ZZ) == [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.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_prs_resultant
>>> f = ZZ.map([[3, 0], [], [-1, 0, 0, -4]])
>>> g = ZZ.map([[1], [1, 0, 0, 0], [-9]])
>>> a = ZZ.map([[3, 0, 0, 0, 0], [1, 0, -27, 4]])
>>> b = ZZ.map([[-3, 0, 0, -12, 1, 0, -54, 8, 729, -216, 16]])
>>> dmp_prs_resultant(f, g, 1, ZZ) == (b[0], [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.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_zz_modular_resultant
>>> f = ZZ.map([[1], [1, 2]])
>>> g = ZZ.map([[2, 1], [3]])
>>> dmp_zz_modular_resultant(f, g, ZZ(5), 1, ZZ)
[-2, 0, 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.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_zz_collins_resultant
>>> f = ZZ.map([[1], [1, 2]])
>>> g = ZZ.map([[2, 1], [3]])
>>> dmp_zz_collins_resultant(f, g, 1, ZZ)
[-2, -5, 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.domains import QQ
>>> from sympy.polys.euclidtools import dmp_qq_collins_resultant
>>> f = [[QQ(1,2)], [QQ(1), QQ(2,3)]]
>>> g = [[QQ(2), QQ(1)], [QQ(3)]]
>>> dmp_qq_collins_resultant(f, g, 1, QQ)
[-2/1, -7/3, 5/6]
sympy.polys.euclidtools.dmp_resultant(f, g, u, K)[source]

Computes resultant of two polynomials in \(K[X]\).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_resultant
>>> f = ZZ.map([[3, 0], [], [-1, 0, 0, -4]])
>>> g = ZZ.map([[1], [1, 0, 0, 0], [-9]])
>>> dmp_resultant(f, g, 1, ZZ)
[-3, 0, 0, -12, 1, 0, -54, 8, 729, -216, 16]
sympy.polys.euclidtools.dmp_discriminant(f, u, K)[source]

Computes discriminant of a polynomial in \(K[X]\).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_discriminant
>>> f = ZZ.map([[[[1]], [[]]], [[[1], []]], [[[1, 0]]]])
>>> dmp_discriminant(f, 3, ZZ)
[[[-4, 0]], [[1], [], []]]
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.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_rr_prs_gcd
>>> f = ZZ.map([[1], [2, 0], [1, 0, 0]])
>>> g = ZZ.map([[1], [1, 0], []])
>>> dmp_rr_prs_gcd(f, g, 1, ZZ)
([[1], [1, 0]], [[1], [1, 0]], [[1], []])
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.domains import QQ
>>> from sympy.polys.euclidtools import dmp_ff_prs_gcd
>>> f = [[QQ(1,2)], [QQ(1), QQ(0)], [QQ(1,2), QQ(0), QQ(0)]]
>>> g = [[QQ(1)], [QQ(1), QQ(0)], []]
>>> dmp_ff_prs_gcd(f, g, 1, QQ)
([[1/1], [1/1, 0/1]], [[1/2], [1/2, 0/1]], [[1/1], []])
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 proces 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.

References

  1. [Liao95]

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_zz_heu_gcd
>>> f = ZZ.map([[1], [2, 0], [1, 0, 0]])
>>> g = ZZ.map([[1], [1, 0], []])
>>> dmp_zz_heu_gcd(f, g, 1, ZZ)
([[1], [1, 0]], [[1], [1, 0]], [[1], []])
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.domains import QQ
>>> from sympy.polys.euclidtools import dmp_qq_heu_gcd
>>> f = [[QQ(1,4)], [QQ(1), QQ(0)], [QQ(1), QQ(0), QQ(0)]]
>>> g = [[QQ(1,2)], [QQ(1), QQ(0)], []]
>>> dmp_qq_heu_gcd(f, g, 1, QQ)
([[1/1], [2/1, 0/1]], [[1/4], [1/2, 0/1]], [[1/2], []])
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.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_inner_gcd
>>> f = ZZ.map([[1], [2, 0], [1, 0, 0]])
>>> g = ZZ.map([[1], [1, 0], []])
>>> dmp_inner_gcd(f, g, 1, ZZ)
([[1], [1, 0]], [[1], [1, 0]], [[1], []])
sympy.polys.euclidtools.dmp_gcd(f, g, u, K)[source]

Computes polynomial GCD of \(f\) and \(g\) in \(K[X]\).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_gcd
>>> f = ZZ.map([[1], [2, 0], [1, 0, 0]])
>>> g = ZZ.map([[1], [1, 0], []])
>>> dmp_gcd(f, g, 1, ZZ)
[[1], [1, 0]]
sympy.polys.euclidtools.dmp_lcm(f, g, u, K)[source]

Computes polynomial LCM of \(f\) and \(g\) in \(K[X]\).

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_lcm
>>> f = ZZ.map([[1], [2, 0], [1, 0, 0]])
>>> g = ZZ.map([[1], [1, 0], []])
>>> dmp_lcm(f, g, 1, ZZ)
[[1], [2, 0], [1, 0, 0], []]
sympy.polys.euclidtools.dmp_content(f, u, K)[source]

Returns GCD of multivariate coefficients.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_content
>>> f = ZZ.map([[2, 6], [4, 12]])
>>> dmp_content(f, 1, ZZ)
[2, 6]
sympy.polys.euclidtools.dmp_primitive(f, u, K)[source]

Returns multivariate content and a primitive polynomial.

Examples

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_primitive
>>> f = ZZ.map([[2, 6], [4, 12]])
>>> dmp_primitive(f, 1, ZZ)
([2, 6], [[1], [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.domains import ZZ
>>> from sympy.polys.euclidtools import dmp_cancel
>>> f = ZZ.map([[2], [0], [-2]])
>>> g = ZZ.map([[1], [-2], [1]])
>>> dmp_cancel(f, g, 1, ZZ)
([[2], [2]], [[1], [-1]])

Polynomial factorization in characteristic zero:

sympy.polys.factortools.dmp_trial_division(f, factors, u, K)[source]

Determine multiplicities of factors 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

  1. [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

  1. [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 polnomial.

Examples

>>> from sympy.polys.factortools import dup_cyclotomic_p
>>> from sympy.polys.domains import ZZ
>>> f = [1, 0, 1, 0, 0, 0,-1, 0, 1, 0,-1, 0, 0, 0, 1, 0, 1]
>>> dup_cyclotomic_p(f, ZZ)
False
>>> g = [1, 0, 1, 0, 0, 0,-1, 0,-1, 0,-1, 0, 0, 0, 1, 0, 1]
>>> dup_cyclotomic_p(g, ZZ)
True
sympy.polys.factortools.dup_zz_cyclotomic_poly(n, K)[source]

Efficiently generate n-th cyclotomic polnomial.

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 using cyclotomic decomposition of \(f\), which makes this method much faster that any other direct factorization approach (e.g. Zassenhaus’s).

References

  1. [Weisstein09]
sympy.polys.factortools.dup_zz_factor_sqf(f, K)[source]

Factor square-free (non-primitive) polyomials 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))

Consider polynomial \(f = 2*x**4 - 2\):

>>> from sympy.polys.factortools import dup_zz_factor
>>> from sympy.polys.domains import ZZ

>>> dup_zz_factor([2, 0, 0, 0, -2], ZZ)
(2, [([1, -1], 1), ([1, 1], 1), ([1, 0, 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

  1. [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

  1. [Wang78]
  2. [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.factortools import dmp_zz_factor
>>> from sympy.polys.domains import ZZ

>>> dmp_zz_factor([[2], [], [-2, 0, 0]], 1, ZZ)
(2, [([[1], [-1, 0]], 1), ([[1], [1, 0]], 1)])

In result we got the following factorization:

f = 2 (x - y) (x + y)

References

  1. [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 polynomials into irreducibles in \(K[X]\).

sympy.polys.factortools.dmp_factor_list_include(f, u, K)[source]

Factor polynomials into irreducibles in \(K[X]\).

sympy.polys.factortools.dmp_irreducible_p(f, u, K)[source]

Returns True if 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.sdp_groebner(f, u, O, K, gens='', verbose=False, 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 setup() from sympy.polys.polyconfig, where method can be either buchberger or f5b.

sympy.polys.groebnertools.buchberger(f, u, O, K, gens='', verbose=False)[source]

Computes Groebner basis for a set of polynomials in \(K[X]\).

Given a set of multivariate polynomials \(F\), finds another set \(G\), such that Ideal \(F = Ideal G\) and \(G\) is a reduced Groebner basis.

The resulting basis is unique and has monic generators if the ground domains is a field. Otherwise the result is non-unique but Groebner bases over e.g. integers can be computed (if the input polynomials are monic).

Groebner bases can be used to choose specific generators for a polynomial ideal. Because these bases are unique you can check for ideal equality by comparing the Groebner bases. To see if one polynomial lies in an ideal, divide by the elements in the base and see if the remainder vanishes.

They can also be used to solve systems of polynomial equations as, by choosing lexicographic ordering, you can eliminate one variable at a time, provided that the ideal is zero-dimensional (finite number of solutions).

References

  1. [Bose03]
  2. [Giovini91]
  3. [Ajwa95]
  4. [Cox97]

Algorithm used: an improved version of Buchberger’s algorithm as presented in T. Becker, V. Weispfenning, Groebner Bases: A Computational Approach to Commutative Algebra, Springer, 1993, page 232.

Added optional gens argument to apply sdp_str() for the purpose of debugging the algorithm.

sympy.polys.groebnertools.sdp_spoly(p1, p2, u, O, K)[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.f5b(F, u, O, K, gens='', verbose=False)[source]

Computes a reduced Groebner basis for the ideal generated by F.

f5b is an implementation of the F5B algorithm by Yao Sun and Dingkang Wang. Similarly to Buchberger’s algorithm, the algorithm proceeds by computing critical pairs, computing the S-polynomial, reducing it and adjoining the reduced S-polynomial if it is not 0.

Unlike Buchberger’s algorithm, each polynomial contains additional information, namely a signature and a number. The signature specifies the path of computation (i.e. from which polynomial in the original basis was it derived and how), the number says when the polynomial was added to the basis. With this information it is (often) possible to decide if an S-polynomial will reduce to 0 and can be discarded.

Optimizations include: Reducing the generators before computing a Groebner basis, removing redundant critical pairs when a new polynomial enters the basis and sorting the critical pairs and the current basis.

Once a Groebner basis has been found, it gets reduced.

** References ** Yao Sun, Dingkang Wang: “A New Proof for the Correctness of F5 (F5-Like) Algorithm”, http://arxiv.org/abs/1004.0084 (specifically v4)

Thomas Becker, Volker Weispfenning, Groebner bases: A computational approach to commutative algebra, 1993, p. 203, 216

sympy.polys.groebnertools.red_groebner(G, u, O, K)[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, u, O, K)[source]

Check if G is a Groebner basis.

sympy.polys.groebnertools.is_minimal(G, u, O, K)[source]

Checks if G is a minimal Groebner basis.

sympy.polys.groebnertools.is_reduced(G, u, O, K)[source]

Checks if G is a reduced Groebner basis.

sympy.polys.groebnertools.matrix_fglm(F, u, O_from, O_to, K)[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

J.C. Faugere, P. Gianni, D. Lazard, T. Mora (1994). Efficient Computation of Zero-dimensional Groebner Bases by Change of Ordering

J.C. Faugere’s lecture notes: http://www-salsa.lip6.fr/~jcf/Papers/2010_MPRI5e.pdf

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/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, \dots, 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.

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]

Undocumented

Many parts of the polys module are still undocumented, and even where there is documentation it is scarce. Please contribute!