SparsePolynomialZonotope

SparsePolynomialZonotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N},
                         MNI<:AbstractMatrix{N},
                         ME<:AbstractMatrix{Int},
                         VI<:AbstractVector{Int}}
    <: AbstractSparsePolynomialZonotope{N}

Type that represents a sparse polynomial zonotope.

A sparse polynomial zonotope $\mathcal{PZ} ⊂ ℝ^n$ is represented by the set

\[\mathcal{PZ} = \left\{x ∈ ℝ^n : x = c + ∑ᵢ₌₁ʰ\left(∏ₖ₌₁ᵖ α_k^{E_{k, i}} \right)Gᵢ+∑ⱼ₌₁^qβⱼGIⱼ,~~ α_k, βⱼ ∈ [-1, 1],~~ ∀ k = 1,…,p, j=1,…,q \right\},\]

where $c ∈ ℝ^n$ is the offset vector (or center), $Gᵢ ∈ ℝ^{n}$ are the dependent generators, $GIⱼ ∈ ℝ^{n}$ are the independent generators, and $E ∈ \mathbb{N}^{p×h}_{≥0}$ is the exponent matrix with matrix elements $E_{k, i}$.

In the implementation, $Gᵢ ∈ ℝ^n$ are arranged as columns of the dependent generator matrix $G ∈ ℝ^{n × h}$, and similarly $GIⱼ ∈ ℝ^{n}$ are arranged as columns of the independent generator matrix $GI ∈ ℝ^{n×q}$.

The shorthand notation $\mathcal{PZ} = ⟨ c, G, GI, E, idx ⟩$ is often used, where $idx ∈ \mathbb{N}^p$ is a list of non-repeated natural numbers storing a unique identifier for each dependent factor $αₖ$.

Fields

• c – offset vector
• G – dependent generator matrix
• GI – independent generator matrix
• E – exponent matrix
• idx – identifier vector of positive integers for the dependent parameters

Notes

Sparse polynomial zonotopes were introduced in Kochdumper and Althoff [KA21].

expmat(P::SparsePolynomialZonotope)

Return the matrix of exponents of the sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The matrix of exponents, where each column is a multidegree.

Notes

In the exponent matrix, each row corresponds to a parameter ($αₖ$ in the definition) and each column to a monomial.

genmat_dep(P::SparsePolynomialZonotope)

Return the matrix of dependent generators of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The matrix of dependent generators.

genmat_indep(P::SparsePolynomialZonotope)

Return the matrix of independent generators of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The matrix of independent generators.

indexvector(P::SparsePolynomialZonotope)

Return the index vector of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The index vector.

Notes

The index vector contains positive integers for the dependent parameters.

polynomial_order(P::SparsePolynomialZonotope)

Return the polynomial order of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The polynomial order.

Notes

The polynomial order is the maximum sum of all monomials' parameter exponents.

rand(::Type{SparsePolynomialZonotope}; [N]::Type{<:Real}=Float64,
     [dim]::Int=2, [nparams]::Int=2, [maxdeg]::Int=3,
     [num_dependent_generators]::Int=-1,
     [num_independent_generators]::Int=-1, [rng]::AbstractRNG=GLOBAL_RNG,
     [seed]::Union{Int, Nothing}=nothing)

Create a random sparse polynomial zonotope.

Input

• SparsePolynomialZonotope – type for dispatch
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension
• nparams – (optional, default: 2) number of parameters
• maxdeg – (optional, default: 3) maximum degree for each parameter
• num_dependent_generators – (optional, default: -1) number of dependent generators (see comment below)
• num_independent_generators – (optional, default: -1) number of independent generators (see comment below)
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random sparse polynomial zonotope.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1.

The number of generators can be controlled with the arguments num_dependent_generators and num_dependent_generators. For a negative value we choose a random number in the range dim:2*dim (except if dim == 1, in which case we only create a single generator). Note that the final number of generators may be lower if redundant monomials are generated.

linear_map(MZ::MatrixZonotope, P::SparsePolynomialZonotope)

Compute the linear map of a sparse polynomial zonotope through a matrix zonotope, following Proposition 1 of Huang et al. [HLBS25].

Input

• lm – a linear map of a sparse polynomial zonotope through a matrix zonotope

Output

