Multiindices

FactorisationEntry

One result from a factorisation function: an ordered list of multiindex-set indices (one per factor slot) together with the number of distinct ordered arrangements of that combination.

• factor_indices — indices into the multiindex set, one per factor slot.
• multiplier — number of distinct orderings (permutations) of this combination. Always 1 for factorisations_asymmetric, which enumerates each ordering as a separate entry.

All three factorisation functions return Vector{FactorisationEntry}, so call sites do not need to know which variant produced the data.

MultiindexSet{N}

A fixed collection of exponent vectors (multiindices) stored as a vector of SVector{N, Int}. The set is guaranteed to be sorted according to the graded lexicographic (Grlex) order.

Fields

• exponents::Vector{SVector{N, Int}}: each element is an exponent vector.

_last_index_below_degree(set::MultiindexSet, max_total_deg::Int,
						 allowed_indices::AbstractVector{Int}) -> Int

Same as the 2‑argument version, but the search is restricted to the indices listed in allowed_indices (which must be sorted in increasing order). The returned value is still an actual column index (or 0 if none qualifies).

_last_index_below_degree(set::MultiindexSet, max_total_deg::Int) -> Int

Return the last column index i in the Grlex‑sorted set such that the total degree of set[i] is strictly less than max_total_deg. If no such index exists, return 0.

_multinomial(e::Int, k::Vector{Int}) -> Int

Multinomial coefficient: e! / (k₁! k₂! … kₚ!) where sum(k) = e. Uses iterative multiplication of binomial coefficients to avoid overflow.

_sv_eq_tuple(v::SVector{N,Int}, t::NTuple{N,Int})

Helper functions that compares: SVector ==(indexwise) NTuple

all_multiindices_in_box(bound::Vector{Int}) -> MultiindexSet

Generate all multi-indices v of length length(bound) such that 0 ≤ v[i] ≤ bound[i] for all i. The vectors are generated and then sorted according to graded lexicographic order.

all_multiindices_up_to(nvars::Int, max_degree::Int) -> MultiindexSet

Generate all exponent vectors with nvars variables whose total degree ≤ max_degree, sorted according to graded lexicographic order. Returns a MultiindexSet.

bounded_index_tuples(M, exp::SVector{N,Int})

Enumerate all index tuples of length M whose component counts are bounded by exp.

This function generates all tuples (i₁, ..., i_M) with entries in 1:N such that:

• Each index k appears at most exp[k] times
• The total length of the tuple is exactly M

Each tuple is represented in its canonical sorted form (non-decreasing order), so that it uniquely corresponds to a count vector (multiindex).

For each valid tuple, the function also returns:

• The associated multiindex alpha, where alpha[k] is the number of times k appears
• The number of distinct permutations of the tuple

Returns a vector of tuples: (indextuple, multiindex, permutationcount)

where:

• index_tuple::NTuple{M,Int} is the sorted tuple
• multiindex::SVector{N,Int} contains the counts
• permutation_count::Int is the number of distinct permutations

build_exponent_index_map(set::MultiindexSet) -> Dict{NTuple{N,Int}, Int} where N

Build a dictionary mapping each exponent (as a tuple) to its column index in the set. Useful for O(1) lookups without repeated binary searches.

The keys are NTuple{N,Int} where N is the number of variables.

divides(a::AbstractVector{Int}, b::AbstractVector{Int}) -> Bool

Check whether a divides b componentwise, i.e., a[i] ≤ b[i] for all i.

factorisations_asymmetric(set, exp, num_factors, candidate_indices) -> Vector{FactorisationEntry}

Return every ordered num_factors-tuple of indices from candidate_indices whose exponent vectors sum to exp. Each ordering is a separate entry with multiplier = 1.

factorisations_fully_symmetric(set, exp, num_factors, candidate_indices) -> Vector{FactorisationEntry}

Return all unordered (non-decreasing index) num_factors-tuples from candidate_indices whose exponent vectors sum to exp. multiplier is the multinomial coefficient num_factors! / (m₁! m₂! … mₖ!) counting the distinct ordered arrangements of each combination.

Duplicate entries in candidate_indices are removed internally.

factorisations_groupwise_symmetric(set, exp, group_sizes, candidate_indices) -> Vector{FactorisationEntry}

Return factorisations of exp into M = length(group_sizes) groups, where group i has group_sizes[i] factor slots and is internally symmetric.

factor_indices in each entry is the concatenation of per-group indices in group order (each group sorted non-decreasingly). multiplier is the product of the per-group permutation counts — the total number of ordered arrangements.

find_in_set(set::MultiindexSet, exp::AbstractVector{Int}) -> Union{Int, Nothing}

Return the column index of exp in set.exponents using binary search, exploiting the fact that the set is sorted according to Grlex. Returns nothing if exp is not present.

find_in_set(set::MultiindexSet, exp::NTuple{N,Int}) where N -> Union{Int, Nothing}

Tuple version – avoids allocating a vector for the exponent.

grlex_precede(a::AbstractVector{<:Integer}, b::AbstractVector{<:Integer}) -> Bool

Graded lexicographic order: compare total degree first, then lexicographic descending. Returns true if a comes before b in this order.

grlex_precede(t::NTuple{N,Int}, v::AbstractVector{Int}) -> Bool

Compare a tuple (representing an exponent) with a vector in graded lexicographic order. Useful for binary search without allocating a vector.

indices_in_box_with_bounded_degree(set::MultiindexSet, box_upper::AbstractVector{Int},
								   degree_lower_bound::Int, total_deg_upper::Int,
								   allowed_indices::AbstractVector{Int}) -> Vector{Int}

Same as the 4‑argument version, but the search is restricted to the indices listed in allowed_indices (which must be sorted). Only those indices that also satisfy the componentwise bound are returned.

indices_in_box_with_bounded_degree(set::MultiindexSet, box_upper::AbstractVector{Int},
								   degree_lower_bound::Int, total_deg_upper::Int) -> Vector{Int}

Return the column indices of all multiindices v in set such that

• v ≤ box_upper componentwise,
• degree_lower_bound ≤ sum(v[i]) < total_deg_upper.

Uses the degree bounds to limit the search to relevant columns.

is_constant(exp::AbstractVector{Int}) -> Bool

Return true if the exponent vector is all zeros.

monomial_rank(exp::AbstractVector{Int}, nvars::Int, max_degree::Int) -> Int

Return the 1‑based rank of the exponent vector exp in the complete set of all multiindices of length nvars with total degree ≤ max_degree, sorted according to graded lexicographic order (Grlex).

The vector exp must satisfy length(exp) == nvars and sum(exp) ≤ max_degree. Uses combinatorial counting formulas for efficiency (O(nvars) time).

If the computed rank exceeds typemax(Int), an error is thrown.

multiindex(components::Int...) -> Vector{Int}

Convenience constructor for an exponent vector.

multiindices_with_total_degree(nvars::Int, deg::Int) -> MultiindexSet

Generate all exponent vectors of length nvars with total degree exactly deg, sorted in lexicographic order (the tie‑breaker for Grlex). Returns a MultiindexSet.

num_multiindices_up_to(nvars::Int, max_degree::Int) -> Integer

Return the number of exponent vectors of length nvars with total degree ≤ max_degree. For nvars = 0 the set contains one element if max_degree ≥ 0, otherwise zero.

zero_multiindex(n::Int) -> Vector{Int}

Return the zero exponent vector of length n (all components zero).