IntPolynomials

AbstractExponents{N,I}

Abstract supertype for all collections of multivariate exponents in N variables (N > 0). Every collection is iterable (both using a default lazy iteration and a mutable iteration into a vector by means of iterate! or veciter) and indexable (return a lazy collection of exponents) with index type I. The collection has a length if it is finite; it is never empty.

AbstractExponentsUnbounded{N,I} <: AbstractExponents{N,I}

Abstract supertype for unbounded collections of multivariate exponents. These collections do not have a length; they are infinite. Their cache is always initialized incrementally as required.

AbstractExponentsDegreeBounded{N,I} <: AbstractExponents{N,I}

Abstract supertype for finite collections of multivariate exponents, bounded by their degrees. These collections have a length; they also provide at least the fields mindeg and maxdeg that describe (a superset of) the covered degree range. Their cache is always initialized completely when required.

ExponentsAll{N,I}()

Represents an index range for a fixed number of variables N without any degree bound.

ExponentsDegree{N,I}(mindeg::Integer, maxdeg::Integer)

Represents an exponent range that is restricted by a bound on the total degree.

ExponentsMultideg{N,I}(mindeg::Integer, maxdeg::Integer,
    minmultideg::AbstractVector, maxmultideg::AbstractVector)

Represents an exponent range that is restricted both by a global bound on the degree and by individual bounds on the variable degrees. Note that the vectors must not be used afterwards, and the constructor may clip maxmultideg to be no larger than maxdeg in each entry.

indextype(e)

Returns the index type of an instance or subtype of AbstractExponents. This function is not exported.

iterate!(v::AbstractVector{Int}, e::AbstractExponents)

Iterates through a set of exponents by maintaining an explicit representation of all exponents. This is slightly more efficient that the lazy iteration version if every exponent has to be accessed explicitly. Note that v must be initialized with a valid exponent combination in e (this may be done via copyto!(v, first(e))). The function returns true if successful and false if the end was reached.

veciter(e::AbstractExponents[, v::AbstractVector{Int}])

Creates an iterator over exponents that stores its result in a vector. This results in zero-allocations per iteration (as the iteration over e also does), but is more efficient if every element in e must be accessed. If the vector v is given as an argument, the data will be stored in this vector. If the vector is omitted, it will be created once at the beginning of the iteration process. The vector must never be altered, as it also serves as the state for the iterator; therefore, the same iterator may also not be nested.

exponents_to_index(::AbstractExponents{N,I}, exponents,
    degree::Int=sum(exponents, init=0)[, report_lastexp::Int])

Calculates the index of a monomial in N variables in an exponent set with exponents given by the iterable exponents (whose length should match N, else the behavior is undefined). The data type of the output is I. If exponents is not present in the exponent set, the result is zero(I). degree must always match the sum of all elements in the exponent set, but if it is already known, it can be passed to the function. No validity check is performed on degree.

exponents_from_index(::AbstractExponents{N,I}, index::I[, degree::Int])

Calculates the exponents that are associated with the monomial index index in N variables within a given exponent set. The return value will be a lazy implementation of AbstractVector{Int} (though iterating is more efficient than indexing). degree must match the degree of the index, if it is specified.

See also degree_from_index.

exponents_sum(e::AbstractExponents{N,I}, exponents...) -> Tuple{I,Int}

Calculates the index of the sum of all exponents within e. If the result cannot be found in e, the function will return zero. Returns the total degree as second entry in the tuple.

exponents_product(e::AbstractExponents{N,I}, exponents, p::Integer) -> Tuple{I,Int}

Calculates the index of the product of the exponents with the number p. If the result cannot be found in e, the function will return zero. Returns the total degree as second entry in the tuple.

degree_from_index(::AbstractExponents{N,I}, index::I)

Returns the degree that is associated with a given monomial index index in N variables. If the index was larger than the maximally allowed index in the exponent set, a degree larger than the maximal degree allowed in the iterator will be returned (not necessarily lastindex +1).

convert_index(target::AbstractExponents{N}, source::AbstractExponents{N,I},
    index::I[, degree::Int])

Converts an index from an exponent set source to an exponent set target. index is always assumed to be a valid index for source, else the behavior is undefined.

compare_indices(e₁::AbstractExponents, index₁, op, e₂::AbstractExponents,
    index₂[, degree::Int])

