Exponential map

ExponentialMap{N, S<:LazySet{N}} <: AbstractAffineMap{N, S}

Type that represents the action of an exponential map on a set.

Fields

• spmexp – sparse matrix exponential
• X – set

Notes

The exponential map preserves convexity: if X is convex, then any exponential map of X is convex as well.

Examples

The ExponentialMap type is overloaded to the usual times * operator when the linear map is a lazy matrix exponential. For instance,

julia> using SparseArrays

julia> A = sprandn(100, 100, 0.1);

julia> E = SparseMatrixExp(A);

julia> B = BallInf(zeros(100), 1.);

julia> M = E * B; # represents the image set: exp(A) * B

julia> M isa ExponentialMap
true

julia> dim(M)
100

The application of an ExponentialMap to a ZeroSet or an EmptySet is simplified automatically.

julia> E * ZeroSet(100)
ZeroSet{Float64}(100)

julia> E * EmptySet(2)
EmptySet{Float64}(2)

dim(em::ExponentialMap)

Return the dimension of an exponential map.

Input

• em – an ExponentialMap

Output

The ambient dimension of the exponential map.

ρ(d::AbstractVector, em::ExponentialMap)

Return the support function of the exponential map.

Input

• d – direction
• em – exponential map

Output

The support function in the given direction.

Notes

If $E = \exp(M)⋅S$, where $M$ is a matrix and $S$ is a set, it follows that $ρ(d, E) = ρ(\exp(M)^T d, S)$ for any direction $d$.

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

σ(d::AbstractVector, em::ExponentialMap)

Return the support vector of the exponential map.

Input

• d – direction
• em – exponential map

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $E = \exp(M)⋅S$, where $M$ is a matrix and $S$ is a set, it follows that $σ(d, E) = \exp(M)⋅σ(\exp(M)^T d, S)$ for any direction $d$.

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

∈(x::AbstractVector, em::ExponentialMap)

Check whether a given point is contained in an exponential map of a set.

Input

• x – point/vector
• em – exponential map of a set

Output

true iff $x ∈ em$.

Algorithm

This implementation exploits that $x ∈ \exp(M)⋅S$ iff $\exp(-M)⋅x ∈ S$. This follows from $\exp(-M)⋅\exp(M) = I$ for any $M$.

Examples

julia> using SparseArrays

julia> em = ExponentialMap(
        SparseMatrixExp(sparse([1, 2], [1, 2], [2.0, 1.0], 2, 2)),
        BallInf([1., 1.], 1.));

julia> [-1.0, 1.0] ∈ em
false
julia> [1.0, 1.0] ∈ em
true

isbounded(em::ExponentialMap)

Determine whether an exponential map is bounded.

Input

• em – exponential map

Output

true iff the exponential map is bounded.

vertices_list(P::AbstractHPolygon{N};
              apply_convex_hull::Bool=true,
              check_feasibility::Bool=true) where {N}

Return the list of vertices of a polygon in constraint representation.

Input

• P – polygon in constraint representation
• apply_convex_hull – (optional, default: true) flag to post-process the intersection of constraints with a convex hull
• check_feasibility – (optional, default: true) flag to check whether the polygon was empty (required for correctness in case of empty polygons)

Output

List of vertices.

Algorithm

We compute each vertex as the intersection of consecutive lines defined by the half-spaces. If check_feasibility is active, we then check if the constraints of the polygon were actually feasible (i.e., they pointed in the right direction). For this we compute the average of all vertices and check membership in each constraint.

vertices_list(B::Ball1{N, VN}) where {N, VN<:AbstractVector}

Return the list of vertices of a ball in the 1-norm.

Input

• B – ball in the 1-norm

Output

A list containing the vertices of the ball in the 1-norm.

vertices_list(∅::EmptySet{N}) where {N}

Return the list of vertices of an empty set.

Input

• ∅ – empty set

Output

The empty list of vertices, as the empty set does not contain any vertices.

vertices_list(P::HPolytope{N};
              [backend]=nothing, [prune]::Bool=true) where {N}

Return the list of vertices of a polytope in constraint representation.

Input

• P – polytope in constraint representation
• backend – (optional, default: nothing) the polyhedral computations backend
• prune – (optional, default: true) flag to remove redundant vertices

Output

List of vertices.

Algorithm

If the polytope is two-dimensional, the polytope is converted to a polygon in H-representation and then its vertices_list function is used. This ensures that, by default, the optimized two-dimensional methods are used.

It is possible to use the Polyhedra backend in two-dimensions as well by passing, e.g. backend=CDDLib.Library().

