Types and Functions
Entry points
PolynomialRings.EntryPoints.@ring!
— Macro@ring! ℚ[x,y]
Define and return the specified polynomial ring, and bind the variable names to its generators.
Currently, the supported rings are: ℚ (Rational{BigInt}
), ℤ (BigInt
), ℝ (BigFloat
) and ℂ (Complex{BigFloat}
).
Note: @ring!
returns the ring and injects the variables. The macro @ring
only returns the ring.
If you need different coefficient rings, or need to specify a non-default monomial order or exponent integer type, use polynomial_ring
instead.
Examples
julia> using PolynomialRings
julia> @ring! ℚ[x,y];
julia> x^3 + y
x^3 + y
See also
polynomial_ring
PolynomialRings.EntryPoints.@ring
— Macro@ring ℚ[x,y]
Define and return the specified polynomial ring.
Currently, the supported rings are: ℚ (Rational{BigInt}
), ℤ (BigInt
), ℝ (BigFloat
) and ℂ (Complex{BigFloat}
).
Note: @ring!
returns the ring and injects the variables into the surrounding scope. The macro @ring
only returns the ring.
If you need different coefficient rings, or need to specify a non-default monomial order or exponent integer type, use polynomial_ring
instead.
Examples
julia> using PolynomialRings
julia> @ring ℚ[x,y]
@ring(ℚ[x,y])
See also
polynomial_ring
@ring!
PolynomialRings.EntryPoints.@polyvar
— Macro@polyvar var [var...]
Define a polynomial ring in the given variables, and inject them into the surrounding scope.
This is equivalent to @ring! Int[var...]
.
If you need different coefficient rings, or need to specify a non-default monomial order or exponent integer type, use @ring!
or polynomial_ring
instead.
Examples
julia> using PolynomialRings
julia> @polyvar x y;
julia> x + 3y
x + 3*y
julia> @polyvar ε[];
julia> 1 + ε()*x + ε()*y
ε[1]*x + ε[2]*y + 1
See also
polynomial_ring
@ring!
PolynomialRings.EntryPoints.@polynomial
— Macro@polynomial x^3 + 3x^2 + 3x + 1
Create a multi-variate polynomial from an expression by creating the ring generated by all symbols appearing in the expression.
Examples
julia> using PolynomialRings
julia> @polynomial x^3 + x^2*y + x*y^2 + y^3
x^3 + x^2*y + x*y^2 + y^3
julia> @polynomial x^3 + x^2*y + x*y^2 + y^3
x^3 + x^2*y + x*y^2 + y^3
In general, you cannot use variables from outside the macro expression; all symbols are interpreted as variables. For example:
d = 4
@polynomial d*x
will give a polynomial in two variables, d
and x
.
As a special exception, exponents are not interpreted, so
@polynomial(x^d) == @polynomial(x)^d
Unfortunately/confusingly, together, this gives
@polynomial(d*x^(d-1))
will have d-1
interpreting d
as an outer variable, and d*x
is a monomial.
This behaviour may (should?) change.
See also
@ring
, polynomial_ring
, convert(R, symbol)
PolynomialRings.EntryPoints.polynomial_ring
— Functionpolynomial_ring(symbols::Symbol...; basering=Rational{BigInt}, exptype=Int16, monomialorder=:degrevlex)
Create a type for the polynomial ring over basering
in variables with names specified by symbols
, and return the type and a tuple of these variables.
The exptype
parameter defines the integer type for the exponents.
The monomialorder
defines an order for the monomials for e.g. Gröbner basis computations; it also defines the internal sort order. Built-in values are :degrevlex
, :deglex
and :lex
. This function will accept any symbol, though, and you can define your own monomial order by implementing
Base.Order.lt(::MonomialOrder{:myorder}, a::M, b::M) where M <: AbstractMonomial
See PolynomialRings.MonomialOrderings
for examples.
Examples
julia> using PolynomialRings
julia> R,(x,y,z) = polynomial_ring(:x, :y, :z);
julia> x*y + z
x*y + z
PolynomialRings.EntryPoints.formal_coefficients
— Functionformal_coefficients(R, name::Symbol)
Return an object representing formal coefficients for the polynomial ring R
.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x];
julia> c = formal_coefficients(R, :c);
julia> c[1:3]
3-element Array{@ring(ℤ[c[]][x]),1}:
c[1]
c[2]
c[3]
julia> [c()*x^2 + c()*x + c() , c()*x^2 + c()*x + c()]
2-element Array{@ring(ℤ[c[]][x]),1}:
c[1]*x^2 + c[2]*x + c[3]
c[4]*x^2 + c[5]*x + c[6]
Arithmetic
Base.rem
— Functionf_red = rem(f, G)
Return the multivariate reduction of a polynomial f
by a vector of polynomials G
. By definition, this means that no leading term of a polynomial in G
divides any monomial in f
, and f_red + factors * G == f
for some factors.
If you need to obtain the vector of factors, use divrem
instead.
Examples
In one variable, this is just the normal Euclidean algorithm:
julia> using PolynomialRings
julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});
julia> rem(x^2 + 1, [x-im])
0
julia> rem(x^2 + y^2 + 1, [x, y])
1 + 0im
Base.divrem
— Functionfactors, f_red = divrem(f, G)
Return the multivariate reduction of a polynomial f
by a vector of polynomials G
, together with row vector of factors. By definition, this means that no leading term of a polynomial in G
divides any monomial in f
, and f_red + factors * G == f
.
Examples
In one variable, this is just the normal Euclidean algorithm:
julia> using PolynomialRings
julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});
julia> divrem(x^2 + 1, [x-im])
(@ring(Complex{Int64}[x,y])[x + 0 + 1im], 0)
julia> divrem(x^2 + y^2 + 1, [x, y])
(@ring(Complex{Int64}[x,y])[x y], 1 + 0im)
Base.diff
— Functiondiff(polynomial, variable)
Return the derivative of polynomial
w.r.t. variable
.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> diff(x^3, :x)
3*x^2
julia> diff(x^3, :y)
0
PolynomialRings.div!
— Functionfactors = div!(f, G)
Compute the multivariate reduction of a polynomial f
by a vector of polynomials G
, in-place. By definition, this means that after applying rem!
no, leading term of a polynomial in G
divides any monomial in f
, and f + factors * G
is equal to the original value of f
.
The return value is nothing
if no reduction has taken place. This situation could also be represented by the zero vector, but we choose nothing
for efficiency.
If you want to allow clearing denominators, e.g. reduce 2x^2
by 3x
even though your base ring is ℤ, use xdiv!
instead.
Examples
In one variable, this is just the normal Euclidean algorithm:
julia> using PolynomialRings
julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});
julia> f = x^2 + 1 + 0im
x^2 + 1 + 0im
julia> collect(div!(f, [x-im]))
1×1 Array{@ring(Complex{Int64}[x,y]),2}:
x + 0 + 1im
julia> f
0
julia> g = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im
julia> collect(div!(g, [x, y]))
1×2 Array{@ring(Complex{Int64}[x,y]),2}:
x y
julia> g
1 + 0im
PolynomialRings.rem!
— Functionany_reductions = rem!(f, G)
Compute the multivariate reduction of a polynomial f
by a vector of polynomials G
, in-place. By definition, this means that after applying rem!
no, leading term of a polynomial in G
divides any monomial in f
, and f + factors * G
is equal to the original value of f
for some row vector factors
.
The return value any_reductions
is true
if and only if factors
is nonzero. Note that factors
itself is not actually computed and not returned. If you need to obtain it, use div!
.
If you want to allow clearing denominators, e.g. reduce 2x^2
by 3x
even though your base ring is ℤ, use xrem!
instead.
Examples
In one variable, this is just the normal Euclidean algorithm:
julia> using PolynomialRings
julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});
julia> f = x^2 + 1
x^2 + 1 + 0im
julia> rem!(f, [x-im])
true
julia> f
0
julia> g = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im
julia> rem!(g, [x, y])
true
julia> g
1 + 0im
PolynomialRings.xrem
— Functionf_red = xrem(f, G)
Return the multivariate reduction of a polynomial f
by a vector of polynomials G
. By definition, this means that no leading term of a polynomial in G
divides any monomial in f
, and f_red + factors * G == m * f
for some factors and for some integer m
.
If you need to obtain the vector of factors, use xdivrem
instead.
Examples
In one variable, this is just the normal Euclidean algorithm:
julia> using PolynomialRings
julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});
julia> xrem(x^2 + 1, [x-im])
0
julia> xrem(x^2 + y^2 + 1, [x, y])
1 + 0im
PolynomialRings.xdiv!
— Functionm, factors = xdiv!(f, G)
Compute the multivariate reduction of a polynomial f
by a vector of polynomials G
, in-place. By definition, this means that after applying rem!
no, leading term of a polynomial in G
divides any monomial in f
, and f + factors * G
is equal to m
times the original value of f
.
The difference between xdiv!
and div
is that the former allows clearing denominators, e.g. reduce 2x^2
by 3x
even when the base ring is ℤ.
Examples
In one variable, this is just the normal Euclidean algorithm:
julia> using PolynomialRings
julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});
julia> f = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im
julia> xdiv!(f, [x-im])
(1 + 0im, @ring(Complex{Int64}[x,y])[x + 0 + 1im])
julia> f
y^2
julia> g = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im
julia> xdiv!(g, [x, y])
(1 + 0im, @ring(Complex{Int64}[x,y])[x y])
julia> g
1 + 0im
PolynomialRings.xrem!
— Functionany_reductions = xrem!(f, G)
Compute the multivariate reduction of a polynomial f
by a vector of polynomials G
, in-place. By definition, this means that after applying rem!
no, leading term of a polynomial in G
divides any monomial in f
, and f + factors * G
is equal to m
times the original value of f
for some scalar m
and for some row vector factors
.
The return value any_reductions
is true
if and only if factors
is nonzero. Note that factors
itself is not actually computed and not returned. If you need to obtain it, use xdiv!
. The same holds for m
.
The difference between xdiv!
and div
is that the former allows clearing denominators, e.g. reduce 2x^2
by 3x
even when the base ring is ℤ.
Examples
In one variable, this is just the normal Euclidean algorithm:
julia> using PolynomialRings
julia> R,(x,y) = polynomial_ring(:x, :y, basering=Complex{Int});
julia> f = x^2 + 1
x^2 + 1 + 0im
julia> xrem!(f, [x-im])
true
julia> f
0
julia> g = x^2 + y^2 + 1
x^2 + y^2 + 1 + 0im
julia> xrem!(g, [x, y])
true
julia> g
1 + 0im
PolynomialRings.Polynomials.map_coefficients
— Functionp = map_coefficients(f, q)
Apply a function f
to all coefficients of q
, and return the result.
Monomial orderings
PolynomialRings.MonomialOrderings.MonomialOrder
— Typeabstract type MonomialOrder{Names} <: Base.Order.Ordering end
Represents a total order between monomials.
Expansions, coefficients, collecting monomials
PolynomialRings.Expansions.@expansion
— Macro@expansion(f, var, [var...])
Return a collection of (monomial, coefficient) tuples decomposing f into its consituent parts.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> collect(@expand(x^3 + y^2, y))
2-element Array{Tuple{Tuple{Int16},@ring(ℤ[x])},1}:
((0,), x^3)
((2,), 1)
julia> collect(@expand(x^3 + y^2, x, y))
2-element Array{Tuple{Tuple{Int16,Int16},BigInt},1}:
((0, 2), 1)
((3, 0), 1)
See also
expansion(...)
, @coefficient
and coefficient
PolynomialRings.expansion
— Functionexpansion(f, symbol, [symbol...])
Return a collection of (monomial, coefficient) tuples decomposing f into its consituent parts.
In the REPL, you likely want to use the friendlier version @expansion
instead.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> collect(expansion(x^3 + y^2, :y))
2-element Array{(Term over @ring(ℤ[x]) in @degrevlex(y)),1}:
x^3
y^2
julia> collect(expansion(x^3 + y^2, :x, :y))
2-element Array{(Term over BigInt in @degrevlex(x > y)),1}:
y^2
x^3
See also
@expansion(...)
, @coefficient
and coefficient
PolynomialRings.Expansions.@expand
— Macro@expand(f, var, [var...])
Return a collection of (exponent tuple, coefficient) tuples decomposing f into its consituent parts.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> collect(@expand(x^3 + y^2, y))
2-element Array{Tuple{Tuple{Int16},@ring(ℤ[x])},1}:
((0,), x^3)
((2,), 1)
julia> collect(@expand(x^3 + y^2, x, y))
2-element Array{Tuple{Tuple{Int16,Int16},BigInt},1}:
((0, 2), 1)
((3, 0), 1)
See also
@expansion
, expand(...)
, @coefficient
and coefficient
PolynomialRings.Expansions.@coefficient
— Macro@coefficient(f, monomial)
Return a the coefficient of f
at monomial
.
monomial
needs to be a literal monomial; it cannot be a variable containing a monomial. This macro has a rather naive parser that gets exponents and variable names from monomial
.
This is considered a feature (not a bug) because it is only as a literal monomial that we can distinguish e.g. x^4
from x^4*y^0
.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> @coefficient(x^3*y + x, x)
1
julia> @coefficient(x^3*y + x, x^3)
y
julia> @coefficient(x^3*y + x, x^3*y^0)
0
julia> @coefficient(x^3*y + x, x^3*y^1)
1
See also
coefficient
, expansion
and @expansion
PolynomialRings.Terms.coefficient
— Functioncoefficient(f, exponent_tuple, symbol, [symbol...])
Return a the coefficient of f at monomial. In the REPL, you likely want to use the friendlier version @coefficient
.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> coefficient(x^3*y + x, (1,), :x)
1
julia> coefficient(x^3*y + x, (3,), :x)
y
julia> coefficient(x^3*y + x, (3,0), :x, :y)
0
julia> coefficient(x^3*y + x, (3,1), :x, :y)
1
See also
@coefficient
, expansion
and @expansion
PolynomialRings.Expansions.@expandcoefficients
— Macro@expandcoefficients(f, vars...)
Return the coefficients of f
when expanded as a polynomial in the given variables.
vars
need to be literal variable names; it cannot be a variable containing it.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> collect(@expandcoefficients(x^3 + y^2, y))
2-element Array{@ring(ℤ[x]),1}:
x^3
1
julia> collect(@expandcoefficients(x^3 + y^2, x, y))
2-element Array{BigInt,1}:
1
1
See also
expandcoefficients
, @expansion
, expansion
, @coefficient
and coefficient
PolynomialRings.Expansions.expandcoefficients
— Functionexpandcoefficients(f, symbol, [symbol...])
Return the coefficients of f
when expanded as a polynomial in the given variables.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> collect(expandcoefficients(x^3 + y^2, :y))
2-element Array{@ring(ℤ[x]),1}:
x^3
1
julia> collect(expandcoefficients(x^3 + y^2, :x, :y))
2-element Array{BigInt,1}:
1
1
See also
@expandcoefficients
, @expansion
, expansion
, @coefficient
and coefficient
PolynomialRings.Expansions.@deg
— Macro@deg(f, vars...)
Return the total degree of f
when expanded as a polynomial in the given variables.
vars
need to be literal variable names; it cannot be a variable containing it.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> @deg (x^2 + x*y - 1) x
2
julia> @deg (x^2 + x*y - 1) y
1
See also
deg
, @expansion
PolynomialRings.deg
— Functiondeg(f, vars...)
Return the total degree of f
when regarded as a polynomial in vars
. Returns -1 for the zero polynomial.
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> deg(x^2, :x)
2
julia> deg(x^2, :x, :y)
2
julia> deg(x^2, :y)
0
PolynomialRings.Expansions.@linear_coefficients
— Macro@linear_coefficient(f, vars...)
linear_coefficients(f, vars...)
Return the linear coefficients of f
as a function of vars
.
vars
need to be symbols; e.g. they cannot be the polynomial x
.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> @linear_coefficients(x^3*y + x + y + 1, x)
1-element Array{@ring(ℤ[y]),1}:
1
julia> @linear_coefficients(x^3*y + x + y + 1, x, y)
2-element Array{BigInt,1}:
1
1
See also
@constant_coefficient
, @coefficient
, and @expansion
PolynomialRings.Expansions.linear_coefficients
— Functionlinear_coefficients(f, vars...)
Return the linear coefficients of f
as a function of vars
.
vars
need to be symbols; e.g. they cannot be the polynomial x
.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> linear_coefficients(x^3*y + x + y + 1, :x)
1-element Array{@ring(ℤ[y]),1}:
1
julia> linear_coefficients(x^3*y + x + y + 1, :x, :y)
2-element Array{BigInt,1}:
1
1
See also
@constant_coefficient
, @coefficient
, and @expansion
PolynomialRings.Expansions.@constant_coefficient
— Macro@constant_coefficient(f, vars...)
Return the constant coefficient of f
as a function of vars
.
vars
need to be literal variable names; it cannot be a variable containing it.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> @constant_coefficient(x^3*y + x + y + 1, x)
y + 1
julia> @constant_coefficient(x^3*y + x + y + 1, x, y)
1
See also
constant_coefficient
, @coefficient
, and @expansion
PolynomialRings.Expansions.constant_coefficient
— Functionconstant_coefficient(f, vars...)
Return the constant coefficient of f
as a function of vars
.
vars
need to be symbols; e.g. they cannot be the polynomial x
.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> constant_coefficient(x^3*y + x + y + 1, :x)
y + 1
julia> constant_coefficient(x^3*y + x + y + 1, :x, :y)
1
See also
@constant_coefficient
, @coefficient
, and @expansion
PolynomialRings.Arrays.@flat_coefficients
— Macro@flat_coefficients(a, var, [var...])
Return the polynomial coefficients of the matrix coefficients of a
, when those matrix coefficients are regarded as polynomials in the given variables.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> collect(flat_coefficients([x^3 + y^2; y^5], :y))
3-element Array{@ring(ℤ[x]),1}:
1
x^3
1
julia> collect(flat_coefficients([x^3 + y^2, y^5], :x, :y))
3-element Array{BigInt,1}:
1
1
1
See also
flat_coefficients
, @expansion
, expansion
, @coefficient
and coefficient
PolynomialRings.Arrays.flat_coefficients
— Functionflat_coefficients(a, symbol, [symbol...])
Return the polynomial coefficients of the matrix coefficients of a
, when those matrix coefficients are regarded as polynomials in the given variables.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> collect(flat_coefficients([x^3 + y^2; y^5], :y))
3-element Array{@ring(ℤ[x]),1}:
1
x^3
1
julia> collect(flat_coefficients([x^3 + y^2, y^5], :x, :y))
3-element Array{BigInt,1}:
1
1
1
See also
@expandcoefficients
, @expansion
, expansion
, @coefficient
and coefficient
Gröbner basis computations
PolynomialRings.gröbner_basis
— Functionbasis = gröbner_basis(polynomials)
Return a Gröbner basis for the ideal generated by polynomials
.
This is computed using the GWV algorithm; see PolynomialRings.GröbnerGWV.gwv
for details.
PolynomialRings.gröbner_transformation
— Functionbasis, transformation = gröbner_transformation(polynomials)
Return a Gröbner basis for the ideal generated by polynomials
, together with a transformation
that proves that each element in basis
is in that ideal (i.e. basis == transformation * polynomials
).
This is computed using the GWV algorithm with a few standard optmizations; see PolynomialRings.GröbnerGWV.gwv
for details.
PolynomialRings.syzygies
— Functionsyz = syzygies(G)
Return all relations between the elements of G.
Examples
julia> using PolynomialRings
julia> R = @ring! ℤ[x,y];
julia> I = [x^5, x^2 + y, x*y + y^2];
julia> G, tr = gröbner_transformation(I);
julia> K = syzygies(G) * tr; # the kernel of the map R^3 -> I induced by these generators
julia> iszero(K * I)
true
PolynomialRings.lift
— Functionfactors = lift(polynomials, y)
Return a row vector of factors
such that factors * polynomials
is equal to y
, or nothing
if y
is not in the ideal generated by polynomials
.
This is computed using gröbner_transformation
; see there for more information.
Note: if you need to compute many lifts for the same set of polynomials
, it is beneficial to use gröbner_transformation
yourself as it avoids re-doing the most computationally intensive part.
PolynomialRings.Solve.matrix_solve_affine
— Functionx = matrix_solve_affine(f, y, dims, Type=eltype(y))
Return the solution x
to the equation
``f(x) = y``
where $x$ is assumed to be a matrix of size dims
, and f
is assumed to be a linear map over Type
.
Note: I haven't really considered the proper semantics when type(x) is not necessarily equal to type(y), and the behaviour of this function may (will) change when I do.
PolynomialRings.GröbnerGWV.gwv
— Functiongröbner_basis = gwv(monomialorder, polynomials)
An implementation of the GWV algorithm as popularized by
Shuhong Gao, Frank Volny, and Mingsheng Wang. "A new algorithm for computing Groebner bases." IACR Cryptology ePrint Archive 2010 (2010): 641.
Internal types and functions
PolynomialRings.AbstractMonomials.AbstractMonomial
— TypeAbstractMonomial{Order}
The abstract base type for multi-variate monomials.
Specifying a monomial is equivalent to specifying the exponents for all variables. The concrete type decides whether this happens as a tuple or as a (sparse or dense) array.
The type also encodes the monomial order, and as part of that, the names of the variables.
Each concrete implementation M
should implement for elements m
:
exp(M, exponents, deg=sum(exponents))
exponents(scheme::NamingScheme, m::M)
exptype(M)
In addition, one may choose to add specific optimizations by overloading other functions, as well.
PolynomialRings.Monomials.TupleMonomials.TupleMonomial
— TypeTupleMonomial{N, I, Order} <: AbstractMonomial where I <: Integer where Order
An implementation of AbstractMonomial that stores exponents as a tuple of integers. This is a dense representation.
PolynomialRings.Monomials.VectorMonomials.VectorMonomial
— TypeVectorMonomial{V,I,Order} <: AbstractMonomial where V <: AbstractVector{I} where I <: Integer where Order
An implementation of AbstractMonomial that stores exponents as a vector of integers. This can be a sparse or dense representation, depending on the type specialization.
This representation is intended for the case when the number of variables is unbounded. In particular, the indexing operation m[i]
returns 0
when i
is out-of-bounds, instead of throwing an exception.
Missing docstring for PolynomialRings.Monomials.enumeratenz
. Check Documenter's build log for details.
PolynomialRings.Terms.Term
— TypeTerm{M, C} where M <: AbstractMonomial where C
This type represents a single term of a multivariate polynomial: that is, it represents the combination of a coefficient and a monomial.
PolynomialRings.Polynomials.Polynomial
— Typef(var1=...,var2=...)
Substitute variables with Numbers