SimpleSparsePolynomialZonotope
LazySets.SimpleSparsePolynomialZonotope
— TypeSimpleSparsePolynomialZonotope{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 vectorG
– generator matrixE
– 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.
LazySets.PolynomialZonotope
— TypePolynomialZonotope = SimpleSparsePolynomialZonotope
Alias for SimpleSparsePolynomialZonotope
.
Notes
Another shorthand is SSPZ
.
Base.rand
— Methodrand(::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 dispatchN
– (optional, default:Float64
) numeric typedim
– (optional, default: 2) dimensionnparams
– (optional, default: 2) number of parametersmaxdeg
– (optinal, default: 3) maximum degree for each parameterrng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseedingnum_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.
LazySets.center
— Methodcenter(P::SimpleSparsePolynomialZonotope)
Return the center of a simple sparse polynomial zonotope.
Input
P
– simple sparse polynomial zonotope
Output
The center of P
.
LazySets.genmat
— Methodgenmat(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
.
LazySets.expmat
— Methodexpmat(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
LazySets.dim
— Methoddim(P::SimpleSparsePolynomialZonotope)
Return the dimension of a simple sparse polynomial zonotope.
Input
P
– simple sparse polynomial zonotope
Output
The ambient dimension of P
.
LazySets.ngens
— Methodngens(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
.
LazySets.nparams
— Methodnparams(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
LazySets.order
— Methodorder(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.
LazySets.linear_map
— Methodlinear_map(M::Union{Real, AbstractMatrix, LinearAlgebra.UniformScaling},
P::SimpleSparsePolynomialZonotope)
Apply the linear map M
to a simple sparse polynomial zonotope.
Input
M
– matrixP
– simple sparse polynomial zonotope
Output
The set resulting from applying the linear map M
to P
.
LazySets.convex_hull
— Methodconvex_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
.
LazySets.quadratic_map
— Methodquadratic_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 matricesS
– 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.
LazySets.quadratic_map
— Methodquadratic_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 matricesS1
– simple sparse polynomial zonotopeS2
– 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.
LazySets.remove_redundant_generators
— Methodremove_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 inE
are removed. - For zero columns in
E
, the corresponding column inG
is summed to the center. - Repeated columns in
E
are grouped together by summing the corresponding columns inG
.