Compares two indices from two possibly different exponent sets. degree, if given, must be the common degree of both exponents); when degree is omitted, also different degrees are possible. Both indices are assumed to be valid for their respective exponent sets, else the behavior is undefined. However, it is not necessary that an index is also valid in the other's exponent set. If ẽ₁ and ẽ₂ denote the conversion of the indices to a common exponent set (say, ExponentsAll), then the result is op(ẽ₁, ẽ₂). The only allowed values for op are ==, !=, <, <=, >, and >=.

a == b

Compares whether two exponents with the same variable number are equal. Exponents with different index types are not considered equal.

See isequal.

isequal(a, b)

Compares whether two exponents with the same variable number are equal. Different index types are disregarded.

See ==.

issubset(a, b)

Checks whether the exponent set a is fully contained in b. Different index types are disregarded.

length(e::AbstractExponentsDegreeBounded)

Returns the total number of exponents present in e.

index_counts(unsafe, ::AbstractExponents{N,I})

Returns the current Matrix{I} that holds the exponents counts for up to N variables in its N+1 columns (in descending order, ending with zero variables), and for the maximal degrees in the rows (in ascending order, starting with zero). The result is neither guaranteed to be defined at all nor have the required form if the cache was not calculated before.

index_counts(::AbstractExponents{N,I}, degree::Integer) -> Tuple{Matrix{I},Bool}

Safe version of the above. If the boolean in the result is true, the matrix will have at least degree+1 rows, i.e., all entries up to degree are present. If it is false, the requested degree is not present in the exponents and the matrix will have fewer rows. Note that true does not mean that the degree is actually present in the exponents, only that its information has been calculated.

exponents_from_index(unsafe, ::AbstractExponents{N,I}, index::I[, degree::Int])

Unsafe variant of exponents_from_index: assumes that the cache for degree degree has already been populated, and that the exponent set contains index. If degree is omitted, it is calculated using the unsafe variant of degree_from_index.

degree_from_index(unsafe, ::AbstractExponents{N,I}, index::I)

Unsafe variant of degree_from_index: assumes that the required cache for the degree that is associated with index has already been initialized, else the behavior is undefined (and in fact, non-deterministic, as it depends on the current size of the cache).

convert_index(unsafe, target::AbstractExponents{N}, source::AbstractExponents{N,I},
    index::I[, degree::Int])

Unsafe variant of convert_index: assumes that caches for both the source and the target are set up as required for degree. If degree is omitted, it is calculated using the unsafe variant of degree_from_index.

compare_indices(unsafe, e₁::AbstractExponents, index₁, op, e₂::AbstractExponents,
    index₂[, degree::Int])

Unsafe variant of compare_indices: assumes that both caches are set up as required for degree (which, if given, must be the common degree of both exponents). If degree is omitted, it is calculated using the unsafe variant of degree_from_index.

length(unsafe, e::AbstractExponentsDegreeBounded)

Unsafe variant of length: requires the cache to be set up correctly, else the behavior is undefined.

IntVariable{Nr,Nc,I<:Unsigned} <: AbstractVariable

IntVariable is the basic type for any simple variable in a polynomial right with Nr real and Nc complex-valued variables. The variable is identified by its index of type I alone. A variable can be explicitly cast to I in order to obtain its index.

To construct a real-valued or complex-valued variable, see IntRealVariable and IntComplexVariable.

IntRealVariable{Nr,Nc}(index::Integer)

Creates a new real-valued simple variable whose identity is determined by index. Real-valued variables with the same index are considered identical; however, they are different from complex-valued variables constructed with the same index. A real variable will print as xᵢ, where the subscript is given by index. The variable is part of the polynomial ring with Nr real and Nc complex variables.

See also IntVariable, IntComplexVariable.

IntComplexVariable{Nr,Nc}(index::Integer, isconj::Bool=false)

Creates a new complex-valued simple variable whose identity is determined by index, and which is a conjugate variable if isconj is set appropriately. Complex-valued variables with the same index and isconj state are considered identical; however, they are different from real-valued variables constructed with the same index, even if they are not conjugate. A complex variable will print as zᵢ (if isconj=false) or z̄ᵢ (if isconj=true), where the subscript is given by index. The variable is part of the polynomial ring with Nr real and Nc complex variables.

See also IntVariable, IntRealVariable.

IntMonomial{Nr,Nc,I<:Integer,E<:AbstractExponents} <: AbstractMonomial

IntMonomial represents a monomial. In order to be used together in operations, the number of real-valued variables Nr and the number of complex-valued variables Nc are fixed in the type. The monomial is identified according to its index (of type I) in an exponent set of type E. This should be an unsigned type, but to allow for BigInt, no such restriction is imposed.

