## Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
##### Activity
• 19:21
mforets opened #28
• 17:06

mforets on tmjets_mince

• 16:00

mforets on tmjets_mince

• 12:35
mforets labeled #194
• 12:35
mforets opened #194
• 12:10
mforets labeled #2014
• 12:10
mforets edited #2014
• 12:10
mforets edited #2014
• 12:08
mforets opened #2014
• 08:09
schillic commented #1982
• 08:05
mforets commented #1982
• 07:53
schillic commented #1982
• 07:51
mforets commented #1982
• 07:46
schillic commented #1982
• 07:43
schillic commented #1982
• 07:24
mforets commented #1982
• 07:23
mforets commented #1982
• 07:21
mforets commented #1982
• 07:15
mforets commented #1982
• 07:15

mforets on gh-pages

build based on 9574153 (compare)

ueliwechsler
@ueliwechsler
I don't think that it is slow, but I am wondering if I can improve on the performance and how it competes with other tools or languages (MATLAB, C++)?
Christian Schilling
@schillic
Is there a way to speed this up? E.g. by not needing to compute the inverse of the linear_map every call.
so do you call this code in a loop while S is it always the same matrix?
i think currently there is no way to pass the inverted matrix, but yes, this could save some time indeed
ueliwechsler
@ueliwechsler
Exactly, I am using the same S every loop. I am preparing an MVP.
Marcelo Forets
@mforets

I can "speed up" the code by omitting to remove the redundant constraints
by adding the constraints like this.

there is an optional kwarg for this: prune=false

https://juliareach.github.io/LazySets.jl/latest/lib/binary_functions/#LazySets.intersection-Union{Tuple{N},%20Tuple{AbstractHPolygon{N},AbstractHPolygon{N}},%20Tuple{AbstractHPolygon{N},AbstractHPolygon{N},Bool}}%20where%20N%3C:Real

Christian Schilling
@schillic
but this is only for polygons, right?
Marcelo Forets
@mforets
indeed
Christian Schilling
@schillic
and it's not in the signature! :O
Marcelo Forets
@mforets
indeed
Christian Schilling
@schillic
shame on us
Marcelo Forets
@mforets
i think i didn't understand the question.. which is the slow operation?
perhaps my question is: what is the result (set type) of minkowski_difference(P, W)
ueliwechsler
@ueliwechsler
The result from minkowski_difference(P,W) is a HPolytopeor HPolyhedron if it is not bounded.
Marcelo Forets
@mforets
ok
ueliwechsler
@ueliwechsler
using LazySets
function maximal_RPI_set(S, 𝒲::LazySet, 𝒟::LazySet)
S_inv = inv(S)
𝒫 = 𝒟
k = 0
while true
k +=1
# concrete set operations (S_inv⋅𝒫 ⊖ 𝒲) ∩ 𝒟
𝒫⁺ = intersection(linear_map(S_inv, minkowski_difference(𝒫,𝒲)), 𝒟)
if (𝒫⁺ ⊆ 𝒫 && 𝒫 ⊆ 𝒫⁺)
break
end
𝒫 = 𝒫⁺
end
return 𝒫, k
end

n = 2
W = BallInf(zeros(n), 0.25)
D = BallInf(zeros(n), 5.0)
# Schur Matrix S
S = [0.755 0.7; 0.0 0.75]
@time maximal_RPI_set(S, W, D)
Marcelo Forets
@mforets
so the question is if one can compute $(A^{-1} X ) \cap D$ (concretely) in some other way
where $X$ is the minkowski difference
ueliwechsler
@ueliwechsler
yes!
And also, I'd like to figure out, how the computational complexity of linear_map growths with the number of constraints?
And to do that, I first wanted to have a really performant code.
Marcelo Forets
@mforets
you know S and S_inv
can't we use the information to quickly compute the action of the linear map to the HPOlytope
i think we had an open issue for this
@schillic this was your idea ?
ueliwechsler
@ueliwechsler
For example, for the minkowski_difference I know that I solve #constraint linear programs (therefore, it is linear in the number of constraints) and I was surprised, that the linear_map does take significantly more time than the minkowski_differnence and now, I try to figure out why exactly.
Or does it make totally sense, that the linear_map takes more time?
Marcelo Forets
@mforets
well it depends
they are very fast if the sets are zonotopic
since then linear maps are just the action over the generators
Christian Schilling
@schillic
yes, to have an option to pass the inverted matrix
Marcelo Forets
@mforets
but if the output of your minkowski_difference is not zonotopic (if it is a general HPolytope) then you have to transform one by one the constraints
if the matrix is invertible then the linear map can be computed without passing to the vrep
it is easy, just see how it transforms each constraints
in the general case (the matrix is not invertible) you have to pass to the vertex representation and this can be expensive
Christian Schilling
@schillic
matrix inversion is i think cubic
Marcelo Forets
@mforets
yes, but it is computed only once in his function
Christian Schilling
@schillic
no
linear_map inverts again
there should be an option to pass S directly
Marcelo Forets
@mforets
no? i would pass S to linear_map
Christian Schilling
@schillic
but that's a different problem statement
and still
Marcelo Forets
@mforets
certainly, i wanted to say that there seems to be room for improvement
if we pass S to linear_map
Christian Schilling
@schillic
isn't that what i said?
there should be an option to pass S directly
maybe our messages crossed
Marcelo Forets
@mforets

yes, but it is computed only once in his function

it is needed to be computed only once in his function, this is what i meant

Christian Schilling
@schillic
i think we agree that there should be an option to pass the inverted matrix
Marcelo Forets
@mforets
:thumbsup: