# SimpleSparsePolynomialZonotope

LazySets.SimpleSparsePolynomialZonotopeType
SimpleSparsePolynomialZonotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N}, ME<:AbstractMatrix{<:Integer}} <: AbstractPolynomialZonotope{N}

Type that represents a sparse polynomial zonotope that is simple in the sense that there is no distinction between independent and dependent generators.

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

$$$\mathcal{PZ} = \left\{x \in \mathbb{R}^n : x = c + \sum_{i=1}^h \left(\prod_{k=1}^p \alpha_k^{E_{k, i}} \right) g_i,~~ \alpha_k \in [-1, 1]~~ \forall i = 1,\ldots,p \right\},$$$

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

Fields

• c – offset vector
• G – generator matrix
• E – exponent matrix

Notes

Sparse polynomial zonotopes were introduced in [KA21]. The simple variation was defined in [K22].

• [KA21] N. Kochdumper and M. Althoff. Sparse Polynomial Zonotopes: A Novel Set Representation for Reachability Analysis. Transactions on Automatic Control, 2021.
• [K21] N. Kochdumper. Challenge Problem 5: Polynomial Zonotopes in Julia. JuliaReach and JuliaIntervals Days 3, 2021.
source
Base.randMethod
rand(::Type{SimpleSparsePolynomialZonotope};
[N]::Type{<:Real}=Float64, [dim]::Int=2, [nparams]::Int=2, [maxdeg]::Int=3,
[num_generators]::Int=-1,
[rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random 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_generators – (optional, default: -1) number of generators of the zonotope (see comment below)

Output

A random zonotope.

Algorithm

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

The number of generators can be controlled with the argument num_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::SimpleSparsePolynomialZonotope)

Return the center of P.

Input

• P – simple sparse polynomial zonotope

Output

The center of P.

source
LazySets.genmatMethod
genmat(P::SimpleSparsePolynomialZonotope)

Return the matrix of generators of P.

Input

• P – simple sparse polynomial zonotope

Output

The matrix of generators of P.

source
LazySets.expmatMethod
expmat(P::SimpleSparsePolynomialZonotope)

Return the matrix of exponents of the sparse polynomial zonotope.

Input

• P – simple 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.

Examples

julia> S = SimpleSparsePolynomialZonotope([2.0, 0], [1 2;2 2.], [1 4;1 2])
SimpleSparsePolynomialZonotope{Float64, Vector{Float64}, Matrix{Float64}, Matrix{Int64}}([2.0, 0.0], [1.0 2.0; 2.0 2.0], [1 4; 1 2])

julia> expmat(S)
2×2 Matrix{Int64}:
1  4
1  2
source
LazySets.dimMethod
dim(P::SimpleSparsePolynomialZonotope)

Return the dimension of P.

Input

• P – simple sparse polynomial zonotope

Output

The ambient dimension of P.

source
LazySets.ngensMethod
ngens(P::SimpleSparsePolynomialZonotope)

Return the number of generators of P.

Input

• P – simple sparse polynomial zonotope

Output

The number of generators of P.

Notes

This is equivalent to the number of monomials in the polynomial representation of P.

source
LazySets.nparamsMethod
nparams(P::SimpleSparsePolynomialZonotope)

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

Input

• P – simple sparse polynomial zonotope

Output

The number of parameters in the polynomial representation of P.

Notes

This corresponds to the number rows in the exponent matrix $E$ (p in the set definition).

Examples

julia> S = SimpleSparsePolynomialZonotope([2.0, 0], [1 2;2 2.], [1 4;1 2])
SimpleSparsePolynomialZonotope{Float64, Vector{Float64}, Matrix{Float64}, Matrix{Int64}}([2.0, 0.0], [1.0 2.0; 2.0 2.0], [1 4; 1 2])

julia> nparams(S)
2
source
LazySets.orderMethod
order(P::SimpleSparsePolynomialZonotope)

Return the order of P.

Input

• P – simple 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::SimpleSparsePolynomialZonotope)

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

Input

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

Output

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

source
LazySets.minkowski_sumMethod
minkowski_sum(P1::SimpleSparsePolynomialZonotope, P2::SimpleSparsePolynomialZonotope)

computes the Minkowski sum of the simple sparse polynomial zonotopes P1 and P2.

Input

• P1 – simple sparse polynomial zonotope
• P2 – simple sparse polynomial zonotope

Output

The Minkowski sum of P1 and P2

source
LazySets.cartesian_productMethod
cartesian_product(P1::SimpleSparsePolynomialZonotope, P2::SimpleSparsePolynomialZonotope)

computes the cartesian product of the simple sparse polynomial zonotopes P1 and P2.

Input

• P1 – simple sparse polynomial zonotope
• P2 – simple sparse polynomial zonotope

Output

The cartesian product of P1 and P2

source
LazySets.linear_combinationMethod
linear_combination(P1::SimpleSparsePolynomialZonotope, P2::SimpleSparsePolynomialZonotope)

Compute the linear combination of simple sparse polynomial zonotopes P1 and P2.

Input

• P1 – simple sparse polynomial zonotope
• P2 – simple sparse polynomial zonotope

Output

Linear combination of P1 and P2.

Notes

The linear combination of two sets $P₁$ and $P₂$ is defined as

$$$\{1/2(1+λ)p₁ + 1/2(1-λ)p₂ | p₁ ∈ P₁, p₂ ∈ P₂, λ ∈ [-1, 1]\}.$$$
source
LazySets.convex_hullMethod
convex_hull(P1::SimpleSparsePolynomialZonotope, P2::SimpleSparsePolynomialZonotope)

Computes the convex hull of the simple sparse polynomial zonotopes P1 and P2.

Input

• P1 : simple sparse polynomial zonotopes
• P2 : simple sparse polynomial zonotopes

Output

Tightest convex simple sparse polynomial zonotope containing P1 and P2.

source
LazySets.convex_hullMethod
convex_hull(P::SimpleSparsePolynomialZonotope)

Computes the convex hull of the simple sparse polynomial zonotope P.

Input

• P – simple sparse polynomial zonotopes

Output

Tightest convex simple sparse polynomial zonotope containing P.

source
LazySets.quadratic_mapMethod
quadratic_map(Q::Vector{MT}, S::SimpleSparsePolynomialZonotope) where {N, MT<:AbstractMatrix{N}}

Return an overapproximation of the quadratic map of the given polynomial zonotope.

Input

• Q – vector of square matrices
• S – simple sparse polynomial zonotope

Output

The quadratic map of the given zonotope represented as a polynomial zonotope.

Algorithm

This method implements Proposition 12 in [1]. See also Proposition 3.1.30 in [2].

[1] N. Kochdumper, M. Althoff. Sparse polynomial zonotopes: A novel set representation for reachability analysis. 2021 [2] N. Kochdumper. Extensions of polynomial zonotopes and their application to verification of cyber-physical systems. 2021.

source
LazySets.remove_redundant_generatorsMethod
remove_redundant_generators(S::SimpleSparsePolynomialZonotope)

Remove redundant generators from S.

Input

• S – simple sparse polynomial zonotope

Output

A new simple simple sparse polynomial zonotope such that redundant generators have been reduced.

Notes

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

Algorithm

Let G be the generator matrix and E the exponent matrix of S. The following simplifications are performed:

• Zero columns in G and the corresponding columns in E are eliminated.
• 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