Sparse distributed multivariate Laurent polynomials

Every element of the multivariate Laurent polynomial ring $R[x_1, x_1^{-1}, \dots, x_n, x_n^{-1}]$ can be presented as a sum of products of powers of the $x_i$ where the power can be any integer. Therefore, the interface for sparse multivarate polynomials carries over with the additional feature that exponents can be negative.

Generic multivariate Laurent polynomial types

AbstractAlgebra.jl provides a generic implementation of multivariate Laurent polynomials, built in terms of regular multivariate polynomials, in the file src/generic/LaurentMPoly.jl.

The type LaurentMPolyWrap{T, ...} <: LaurentMPolyElem{T} implements generic multivariate Laurent polynomials by wrapping regular polynomials: a Laurent polynomial l wraps a polynomial p and a vector of integers $n_i$ such that $l = \prod_i x_i^{n_i} * p$. The representation is said to be normalized when each $n_i$ is as large as possible (or zero when l is zero), but the representation of a given element is not required to be normalized internally.

The corresponding parent type is LaurentMPolyWrapRing{T, ...} <: LaurentMPolyRing{T}.

Abstract types

Two abstract types LaurentMPolyElem{T} and LaurentMPolyRing{T} are defined to represent Laurent polynomials and rings thereof, parameterized on a base ring T.

Multivate Laurent polynomial operations

Since, from the point of view of the interface, Laurent polynomials are simply regular polynomials with possibly negative exponents, the following functions from the polynomial interface are completely analogous. As with regular polynomials, an implementation must provide access to the elements as a sum of individual terms in some order. This order currently cannot be specified in the constructor.

LaurentPolynomialRing(R::Ring, S::Vector{String}; cached::Bool = true)
LaurentPolynomialRing(R::Ring, n::Int, s::String="x"; cached::Bool = false)
(S::LaurentMPolyRing{T})(A::Vector{T}, m::Vector{Vector{Int}})
push_term!(M::LaurentMPolyBuildCtx, c::RingElem, v::Vector{Int})
gen(S::LaurentMPolyRing, i::Int)
change_base_ring(::Ring, p::LaurentMPolyElem)
change_coefficient_ring(::Ring, p::LaurentMPolyElem)
map_coefficients(::Any, p::LaurentMPolyElem)
evaluate(p::LaurentMPolyElem, ::Vector)
derivative(p::LaurentMPolyElem, x::LaurentMPolyElem)
derivative(p::LaurentMPolyElem, i::Int)
rand(R::LaurentMPolyElem, length_range::UnitRange{Int}, exp_range::UnitRange{Int}, v...)

The choice of canonical unit for Laurent polynomials includes the product $\prod_i x_i^{n_i}$ from the normalized representation. In particular, this means that the output of gcd will not have any negative exponents.

julia> R, (x, y) = LaurentPolynomialRing(ZZ, ["x", "y"]);

julia> canonical_unit(2*x^-5 - 3*x + 4*y^-4 + 5*y^2)

julia> gcd(x^-3 - y^3, x^-2 - y^2)
x*y - 1