Multivariate polynomials

Singular.jl allows the creation of multivariate polynomials over any of the coefficient rings described above.

The default multivariate polynomial type in Singular.jl is the Singular spoly type.

The associated polynomial ring is represented by a parent object which can be constructed by a call to the polynomial_ring constructor.

The types of the polynomial ring parent objects and elements thereof are given in the following table according to the library providing them.

LibraryElement typeParent type
Singularspoly{T}Singular.PolyRing{T}

These types are parameterised by the type of elements in the coefficient ring of the polynomials.

All polynomial types belong directly to the abstract type MPolyRingElem and all the polynomial ring parent object types belong to the abstract type MPolyRing.

Multivariate polynomial functionality

Singular.jl polynomials provides all the Multivariate Polynomial Ring functionality described by AbstractAlgebra.jl.

https://nemocas.github.io/AbstractAlgebra.jl/latest/mpolynomial

In particular, Singular polynomials are sparse distributed, but do not have random access. Instead, they implement iterator access to terms. This is due to their storage in a linked list, for efficient implementation of Groebner basis algorithms.

Some polynomial rings may also implement part of the Euclidean Ring interface, where this is appropriate.

https://nemocas.github.io/AbstractAlgebra.jl/latest/euclidean_interface

Below, we describe the functionality that is specific to the Singular multivariate polynomials that is not documented in the general multivariate interface.

Constructors

polynomial_ring(R::Union{Ring, Field}, s::AbstractVector{<:VarName};
               cached::Bool = true, ordering = :degrevlex,
               ordering2::Symbol = :comp1min, degree_bound::Int = 0)

Returns a tuple, $S, x$ consisting of a multivariate polynomial ring $S$ and an array $x$ of variables (from which polynomials can be constructed). The ring $R$ must be a valid Singular coefficient ring, or any Nemo/AbstractAlgebra coefficient ring. The array $s$ must be a list of strings corresponding to how the variables will be printed. By default, there will only be one Singular polynomial ring in the system for each combination of coefficient ring, list of variable names, ordering and degree bound. This is accomplished by making use of a global cache. If this is not the desired behaviour, false can be passed to the optional argument cached.

If the first ordering ordering is specified as a symbol, then two orderings can be specified, one for term ordering of the polynomials, and another for ordering of module components. They can occur in either order, the first taking precedence over the other, when the polynomials are used to represent module generators. If either is not specified, the indicated default is used. The options for polynomial term ordering are, :lex, :deglex, :degrevlex, :neglex, :negdeglex and :negdegrevlex, and the options for module component ordering are comp1min and comp1max.

If the first ordering ordering is specified as a non-symbol, the second ordering ordering2 will be ignored. For specifying non-symbolic term orderings, please see the Term orderings section below.

If one has an a priori bound on the degree in each variable of a polynomial (including for all intermediate computations in this ring), one can specify it using the degree_bound optional parameter. Singular may then be able to use a more efficient representation internally, which will use less memory and allow for faster arithmetic. By default, Singular uses a bound of 16 bits internally for the exponent of each variable, however this is a signed value, so that the default is for nonnegative exponents that fit in 15 bits.

Note that internally, Singular may use a higher bound than specified, if it will not increase the amount of storage required.

Examples

julia> R, (x, y, z) = polynomial_ring(ZZ, ["x", "y", "z"])
(Singular polynomial ring (ZZ),(x,y,z),(dp(3),C), spoly{n_Z}[x, y, z])

julia> S, vars = polynomial_ring(QQ, ["x", "y"]; ordering=:deglex)
(Singular polynomial ring (QQ),(x,y),(Dp(2),C), spoly{n_Q}[x, y])

julia> T, x = polynomial_ring(ZZ, ["x$i" for i in 1:5];
              ordering=:comp1max, ordering2=:degrevlex, degree_bound=5)
(Singular polynomial ring (ZZ),(x1,x2,x3,x4,x5),(c,dp(5),L(5)), spoly{n_Z}[x1, x2, x3, x4, x5])

See also the convenience macros below for simple use cases.

The following function allows creating a Singular polynomial ring from a given polynomial ring of type AbstractAlgebra.Generic.MPolyRing:

polynomial_ring(R::AbstractAlgebra.Generic.MPolyRing{T}; cached::Bool = true, ordering::Symbol = :degrevlex, ordering2::Symbol = :comp1min, degree_bound::Int = 0)  where {T <: RingElement}

Polynomials can be constructed using arithmetic operations on the generators, but this can be extremely inefficient. For this purpose, Singular polynomials support construction using a build context, as described in the AbstractAlgebra documentation:

https://nemocas.github.io/AbstractAlgebra.jl/latest/mpolynomial

