SparsePolynomialZonotope

LazySets.SparsePolynomialZonotopeType
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, vector of positive integers identifing the dependent parameters of PZ.

Notes

Sparse polynomial zonotopes were introduced in [KA21].

  • [KA21] N. Kochdumper and M. Althoff. Sparse Polynomial Zonotopes: A Novel Set Representation for Reachability Analysis. Transactions on Automatic Control, 2021.
source
Base.randMethod
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

  • Zonotope – 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
  • rng – (optional, default: GLOBAL_RNG) random number generator
  • seed – (optional, default: nothing) seed for reseeding
  • num_dependent_generators – (optional, default: -1) number of dependent generators of the zonotope (see comment below)
  • num_independent_generators – (optional, default: -1) number of independent generators of the zonotope (see comment below)

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.

source
LazySets.centerMethod
center(P::SparsePolynomialZonotope)

Return the center of P.

Input

  • P – sparse polynomial zonotope

Output

The center of P.

source
LazySets.genmat_depMethod
genmat_dep(P::SparsePolynomialZonotope)

Return the matrix of dependent generators of P.

Input

  • P – sparse polynomial zonotope
source
LazySets.genmat_indepMethod
genmat_indep(P::SparsePolynomialZonotope)

Return the matrix of independent generators of P.

Input

  • P – sparse polynomial zonotope
source
LazySets.expmatMethod
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.

source
LazySets.indexvectorMethod
indexvector(P::SparsePolynomialZonotope)

Return the index vector of P.

Input

  • P – sparse polynomial zonotope

Notes

The index vector is a vector of positive integers identifing the dependent parameters of P.

source
LazySets.uniqueIDMethod
uniqueID(n::Int)

Returns a collection of n unique identifiers (intergers 1, …, n).

source
LazySets.dimMethod
dim(P::SparsePolynomialZonotope)

Return the dimension of P.

Input

  • P – sparse polynomial zonotope

Output

The ambient dimension of P.

source
LazySets.ngens_depMethod
ngens_dep(P::SparsePolynomialZonotope)

Return the number of dependent generators of P.

Input

  • P – sparse polynomial zonotope
source
LazySets.ngens_indepMethod
ngens_indep(P::SparsePolynomialZonotope)

Return the number of independent generators of P.

Input

  • P – sparse polynomial zonotope
source
LazySets.nparamsMethod
nparams(P::SparsePolynomialZonotope)

Return the number of dependent parameters in the polynomial representation of P.

Input

  • P – sparse polynomial zonotope

Output

The number of dependent parameters in the polynomial representation of P.

Notes

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

source
LazySets.orderMethod
order(P::SparsePolynomialZonotope)

Return the order of P.

Input

  • P – sparse polynomial zonotope

Output

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

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

Apply the linear map M to the sparse polynomial zonotope P.

Input

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

Output

The set resulting from applying the linear map M to P.

source
LazySets.translateMethod
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.

source
LazySets.remove_redundant_generatorsMethod
remove_redundant_generators(S::SparsePolynomialZonotope)

Remove redundant generators from S.

Input

  • S – sparse polynomial zonotope

Output

A new sparse polynomial zonotope such that 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. The following simplifications are performed:

  • Zero columns in G and the corresponding columns in E are removed.
  • Zero columns in GI are removed.
  • For zero columns in E, the corresponding column in G is summed to the center.
  • Repeated columns in E are grouped together by summing the corresponding columns in G.
source
LazySets.reduce_orderFunction
reduce_order(P::SparsePolynomialZonotope, r::Real,
             [method]::AbstractReductionMethod=GIR05())

Overapproximate the sparse polynomial zonotope P by one which has at most order 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.

source