If the polytope is not two-dimensional, the concrete polyhedra manipulation library Polyhedra is used. The actual computation is performed by a given backend; for the default backend used in LazySets see default_polyhedra_backend(P). For further information on the supported backends see Polyhedra's documentation.

vertices_list(cp::CartesianProduct{N}) where {N}

Return the list of vertices of a (polytopic) Cartesian product.

Input

• cp – Cartesian product

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

vertices_list(cpa::CartesianProductArray{N}) where {N}

Return the list of vertices of a (polytopic) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

vertices_list(em::ExponentialMap{N}) where {N}

Return the list of vertices of a (polytopic) exponential map.

Input

• em – exponential map

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polytopic. Then the result is just the exponential map applied to the vertices of X.

SparseMatrixExp{N}

Type that represents the matrix exponential, $\exp(M)$, of a sparse matrix.

Fields

• M – sparse matrix; it should be square

Examples

Take for example a random sparse matrix of dimensions $100 × 100$ and with occupation probability $0.1$:

julia> using SparseArrays

julia> A = sprandn(100, 100, 0.1);

julia> using Expokit

julia> E = SparseMatrixExp(A);

julia> size(E)
(100, 100)

Here E is a lazy representation of $\exp(A)$. To compute with E, use get_row and get_column resp. get_rows and get_columns. These functions return row and column vectors (or matrices). For example:

julia> get_row(E, 10); # compute E[10, :]

julia> get_column(E, 10); # compute E[:, 10]

julia> get_rows(E, [10]); # same as get_row(E, 10) but a 1x100 matrix is returned

julia> get_columns(E, [10]); # same as get_column(E, 10) but a 100x1 matrix is returned

Notes

This type is provided for use with very large and very sparse matrices. The evaluation of the exponential matrix action over vectors relies on the Expokit package. Hence, you will have to install and load this optional dependency to have access to the functionality of SparseMatrixExp.

    *(spmexp::SparseMatrixExp, X::LazySet)

Return the exponential map of a set from a sparse matrix exponential.

Input

• spmexp – sparse matrix exponential
• X – set

Output

The exponential map of the set.

get_row(spmexp::SparseMatrixExp{N}, i::Int) where {N}

Return a single row of a sparse matrix exponential.

Input

• spmexp – sparse matrix exponential
• i – row index

Output

A row vector corresponding to the ith row of the matrix exponential.

Notes

This function uses Julia's transpose function to create the result. The result is of type Transpose; in Julia versions older than v0.7, the result was of type RowVector.

ExponentialProjectionMap{N, S<:LazySet{N}} <: AbstractAffineMap{N, S}

Type that represents the application of a projection of a sparse matrix exponential to a set.

Fields

• spmexp – projection of a sparse matrix exponential
• X – set

Notes

The exponential projection preserves convexity: if X is convex, then any exponential projection of X is convex as well.

dim(eprojmap::ExponentialProjectionMap)

Return the dimension of a projection of an exponential map.

Input

• eprojmap – projection of an exponential map

Output

The ambient dimension of the projection of an exponential map.

σ(d::AbstractVector, eprojmap::ExponentialProjectionMap)

Return the support vector of a projection of an exponential map.

Input

• d – direction
• eprojmap – projection of an exponential map

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $S = (L⋅M⋅R)⋅X$, where $L$ and $R$ are matrices, $M$ is a matrix exponential, and $X$ is a set, it follows that $σ(d, S) = L⋅M⋅R⋅σ(R^T⋅M^T⋅L^T⋅d, X)$ for any direction $d$.

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

isbounded(eprojmap::ExponentialProjectionMap)

Determine whether an exponential projection map is bounded.

Input

• eprojmap – exponential projection map

Output

true iff the exponential projection map is bounded.

Algorithm

We first check if the left or right projection matrix is zero or the wrapped set is bounded. Otherwise, we check boundedness via LazySets._isbounded_unit_dimensions.

ProjectionSparseMatrixExp{N, MN1<:AbstractSparseMatrix{N},
                             MN2<:AbstractSparseMatrix{N},
                             MN3<:AbstractSparseMatrix{N}}

Type that represents the projection of a sparse matrix exponential, i.e., $L⋅\exp(M)⋅R$ for a given sparse matrix $M$.

Fields

• L – left multiplication matrix
• E – sparse matrix exponential
• R – right multiplication matrix

    *(projspmexp::ProjectionSparseMatrixExp, X::LazySet)

Return the application of a projection of a sparse matrix exponential to a set.

Input

• projspmexp – projection of a sparse matrix exponential
• X – set

Output

The application of the projection of a sparse matrix exponential to the set.