Examples

julia> R, (x, y) = polynomial_ring(ZZ, ["x", "y"])
(Singular polynomial ring (ZZ),(x,y),(dp(2),C), spoly{n_Z}[x, y])

julia> C = MPolyBuildCtx(R)
Builder for an element of Singular polynomial ring (ZZ),(x,y),(dp(2),C)

julia> push_term!(C, ZZ(1), [1, 2])
x*y^2

julia> push_term!(C, ZZ(3), [1, 1])
x*y^2 + 3*x*y

julia> push_term!(C, -ZZ(1), [0, 1])
x*y^2 + 3*x*y - y

julia> f = finish(C)
x*y^2 + 3*x*y - y

Term orderings

A general term ordering can be constructed as a product of one or more of the following block orderings.

Singular.ordering_lpFunction
ordering_lp(nvars::Int = 1)

Represents a block of at least nvars variables with the lexicographical ordering (:lex) (the Singular ordering lp).

source
Singular.ordering_ipFunction
ordering_ip(nvars::Int = 1)

Represents a block of at least nvars variables with the Singular ordering ip. This stands for what the Singular manual refers to as "reverse lexicographical ordering" (and is elsewhere sometimes called "inverse lexicographical ordering), i.e. a lexicographical ordering from the right with 1 < x_1 < ... <x_n.

Note that this reverses the "natural" order x_1 > ... > x_n.

source
Singular.ordering_rpFunction
ordering_rp(nvars::Int = 1)

Represents a block of at least nvars variables with the inverse lexicographical ordering (:invlex) (the Singular ordering ip).

Note that this reverses the "natural" order x_1 > ... > x_n.

source
Singular.ordering_dpFunction
ordering_dp(nvars::Int = 1)

Represents a block of at least nvars variables with the degree reverse lexicographical ordering (:degrevlex) (the Singular ordering dp).

source
Singular.ordering_DpFunction
ordering_Dp(nvars::Int = 1)

Represents a block of at least nvars variables with the degree lexicographical ordering (:deglex) (the Singular ordering Dp).

source
Singular.ordering_wpMethod
ordering_wp(w::Vector{Int})

Represents a block of variables with the weighted reverse lexicographical ordering. The weight vector w is expected to consist of positive integers only. (the Singular ordering wp).

source
Singular.ordering_WpMethod
ordering_Wp(w::Vector{Int})

Represents a block of variables with the weighted lexicographical ordering. The weight vector is expected to consist of positive integers only. (the Singular ordering Wp).

source
Singular.ordering_IpFunction
ordering_Ip(nvars::Int = 1)

Represents a block of at least nvars variables with the degree inverse lexicographical ordering (:deginvlex) (the Singular ordering Ip).

Note that this reverses the "natural" order x_1 > ... > x_n.

source
Singular.ordering_lsFunction
ordering_ls(nvars::Int = 1)

Represents a block of at least nvars variables with the negative lexicographical ordering (:neglex) (the Singular ordering ls).

source
Singular.ordering_isFunction
ordering_is(nvars::Int = 1)

Represents a block of at least nvars variables with the negative inverse lexicographical ordering (:neginvlex) (the Singular ordering is)

Note that this reverses the "natural" order x_1 > ... > x_n.

source
Singular.ordering_rsFunction
ordering_rs(nvars::Int = 1)

Represents a block of at least nvars variables with the negative inverse lexicographical ordering (:neginvlex) (the Singular ordering is)

Note that this reverses the "natural" order x_1 > ... > x_n.

source
Singular.ordering_dsFunction
ordering_ds(nvars::Int = 1)

Represents a block of at least nvars variables with the negative degree reverse lexicographical ordering (:negdegrevlex) (the Singular ordering ds).

source
Singular.ordering_DsFunction
ordering_Ds(nvars::Int = 1)

Represents a block of at least nvars variables with the negative degree reverse lexicographical ordering (:negdeglex). (the Singular ordering Ds).

source
Singular.ordering_wsMethod
ordering_ws(w::Vector{Int})

Represents a block of variables with the general weighted reverse lexicographical ordering. The weight vector w is expected to have a nonzero first entry. (the Singular ordering ws).

source
Singular.ordering_WsMethod
ordering_Ws(w::Vector{Int})

Represents a block of variables with the general weighted lexicographical ordering. The weight vector w is expected to have a nonzero first entry. (the Singular ordering Ws).

source
Singular.ordering_aMethod
ordering_a(w::Vector{Int})

Represents an extra weight vector that may precede any monomial ordering. An extra weight vector does not define a monomial ordering by itself: it can only be used in combination with other orderings to insert an extra line of weights into the ordering matrix. (the Singular ordering a).

source
Singular.ordering_MMethod
ordering_M(m::Matrix{Int}; checked::Bool = true)

Represents a block of variables with a general matrix ordering. The matrix m is expected to be invertible, and this is checked by default. (the Singular ordering M).

source
Singular.ordering_CMethod
ordering_C()

Represents an ascending ordering on vector components gen(1) < gen(2) < .... All monomial block orderings preceding the component ordering have higher precedence, and all succeeding monomial block orderings have lower precedence. It is not necessary to specify this ordering explicitly since it appended automatically to an ordering lacking a component specification. (the Singular ordering C).

source
Singular.ordering_cMethod
ordering_c()

Represents a descending ordering on vector components gen(1) > gen(2) > .... All monomial block orderings preceding the component ordering have higher precedence, and all succeeding monomial block orderings have lower precedence. (the Singular ordering c).

source

Examples

polynomial_ring(QQ, "x".*string.(1:8), ordering = ordering_M([1 2; 3 5])*ordering_lp(3)*ordering_wp([1, 2, 3]))

polynomial_ring(QQ, "x".*string.(1:5), ordering = ordering_dp(3)*ordering_dp())

Polynomial ring macros

For convenience, we provide some macros for constructing polynomial rings and injecting the variables into scope. These are easier to use, but have some limitations. In particular, they can only be used at the top level by the user, and cannot be used programmatically or in library code (it is not possible to inject an arbitrary number of variables into scope inside a function).

The macros are designed for simple use cases, and do not offer the full power of the most general constructor above.

@polynomial_ring(R, s, n, o)

Given a coefficient ring $R$, a root variable name, e.g. "x", a number of variable $n$ and a polynomial term ordering o, create the variables x1, x2, ..., xn and inject them into scope, and return the corresponding polynomial ring S.

@polynomial_ring(R, s, n)

As per the previous macro, with a default of :degrevlex for the polynomial term ordering.

Examples

julia> S = @polynomial_ring(ZZ, "x", 5, :deglex)
Singular polynomial ring (ZZ),(x1,x2,x3,x4,x5),(Dp(5),C)

julia> T = @polynomial_ring(QQ, "y", 10)
Singular polynomial ring (QQ),(y1,y2,y3,y4,y5,y6,y7,y8,y9,y10),(dp(10),C)

Basic manipulation

Singular.has_global_orderingMethod
has_global_ordering(R::PolyRingUnion)

Return true if the given ring has a global ordering, i.e. if $1 < x$ for each variable $x$ in the ring. This include :lex, :deglex and :degrevlex orderings.

source
Singular.has_mixed_orderingMethod
has_mixed_ordering(R::PolyRingUnion)

Return true if the given ring has a mixed ordering, i.e. if $1 < x_i$ for a variable $x_i$ and $1>x_j$ for another variable $x_j$.

source
Singular.has_local_orderingMethod
has_local_ordering(R::PolyRingUnion)

Return true if the given ring has a local ordering, i.e. if $1 > x$ for all variables $x$.

source
Singular.degree_boundMethod
degree_bound(R::PolyRing)

Return the internal degree bound in each variable, enforced by Singular. This is the largest positive value any degree can have before an overflow will occur. This internal bound may be higher than the bound requested by the user via the degree_bound parameter of the polynomial_ring constructor.

source

Examples

julia> R = @polynomial_ring(ZZ, "x", 3)
Singular polynomial ring (ZZ),(x1,x2,x3),(dp(3),C)

julia> n = nvars(R)
3

julia> has_global_ordering(R) == true
true

julia> c = characteristic(R)
0

julia> L = degree_bound(R)
1048575

julia> exps = leading_exponent_vector(x1*x2 + 3x1*x2^2 + x3 + 2)
3-element Vector{Int64}:
 1
 2
 0

julia> deg = total_degree(x1*x2 + 3x1*x2^2 + x3 + 2)
3

julia> ord = order(x1*x2 + 3x1*x2^2 + x3 + 2)
0

Differential functions

Working over any coefficient ring, basic functionality involving differential operations is available.

Singular.jetMethod
jet(x::spoly{T}, n::Int) where T <: Nemo.RingElem

Return the truncation of $x$ up to degree $n$.

source
AbstractAlgebra.derivativeMethod
derivative(x::spoly{T}, n::Int) where T <: Nemo.RingElem

Return the derivative of $x$ with respect to the variable of index $n$.

source
AbstractAlgebra.derivativeMethod
derivative(x::spoly{T}, v::spoly{T}) where T <: Nemo.RingElem

Return the derivative of $x$ with respect to the variable $v$.

source
Singular.jacobian_idealMethod
jacobian_ideal(p::spoly{T}) where T <: Nemo.RingElem

Return the ideal generated by all partial derivatives of $x$.

source
Singular.jacobian_matrixMethod
jacobian_matrix(p::spoly{T}) where T <: Nemo.RingElem

Return the column matrix $\{\frac{\partial p}{\partial x_i}\}_i$ of partial derivatives.

source
Singular.jacobian_matrixMethod
jacobian_matrix(a::Vector{spoly{T}}) where T <: Nemo.RingElem

Return the matrix $\{\frac{\partial a_i}{\partial x_j}\}_{ij}$ of partial derivatives.

source

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Singular polynomial ring (QQ),(x,y,z),(dp(3),C), spoly{n_Q}[x, y, z])

