Inverse linear map (InverseLinearMap)

InverseLinearMap{N, S<:LazySet{N}, NM, MAT<:AbstractMatrix{NM}} <: AbstractAffineMap{N, S}

Given a linear transformation $M$, this type represents the linear transformation $M⁻¹⋅X$ of a set $X$ without actually computing $M⁻¹$.

Fields

• M – invertible matrix
• X – set

Notes

This type is parametric in the elements of the inverse linear map, NM, which is independent of the numeric type of the wrapped set (N). Typically NM = N, but there may be exceptions, e.g., if NM is an interval that holds numbers of type N, where N is a floating point number type such as Float64.

Examples

For the examples we create a $3×3$ matrix and a unit three-dimensional square.

julia> A = [1 2 3; 2 3 1; 3 1 2];

julia> X = BallInf([0, 0, 0], 1);

julia> ilm = InverseLinearMap(A, X)
InverseLinearMap{Int64,BallInf{Int64,Array{Int64,1}},Int64,Array{Int64,2}}([1 2 3; 2 3 1; 3 1 2], BallInf{Int64,Array{Int64,1}}([0, 0, 0], 1))

Applying an inverse linear map to a InverseLinearMap object combines the two maps into a single InverseLinearMap instance.

julia> B = transpose(A); ilm2 = InverseLinearMap(B, ilm)
InverseLinearMap{Int64,BallInf{Int64,Array{Int64,1}},Int64,Array{Int64,2}}([14 11 11; 11 14 11; 11 11 14], BallInf{Int64,Array{Int64,1}}([0, 0, 0], 1))

julia> ilm2.M == A*B
true

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

julia> InverseLinearMap(A, ZeroSet{Int}(3))
ZeroSet{Int64}(3)

dim(ilm::InverseLinearMap)

Return the dimension of an inverse linear map.

Input

• ilm – inverse linear map

Output

The ambient dimension of the inverse linear map.

σ(d::AbstractVector, ilm::InverseLinearMap)

Return the support vector of the inverse linear map.

Input

• d – direction
• ilm – inverse linear map

Output

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

Notes

If $L = M^{-1}⋅X$, where $M$ is a matrix and $X$ is a set, since (M^T)^{-1}=(M^{-1})^T, it follows that $σ(d, L) = M^{-1}⋅σ((M^T)^{-1} d, X)$ for any direction $d$.

ρ(d::AbstractVector, ilm::InverseLinearMap)

Return the support function of the inverse linear map.

Input

• d – direction
• ilm – inverse linear map

Output

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

Notes

If $L = M^{-1}⋅X$, where $M$ is a matrix and $X$ is a set, it follows that $ρ(d, L) = ρ((M^T)^{-1} d, X)$ for any direction $d$.

∈(x::AbstractVector, ilm::InverseLinearMap)

Check whether a given point is contained in the inverse linear map of a set.

Input

• x – point/vector
• ilm – inverse linear map of a set

Output

true iff $x ∈ ilm$.

Algorithm

This implementation does not explicitly invert the matrix since it uses the property $x ∈ M^{-1}⋅X$ iff $M⋅x ∈ X$.

Examples

julia> ilm = LinearMap([0.5 0.0; 0.0 -0.5], BallInf([0., 0.], 1.));

julia> [1.0, 1.0] ∈ ilm
false

julia> [0.1, 0.1] ∈ ilm
true

an_element(ilm::InverseLinearMap)

Return some element of an inverse linear map.

Input

• ilm – inverse linear map

Output

An element in the inverse linear map. It relies on the an_element function of the wrapped set.

vertices_list(ilm::InverseLinearMap; prune::Bool=true)

Return the list of vertices of a (polyhedral) inverse linear map.

Input

• ilm – inverse linear map
• prune – (optional, default: true) if true removes redundant vertices

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polyhedral. Then the result is just the inverse linear map applied to the vertices of X.

constraints_list(ilm::InverseLinearMap)

Return the list of constraints of a (polyhedral) inverse linear map.

Input

• ilm – inverse linear map

Output

The list of constraints of the inverse linear map.

Notes

We assume that the underlying set X is polyhedral, i.e., offers a method constraints_list(X).

Algorithm

We fall back to a concrete set representation and apply linear_map_inverse.

linear_map(M::AbstractMatrix, ilm::InverseLinearMap)

Return the linear map of a lazy inverse linear map.

Input

• M – matrix
• ilm – inverse linear map

Output

The set representing the linear map of the lazy inverse linear map of a set.

Notes

This implementation is inefficient because it will compute the concrete inverse of $M$, which is what InverseLinearMap is supposed to avoid.