IntMonomial{Nr,0[,I]}([e::AbstractExponents,]
    exponents_real::AbstractVector{<:Integer})
IntMonomial{0,Nc[,I]}([e::AbstractExponents,]
    exponents_complex::AbstractVector{<:Integer},
    exponents_conj::AbstractVector{<:Integer})
IntMonomial{Nr,Nc[,I]}([e::AbstractExponents,]
    exponents_real::AbstractVector{<:Integer},
    exponents_complex::AbstractVector{<:Integer},
    exponents_conj::AbstractVector{<:Integer})

Creates a monomial within an exponent set e. If e is omitted, ExponentsAll{Nr+2Nc,UInt} is chosen by default. Alternatively, all three methods may also be called with the index type I as a third type parameter, omitting e, which then chooses ExponentsAll{Nr+2Nc,I} by default.

IntConjMonomial(m::IntMonomial) <: AbstractMonomial

This is a wrapper type for the conjugate of a simple monomial. A lot of operations allow to pass either IntConjMonomial or IntMonomial. Constructing the conjugate using this type works in zero time.

See also conj.

IntMonomial(c::IntConjMonomial)

Converts a IntConjMonomial into a IntMonomial. This performs the calculation of the conjugate index.

IntMonomialVector{Nr,0[,I]}([e::AbstractExponents,]
    exponents_real::AbstractMatrix{<:Integer}, along...)
IntMonomialVector{0,Nc[,I]}([e::AbstractExponents,]
    exponents_complex::AbstractMatrix{<:Integer},
    exponents_conj::AbstractMatrix{<:Integer}, along...)
IntMonomialVector{Nr,Nc[,I]}([e::AbstractExponents,]
    exponents_real::AbstractMatrix{<:Integer},
    exponents_complex::AbstractMatrix{<:Integer},
    exponents_conj::AbstractMatrix{<:Integer}, along...)

Creates a monomial vector, where each column corresponds to one monomial and each row contains its exponents. The internal representation will be made with respect to the exponent set e. If e is omitted, ExponentsAll{Nr+2Nc,UInt} is chosen by default. Alternatively, all three methods may also be called with the index type I as a third type parameter, omitting e, which then chooses ExponentsAll{Nr+2Nc,I} by default. All matrices must have the same number of columns; complex and conjugate matrices must have the same number of rows. The input will be sorted; if along are present, those vectors will be put in the same order as the inputs. The input must not contain duplicates.

IntMonomialVector[{I}](mv::AbstractVector{<:AbstractMonomialLike}, along...;
    vars=variables(mv))

Creates a IntMonomialVector from a generic monomial vector that supports MultivariatePolynomials's interface. The monomials will internally be represented by the type I (UInt by default). The keyword argument vars must contain all real-valued and original complex-valued (so not the conjugates) variables that occur in the monomial vector. However, the order of this iterable (which must have a length) controls how the MP variables are mapped to IntVariables. The variables must be commutative; there is currently no way to check for this, so in the conversion process, commutativity is simply assumed. The input must not contain duplicates. It will be sorted; if along are present, those vectors will be put in the same order as the inputs.

IntPolynomial[{I}](p::AbstractPolynomialLike{C}, coefficient_type=C; kwargs...) where {C}

Creates a new IntPolynomial based on any polynomial-like object that implements MultivariatePolynomials's AbstractPolynomialLike interface. The coefficients will be of type coefficient_type, the internal index type for the monomials will be I (UInt if omitted). Keyword arguments are passed on to IntMonomialVector, which allows to influence the variable mapping.

change_backend(mv::IntMonomialVector, variable::AbstractVector{<:AbstractVariable})

Changes a IntMonomialVector into a different implementation of MultivariatePolynomials, where the variables are taken from the given vector in the order as they appear (but keeping real and complex variables distinct).

This conversion is not particularly efficient, as it works with generic implementations.

change_backend(p::IntPolynomial, variables::AbstractVector{<:AbstractVariable})

Changes a IntPolynomial into a different implementation of MultivariatePolynomials, where the variables are taken from the given vector in the order as they appear (but keeping real and complex variables distinct). Note that the coefficients are returned without making a copy, which depending on the backend can imply back-effects on p itself should the output be changed. This conversion is not particularly efficient, as it works with generic implementations.

conj(m::Union{<:IntMonomial,<:IntConjMonomial})