julia> f = x^2*y*z + z^2*x + x*y*z
x^2*y*z + x*y*z + x*z^2

julia> g = jet(f, 3)
x*y*z + x*z^2

julia> derivative(f, 1)
2*x*y*z + y*z + z^2

julia> derivative(f, y)
x^2*z + x*z

julia> J = jacobian_ideal(f)
Singular ideal over Singular polynomial ring (QQ),(x,y,z),(dp(3),C) with generators (2*x*y*z + y*z + z^2, x^2*z + x*z, x^2*y + x*y + 2*x*z)

julia> Jf1 = jacobian_matrix(f)
[2*x*y*z + y*z + z^2
x^2*z + x*z
x^2*y + x*y + 2*x*z]

julia> Jf2 = jacobian_matrix([f, g])
[2*x*y*z + y*z + z^2, x^2*z + x*z, x^2*y + x*y + 2*x*z
y*z + z^2, x*z, x*y + 2*x*z]

Content and primitive part

When coefficient rings have a meaningful GCD function, the following functions are available.

AbstractAlgebra.primpartMethod
primpart(x::SPolyUnion)

Return the primitive part of the polynomial, i.e. the polynomial divided by the GCD of its coefficients.

source

Examples

julia> R = @polynomial_ring(ZZ, "x", 2)
Singular polynomial ring (ZZ),(x1,x2),(dp(2),C)

