SimpleSparsePolynomialZonotope

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 [1]. The simple variation was defined in [2].

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

Representation for Reachability Analysis*. Transactions on Automatic Control,

• [2] N. Kochdumper. Challenge Problem 5: Polynomial Zonotopes in Julia.

JuliaReach and JuliaIntervals Days 3, 2021.

PolynomialZonotope = SimpleSparsePolynomialZonotope

Alias for SimpleSparsePolynomialZonotope.

Notes

Another shorthand is SSPZ.

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

Output

A random simple 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 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.

center(P::SimpleSparsePolynomialZonotope)

Return the center of a simple sparse polynomial zonotope.

Input

• P – simple sparse polynomial zonotope

Output

The center of P.

genmat(P::SimpleSparsePolynomialZonotope)

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

Input

• P – simple sparse polynomial zonotope

Output

The matrix of generators of P.

expmat(P::SimpleSparsePolynomialZonotope)

Return the matrix of exponents of a simple 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 mathematical set definition) and each column corresponds 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

dim(P::SimpleSparsePolynomialZonotope)

Return the dimension of a simple sparse polynomial zonotope.

Input

• P – simple sparse polynomial zonotope

Output

The ambient dimension of P.

ngens(P::SimpleSparsePolynomialZonotope)

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

Input

• P – simple sparse polynomial zonotope

Output

The number of generators of P.

Notes

This number corresponds to the number of monomials in the polynomial representation of P.

nparams(P::SimpleSparsePolynomialZonotope)

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

Input

• P – simple sparse polynomial zonotope

Output

The number of parameters in the polynomial representation of P.

Notes

This number corresponds to the number of rows in the exponent matrix $E$ (p in the mathematical 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

order(P::SimpleSparsePolynomialZonotope)

Return the order of a simple sparse polynomial zonotope.

Input

• P – simple sparse polynomial zonotope

Output

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

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

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

Input

• M – matrix
• P – simple sparse polynomial zonotope

Output

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

convex_hull(P::SimpleSparsePolynomialZonotope)

Compute the convex hull of a simple sparse polynomial zonotope.

Input

• P – simple sparse polynomial zonotope

Output

The tightest convex simple sparse polynomial zonotope containing P.

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

Return the quadratic map of a simple sparse polynomial zonotope.

Input

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

Output

The quadratic map of P represented as a simple sparse 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.

quadratic_map(Q::Vector{MT}, S1::SimpleSparsePolynomialZonotope,
              S2::SimpleSparsePolynomialZonotope)
    where {N, MT<:AbstractMatrix{N}}

Return the quadratic map of two simple sparse polynomial zonotopes. The quadratic map is the set $\{x | xᵢ = s₁ᵀQᵢs₂, s₁ ∈ S₁, s₂ ∈ S₂, Qᵢ ∈ Q\}$.

Input

• Q – vector of square matrices
• S1 – simple sparse polynomial zonotope
• S2 – simple sparse polynomial zonotope

Output

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

Algorithm

This method implements Proposition 3.1.30 in [1].

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

remove_redundant_generators(S::SimpleSparsePolynomialZonotope)

Remove redundant generators from a simple sparse polynomial zonotope.

Input

• S – simple sparse polynomial zonotope

Output

A new simple 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 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 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.