search

GeomScale / volesti

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

Khachiyan algorithm for Minimum Volume Enclosing Ellipsoids #103

Closed vissarion closed 3 years ago

vissarion commented 4 years ago

Is your feature request related to a problem? Please describe. Reimplement or find a more efficient implementation for Khachiyan algorithm for Minimum Volume Enclosing Ellipsoids. See https://people.orie.cornell.edu/miketodd/TYKhach.pdf as a reference. Currently we use this code https://github.com/GeomScale/volume_approximation/tree/develop/external/minimum_ellipsoid which depends on ublas. Even changing this code to use Eigen or lapack could result in more efficient implementation. Currently, the implementation is very efficient for d<200.

A CGAL function is also available: https://doc.cgal.org/latest/Bounding_volumes/classCGAL_1_1Approximate__min__ellipsoid__d.html and used by volesti in the past.

@TolisChal feel free to add more information and/or benchmarks if available.

vaithak commented 3 years ago

I have created a PR for replacing ublas with Eigen, currently one of the test case is failing on my system ("volume_cb_uniform_zonotope"). I am debugging it, it would be great if anyone can help me in finding what is causing the test case to fail ?

Edit: I have fixed the code which was causing one test case to fail.

vissarion commented 3 years ago

We are not dependent on this part of code any more so https://github.com/GeomScale/volume_approximation/pull/129 is enough to close this issue.