julia> f = 3x1^2 + 3x1*x2 + 6x2^2
3*x1^2 + 3*x1*x2 + 6*x2^2

julia> p = primpart(f)
x1^2 + x1*x2 + 2*x2^2

julia> c = content(f)
3

Homogeneous polynomials

Singular.homogenizeMethod
homogenize(p::spoly{T}, v::spoly{T}) where T <: Nemo.RingElem

Multiply each monomial in p by a suitable power of the variable v and return the corresponding homogeneous polynomial. The variable v must have weight 1.

source

Multivariate Factorisation

For the Singular base fields QQ and Fp a function to compute a squarefree factorization is available.

Examples

julia> R = @polynomial_ring(QQ, "x", 4)
Singular Polynomial Ring (QQ),(x1,x2,x3,x4),(dp(4),C)

julia> f = 123*(57*x2^3 + x4^5)^3*(x1^2 + x1+1)^2*(x1 + x2*x3)^2;

julia> Fac = factor(f)
123 * (x4^5 + 57*x2^3)^3 * (x1^2 + x1 + 1)^2 * (x2*x3 + x1)^2

For the Singular base rings QQ, ZZ and Fp a function to compute the multivariate factorization is available.

Examples

julia> R = @polynomial_ring(ZZ, "x", 4)
Singular Polynomial Ring (ZZ),(x1,x2,x3,x4),(dp(4),C)

julia> f = 123*(57*x2^3 + x4^5)^3*(x1^2 + x1+1)^2*(x1 + x2*x3)^2;

julia> Fac = factor(f)
123 * (x2*x3 + x1)^2 * (x4^5 + 57*x2^3)^3 * (x1^2 + x1 + 1)^2

Change of coefficient rings

It is possible to change the coefficient ring of a given polynomial $p$ via the function 'changebasering'.

Examples

julia> R, (x, y) = polynomial_ring(ZZ, ["x", "y"])
(Singular polynomial ring (ZZ),(x,y),(dp(2),C), spoly{n_Z}[x, y])

julia> p = x^5 + y^3+1
x^5 + y^3 + 1

julia> p2 = change_base_ring(QQ, p)
x^5 + y^3 + 1

julia> parent(p2)
Singular polynomial ring (QQ),(x,y),(dp(2),C)

It also possible to work with Nemo rings by casting to a suitable Singular type via CoefficientRing.

Examples

R, (x, y) = polynomial_ring(ZZ, ["x", "y"])

p = x^5 + y^3+1

p2 change_base_ring(CoefficientRing(Nemo.QQ), p)