A sparse polynomial zonotope representing the linear map $MZ ⋅ P$`.

linear_map(MZP::MatrixZonotopeProduct, P::SparsePolynomialZonotope)

Compute the linear map of a sparse polynomial zonotope through a matrix zonotope product by recursively applying the linear_map method from the inside out.

Input

• MZ – a matrix zonotope product
• P – a sparse polynomial zonotope

Output

A sparse polynomial zonotope representing the linear map $MZ ⋅ P$.

remove_redundant_generators(Z::AbstractZonotope)

Remove all redundant (pairwise linearly dependent) generators of a zonotopic set.

Input

• Z – zonotopic set

Output

A new zonotope with fewer generators, or the same zonotopic set if no generator could be removed.

Algorithm

By default this implementation returns the input zonotopic set. Subtypes of AbstractZonotope whose generators can be removed have to define a new method.

Extended help

remove_redundant_generators(S::SparsePolynomialZonotope)

Notes

The result uses dense arrays irrespective of the array type of S.

Algorithm

Let G be the dependent generator matrix, E the exponent matrix, and GI the independent generator matrix of S. We perform the following simplifications:

• Remove zero columns in G and the corresponding columns in E.
• For each generator $g_j$ in GI, we find all other generators that are linearly dependent with $g_j$ and combine those generators into a single generator.
• For zero columns in E, add the corresponding column in G to the center.
• Group repeated columns in E together by summing the corresponding columns in G.

uniqueID(n::Int)

Return a collection of n unique identifiers (integers 1, …, n).

Input

• n – number of variables

Output

1:n.

merge_id(id1::AbstractVector{Int}, id2::AbstractVector{Int},
         E₁::AbstractMatrix{N}, E₂::AbstractMatrix{N}) where {N}

Align two identifier vectors and their corresponding exponent matrices in compatible form.

Input

• id1::AbstractVector{Int} – identifiers corresponding to the rows of E₁
• id2::AbstractVector{Int} – identifiers corresponding to the rows of E₂
• E₁::AbstractMatrix{N} – first exponent matrix of size (p₁ × h₁)
• E₂::AbstractMatrix{N} – second exponent matrix of size (p₂ × h₂)

Output

• Ē₁::Matrix{N}: Aligned version of E₁
• Ē₂::Matrix{N}: Aligned version of E₂
• idx::Vector{Int}: Merged identifier vector, containing all elements of id1 and any new ones from id2.

Algorithm

This method implements Kochdumper and Althoff [KA21], Proposition 1.

Example

julia> using LazySets.SparsePolynomialZonotopeModule: merge_id

julia> id1 = [1, 2];

julia> E₁ = [1 2; 1 0];

julia> id2 = [2, 3];

julia> E₂ = [1 0 1; 3 2 0];

julia> Ē₁, Ē₂, idx = merge_id(id1, id2, E₁, E₂)
([1 2; 1 0; 0 0], [0 0 0; 1 0 1; 3 2 0], [1, 2, 3])

reduce_order(Z::AbstractZonotope, r::Real,
             [method]::AbstractReductionMethod=GIR05())

Reduce the order of a zonotopic set by overapproximating with a zonotope with fewer generators.

Input

• Z – zonotopic set
• r – desired order
• method – (optional, default: GIR05()) the reduction method used

Output

A new zonotope with fewer generators, if possible.

Algorithm

The available algorithms are:

julia> subtypes(AbstractReductionMethod)
4-element Vector{Any}:
 LazySets.ASB10
 LazySets.COMB03
 LazySets.GIR05
 LazySets.SRMB16

See the documentation of each algorithm for references. Most methods split the given zonotopic set Z into two zonotopes, K and L, where K contains the most "representative" generators and L contains the generators that are reduced, Lred, using a box overapproximation. This methodology varies slightly for SRMB16. We follow the notation from Yang and Scott [YS18]. See also Kopetzki et al. [KSA17].

Extended help

reduce_order(P::SparsePolynomialZonotope, r::Real,
             [method]::AbstractReductionMethod=GIR05())

Notes

This method implements the algorithm described in Kochdumper [Koc22], Proposition 3.1.39.

exact_sum(X::LazySet, Y::LazySet)

Compute the exact sum of two parametric sets.

Input

• X – parametric set
• Y – parametric set

Output

A set representing the exact sum, sometimes written $X ⊞ Y$.

Notes

For parametric sets, the exact sum behaves like the Minkowski sum, except that the parameters are shared. Thus, for nonparametric sets, it coincides with the Minkowski sum.

Extended help

exact_sum(P1::SparsePolynomialZonotope, P2::SparsePolynomialZonotope)

Algorithm

This method implements Kochdumper [Koc22], Proposition 3.1.20.