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.
| Library | Element type | Parent type |
|---|---|---|
| Singular | spoly{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 - yTerm orderings
A general term ordering can be constructed as a product of one or more of the following block orderings.
Singular.ordering_lp — Functionordering_lp(nvars::Int = 1)Represents a block of at least nvars variables with the lexicographical ordering (:lex) (the Singular ordering lp).
Singular.ordering_ip — Functionordering_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.
Singular.ordering_rp — Functionordering_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.
Singular.ordering_dp — Functionordering_dp(nvars::Int = 1)Represents a block of at least nvars variables with the degree reverse lexicographical ordering (:degrevlex) (the Singular ordering dp).
Singular.ordering_Dp — Functionordering_Dp(nvars::Int = 1)Represents a block of at least nvars variables with the degree lexicographical ordering (:deglex) (the Singular ordering Dp).
Singular.ordering_wp — Methodordering_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).
Singular.ordering_Wp — Methodordering_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).
Singular.ordering_Ip — Functionordering_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.
Singular.ordering_ls — Functionordering_ls(nvars::Int = 1)Represents a block of at least nvars variables with the negative lexicographical ordering (:neglex) (the Singular ordering ls).
Singular.ordering_is — Functionordering_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.
Singular.ordering_rs — Functionordering_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.
Singular.ordering_ds — Functionordering_ds(nvars::Int = 1)Represents a block of at least nvars variables with the negative degree reverse lexicographical ordering (:negdegrevlex) (the Singular ordering ds).
Singular.ordering_Ds — Functionordering_Ds(nvars::Int = 1)Represents a block of at least nvars variables with the negative degree reverse lexicographical ordering (:negdeglex). (the Singular ordering Ds).
Singular.ordering_ws — Methodordering_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).
Singular.ordering_Ws — Methodordering_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).
Singular.ordering_a — Methodordering_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).
Singular.ordering_M — Methodordering_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).
Singular.ordering_C — Methodordering_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).
Singular.ordering_c — Methodordering_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).
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_ordering — Methodhas_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.
Singular.has_mixed_ordering — Methodhas_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$.
Singular.has_local_ordering — Methodhas_local_ordering(R::PolyRingUnion)Return true if the given ring has a local ordering, i.e. if $1 > x$ for all variables $x$.
Singular.degree_bound — Methoddegree_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.
AbstractAlgebra.Generic.total_degree — Methodtotal_degree(p::spoly)Return the total degree (largest sum of exponents of any monomial) of $p$.
AbstractAlgebra.order — Methodorder(p::spoly)Return the order of $p$.
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)
0Differential functions
Working over any coefficient ring, basic functionality involving differential operations is available.
Singular.jet — Methodjet(x::spoly{T}, n::Int) where T <: Nemo.RingElemReturn the truncation of $x$ up to degree $n$.
AbstractAlgebra.derivative — Methodderivative(x::spoly{T}, n::Int) where T <: Nemo.RingElemReturn the derivative of $x$ with respect to the variable of index $n$.
AbstractAlgebra.derivative — Methodderivative(x::spoly{T}, v::spoly{T}) where T <: Nemo.RingElemReturn the derivative of $x$ with respect to the variable $v$.
Singular.jacobian_ideal — Methodjacobian_ideal(p::spoly{T}) where T <: Nemo.RingElemReturn the ideal generated by all partial derivatives of $x$.
Singular.jacobian_matrix — Methodjacobian_matrix(p::spoly{T}) where T <: Nemo.RingElemReturn the column matrix $\{\frac{\partial p}{\partial x_i}\}_i$ of partial derivatives.
Singular.jacobian_matrix — Methodjacobian_matrix(a::Vector{spoly{T}}) where T <: Nemo.RingElemReturn the matrix $\{\frac{\partial a_i}{\partial x_j}\}_{ij}$ of partial derivatives.
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.primpart — Methodprimpart(x::SPolyUnion)Return the primitive part of the polynomial, i.e. the polynomial divided by the GCD of its coefficients.
AbstractAlgebra.content — Methodcontent(x::SPolyUnion)Return the content of the polynomial, i.e. the GCD of its coefficients.
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)
3Homogeneous polynomials
Singular.homogenize — Methodhomogenize(p::spoly{T}, v::spoly{T}) where T <: Nemo.RingElemMultiply 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.
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)^2For 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)^2Change 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)