search

GeomScale / volesti

Practical volume computation and sampling in high dimensions
GNU Lesser General Public License v3.0
144 stars 113 forks source link

Implement boundary oracle for integral collocation method #121

Open papachristoumarios opened 3 years ago

papachristoumarios commented 3 years ago

The Integral Collocation method of this paper is implemented in volesti under include/ode_solvers/integral_collocation.hpp.

The current state of the solver does not include a boundary oracle (and thus it does not currently support truncation).

The goal of this feature request is to implement a boundary oracle for the method. More specifically the boundary oracle method has to solve the intersection of the trajectory (computed via Lagrange interpolation at the Chebyshev nodes) which is defined by its Chebyshev transform (via using the Chebyshev transform class provided in boost) with the boundary of the H-polytope.

To solve it effectively, I propose converting the Chebyshev transform to a complex polynomial of twice the degree such that the real part of its roots represent solutions of the equation.

So, all in all, we need to

  1. Compute the polynomial of twice the degree (already implemented)
  2. Compute the integral of this polynomial (a[k] x^k -> a[k] / (k + 1) x^{k + 1})
  3. Project on each of the facet normals and solve the corresponding polynomial equation numerically (e.g. with MPSolve)
  4. Keep the smallest positive of the real parts of the complex roots
JRS296 commented 11 months ago

@vissarion I'd like to know the status of this issue, has it been solved yet? and if not, if I can help.

vissarion commented 11 months ago

Hi @JRS296 thanks for your interest I do not know if this issue is the right to get started. I propose to choose one issue from https://github.com/GeomScale/volesti/issues?q=is%3Aissue+is%3Aopen+label%3A%22good+first+issue%22