Change representation of multiple domains in ODE solvers interface

[papachristoumarios]

Instead of defining std::vector<Polytope*> to represent a list which has elements either a Polytope
or NULL to represent R^d.

We want to change this structure to std::vector<Polytope> and the representation of R^d should be
handled inside the corresponding polytope classes.

[vaithak]

Hi @papachristoumarios, I want to give this a try. Can you give some more details about this?

[papachristoumarios]

Hi @vaithak,

The question refers to refactoring the current ODE solvers to take vectors of polytopes (or references to polytopes) and not pointers (see here: https://github.com/papachristoumarios/volume_approximation/blob/icml-2021/include/ode_solvers/leapfrog.hpp).

In the existing implementation, we have assumed that the euclidean space R^d is represented by a NULL pointer. The reason for defining R^d as NULL is currently so as not to run the code to calculate boundary reflections and, instead, proceed with running the solver as is.

Please let me know in case you have any questions.

[papachristoumarios]

The whole reason behind this is better (and less error-prone) memory management.

[vaithak]

@papachristoumarios I think this can be solved by representing R^d as a polytope with each coordinate from -inf to inf, also we need to make appropriate changes if necessary in computing intersections and reflections. This would mean that line_itersect step here would be computed for each polytope irrespective of whether it's bounded or not.
What do you think about this?

[papachristoumarios]

Hi @vaithak,

If R^d can be represented as an instance (and preferably a singleton) of a Polytope-type class, all the oracles (membership, line intersection etc.) must return answers in O(1) time. That said, you should have a boolean flag in the polytope classes indicating this case and you should place if statements at the start of the desired methods. That said, it is not efficient to run any of the code that any of these methods include (you will end up paying extra costs by checking if variables belong to (-inf, inf) which is not good at any case). Moreover, the euclidean space, as a matter of mathematical formality is not a convex polytope, so in terms of design principles doing that will make the code less readable and may confuse others who want to use it, and in fact that's why I used NULL pointers from the beginning to represent it (of course with the shortfall of a not that great memory management scheme).

Thank you!

[vaithak]

Thanks for replying 🙂. Yup, I get your point. I am currently stuck in some other thing so didn't get a lot time to look at the code, will do it soon. What I was thinking was, in ODE solvers hpolytopes are used for bounds, right ? And as you suggested, it wont be right to also consider R^d as a polytope, so how about we instead make another class - Bounds (or InputSpace) or anything similar to handle this. In that we can have a boolean variable for R^d, and also have an hpolytope inside it in case the space is not complete R^d.

[papachristoumarios]

Thanks! Yes you can do something like this. Moreover we are striving for simplicity regrading the techniques we use so that the resulting code is fast (that's why almost all classes are templated, we do not use inheritance and so on). If in the case of very large tests there's insignificant increase in the runtime then we can have it. Also cc'ing @vissarion.