Creates the conjugate of a IntMonomial. The result type of this operation will always be IntMonomial. If the conjugate can be used to work with lazily, consider wrapping the monomial in a IntConjMonomial instead.

variable_index(v::IntVariable{Nr,Nc})

Returns the index of the variable v, where real-valued variables have indices between 1 and Nr, and complex-valued variables have indices between Nr+1 and Nr+Nc. Conjugates have the same indices as their ordinary variables.

monomial_product(e::AbstractExponents, m...)

Calculates the product of all monomials (or conjugates, or variables) m. The result must be part of the exponent set e. If the default multiplication * is used instead, e will always be ExponentsAll with the jointly promoted index type.

monomial_index([e::AbstractExponents,] m...)

Calculates the index of the given monomial (or the product of all given monomials, or conjugates, or variables) m. The result must be part of the exponent set e. If e is omitted, it will be be ExponentsAll with the jointly promoted index type.

effective_nvariables(x::Union{<:IntMonomialVector{Nr,Nc},
                              <:AbstractArray{<:IntMonomialVector{Nr,Nc}}}...)

Calculates the number of effective variable of its arguments: there are at most Nr + 2Nc variables that may occur in any of the monomial vectors or arrays of monomial vectors in the arguments. This function calculates efficiently the number of variables that actually occur at least once anywhere in any argument.

monomials(Nr, Nc, degree::AbstractUnitRange{<:Integer};
    minmultideg=nothing, maxmultideg=nothing, filter_exps=nothing,
    filter_mons=nothing, I=UInt)

Returns a IntMonomialVector with Nr real and Nc complex variables, total degrees contained in degree, ordered according to Graded{LexOrder} and individual variable degrees varying between minmultideg and maxmultideg (where real variables come first, then complex variables, then their conjugates).

The monomial vector will take possession of the min/maxmultidegs, do not modify them afterwards.

An additional filter may be employed to drop monomials during the construction. Note that the presence of a filter function will change to a less efficient internal representation. The filter function can get a vector with the exponents as its argument (filter_exps) or a filter function that gets the corresponding IntMonomial. The former is more efficient if every exponent has to be retrieved (but do not alter the argument).

The internal representation will be of the type I.

This function can be made type-stable by passing Nr and Nc as Vals.

intersect(a::IntMonomialVector{Nr,Nc}, b::IntMonomialVector{Nr,Nc})

Calculates efficiently the intersection of two monomial vectors.

merge_monomial_vectors(::Val{Nr}, ::Val{Nc}, e::AbstractExponents, X::AbstractVector)

Returns the vector of monomials contained X in increasing order and without any duplicates. The individual elements in X must be sorted iterables with a length and return IntMonomials compatible with the number of real Nr and complex variables Nc. The output will internally use the exponents e. The result type will be a IntMonomialVector with Nr and Nc as given, I and the exponents determined by e, and indexed internally with a Vector{I}.

merge_monomial_vectors(X::AbstractVector)

Potentially type-unstable variant that automatically determines the output format. If X has a defined eltype with known eltype <:IntMonomial{Nr,Nc,I,E}, Nr, Nc, and I are determined automatically in a type-stable manner. If not, they are taken from the eltype of the first iterable in X (which is not type stable). If this is not possible, either, they are taken from the first element in the first nonempty iterable in X.

Regarding the automatic determination of E, the following rule is applied: it is assumed that if E is known in the element type, then every monomial will have the same instance of e as the exponents per iterable (this is always satisfied if the iterables are IntMonomialVectors). If there is one exponent that covers all others, this instance will be used. If not, the largest necessary exponents will be constructed; the result will be indexed unless all can be merged contiguously). Note that inhomogeneous iterables must implement last if the elements are based on ExponentsAll.

veciter(mv::IntMonomialVector[, v::AbstractVector{Int}], indexed::Bool=false)

Creates an iterator over all exponents present in mv (see veciter for AbstractExponents). By setting indexed to true, this iterator will instead give a tuple similar to enumerate, where the first index corresponds to the index of the monomial in the exponent set (so it does not necessarily start at 1 or have unit step). For type stability, indexed may instead be Val(false) or Val(true).

keepat!!(x::IntMonomialVector, i::AbstractVector{Bool})

Keeps the jᵗʰ monomial in x only if i[j] is true. This will mutate x if possible (i.e., if it was already indexed by a vector before), but it might also create a new vector if required (i.e., if a whole range of exponents was covered). Always use the return value, never rely on x. This function is not exported.