SparsePolynomialZonotope

SparsePolynomialZonotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N},
                         MNI<:AbstractMatrix{N},
                         ME<:AbstractMatrix{<:Integer},
                         VI<:AbstractVector{<:Integer}}
    <: AbstractPolynomialZonotope{N}

Type that represents a sparse polynomial zonotope.

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

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

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

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 [1].

• [1] N. Kochdumper and M. Althoff. *Sparse Polynomial Zonotopes: A Novel Set

Representation for Reachability Analysis*. Transactions on Automatic Control,

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 – (optinal, 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.

center(P::SparsePolynomialZonotope)

Return the center of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The center.

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.

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 ($lpha_k$ in the definition) and each column to a monomial.

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.

uniqueID(n::Int)

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

Input

• n – number of variables

Output

1:n.

dim(P::SparsePolynomialZonotope)

Return the dimension of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The ambient dimension of P.

ngens_dep(P::SparsePolynomialZonotope)

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

Input

• P – sparse polynomial zonotope

Output

The number of dependent generators.

ngens_indep(P::SparsePolynomialZonotope)

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

Input

• P – sparse polynomial zonotope

Output

The number of independent generators.

nparams(P::SparsePolynomialZonotope)

Return the number of dependent parameters in the polynomial representation of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The number of dependent parameters in the polynomial representation.

Notes

This number corresponds to the number of rows in the exponent matrix $E$.

order(P::SparsePolynomialZonotope)

Return the order of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The order, defined as the quotient between the number of generators and the ambient dimension, as a Rational number.

linear_map(M::Union{Real, AbstractMatrix, LinearAlgebra.UniformScaling},
           P::SparsePolynomialZonotope)

Apply a linear map to a sparse polynomial zonotope.

Input

• M – square matrix with size(M) == dim(P)
• P – sparse polynomial zonotope

Output

The sparse polynomial zonotope resulting from applying the linear map.

translate(S::SparsePolynomialZonotope, v::AbstractVector)

Translate (i.e., shift) a sparse polynomial zonotope by a given vector.

Input

• S – sparse polynomial zonotope
• v – translation vector

Output

A translated sparse polynomial zonotope.

remove_redundant_generators(S::SparsePolynomialZonotope)

Remove redundant generators from S.

Input

• S – sparse polynomial zonotope

Output

A new sparse polynomial zonotope where redundant generators have been removed.

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.
• Remove Zero columns in GI.
• 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.

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

Overapproximate the sparse polynomial zonotope by another sparse polynomial zonotope with order at most r.

Input

• P – sparse polynomial zonotope
• r – maximum order of the resulting sparse polynomial zonotope (≥ 1)
• method – (optional default GIR05) algorithm used internally for the order reduction of a (normal) zonotope

Output

A sparse polynomial zonotope with order at most r.

Notes

This method implements the algorithm described in Proposition 3.1.39 of [1].

[1] N. Kochdumper. Extensions of polynomial zonotopes and their application to verification of cyber-physical systems. 2021.