Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
  • Nov 16 03:32
    mforets review_requested #710
  • Nov 16 03:32
    mforets review_requested #711
  • Nov 16 03:23
    mforets opened #1790
  • Nov 16 03:22

    mforets on 1305

    add difference for hyperrectang… update docs and add test for se… (compare)

  • Nov 16 02:56
    mforets assigned #1305
  • Nov 16 02:44
    mforets opened #711
  • Nov 16 02:44

    mforets on 699

    add dimensional check in solve! (compare)

  • Nov 16 02:36
    mforets synchronize #710
  • Nov 16 02:36

    mforets on 242

    add index 2 (compare)

  • Nov 16 02:32
    mforets edited #154
  • Nov 16 02:20
    mforets opened #710
  • Nov 16 02:20

    mforets on 242

    add example for issue 242 (compare)

  • Nov 16 02:12
    mforets labeled #452
  • Nov 16 02:10
    mforets closed #254
  • Nov 16 02:10
    mforets commented #254
  • Nov 16 01:54
    mforets closed #165
  • Nov 16 01:54
    mforets commented #165
  • Nov 14 03:45
    carlosal1015 starred JuliaReach/LazySets.jl
  • Nov 13 18:33
    IanBoyanZhang starred JuliaReach/Reachability.jl
Marcelo Forets
@mforets
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:
Christian Schilling
@schillic
actually it is not needed at all
because you just pass it to linear_map but would not use it
because you know it's invertible and the inverse is S
Marcelo Forets
@mforets
indeed
Christian Schilling
@schillic
maybe there should be a new function linear_map_inverse?
Marcelo Forets
@mforets
hmm optionally passing the extra stuff to linear_map seems better imo
Christian Schilling
@schillic
@ueliwechsler: sorry that this drifted. do you still follow? :)
Marcelo Forets
@mforets
@ueliwechsler congratulations you earned an issue! :p
hmm this is related but not the same?
we didn't speak about passing the inverse matrix there
Christian Schilling
@schillic
true, we want to do sth even faster
where you already know the inverse
Marcelo Forets
@mforets
yup
Christian Schilling
@schillic
but it's definitely related
Marcelo Forets
@mforets
ok we may want to include the optional inverse in this issue as well
this issue was some logic (my logic) broken
Christian Schilling
@schillic
ok
Marcelo Forets
@mforets
let me add a comment about this discussion.. then i'll head for lunch
Christian Schilling
@schillic
:+1:
Christian Schilling
@schillic
@ueliwechsler: it seems to me be that in your minkowski_difference the second argument is a (again: constant) BallInf. maybe that can be exploited, but from the code for minkowski_difference i don't see how
however, your inputs are zonotopes, minkowski_difference of two zonotopes is again a zonotope (not in our current implementation, but it should be easy to add a method for that; this is JuliaReach/LazySets.jl#586), and the linear map of a zonotope is again a zonotope. the "problematic" operation here is the intersection with a BallInf, which does not preserve "being a zonotope." if you are willing to pay the price of an overapproximation to a zonotope at this point, you would get rid of the remove_redundant_constraints and the linear_map would be cheap as well. but the intersection then becomes more complicated (i think there is no way around some bottleneck :P)
Christian Schilling
@schillic

for the minkowski_difference I know that I solve #constraint linear programs (therefore, it is linear in the number of constraints)

no, the implementation of minkowski_difference performs m support-function queries, which in your case are applied to a BallInf (which is very cheap)

so i'm not surprised that minkowski_difference is fast
ueliwechsler
@ueliwechsler
Thanks for your help guys! :D
Yes, I followed (but then my supervisor interrupted me)
For my problem, I most likely need to work with HPolytopes so even though the Zonotopes option sounds really interesting, I cannot use it for my current issue.
But enabling linear_map to pass the matrix S directly would be exactly what I was looking for since if I can get rid of the performance penalty of computing the inverse every iteration.
Christian Schilling
@schillic
but then my supervisor interrupted me
they tend to do that :)
ueliwechsler
@ueliwechsler
I see, so I have to be really careful with my conclusions since they depend heavily on the type 😅
Christian Schilling
@schillic
so the BallInfs are just examples?
yes, it is common that you can write a much more efficient algorithm if you know the type of set you are dealing with
and that's also why preserving more concrete types is beneficial
for instance in your first loop iteration you could work with zonotopes (assuming we have the efficient minkowski_difference) until the intersection "for free"