forum.polymake.org

I am wondering if there is a method or superior representation I am unaware of that may lead to faster volume computations for some polytopes. I have posted an example script with sample output http://goo.gl/3dVu4Z that does not terminate within 24 hrs given 40GB of memory.

I can post another example that suffers from the same problem if that would be helpful. I appreciate your time in helping me either to understand why I am asking for something impossible or to make better use of polymake.

Computing the exact volume of a polytope is known to be #P-hard by a result of Dyer and Frieze. See here for a quick overview (and the reference).

polymake computes the (exact) volume by triangulating the polytope. This is implemented via the beneath-and-beyond method. The key factor in the running time is the size of the triangulation computed. For an estimation of the running time, e.g., see my paper "Beneath-and-beyond revisited", Algebra, geometry, and software systems, 1-21, Springer, Berlin, 2003. The problem is that there are polytopes which may look small (few vertices and few facets) but still every one of their triangulations is huge. In that sense you might just be unlucky. You can try to sort your vertices in a different way ("placing_triangulation" takes a permutation as an optional parameter), but this is not guaranteed to give you anything better.

Presumably, the best method to compute volumes approximately is Lovász, László and Vempala, Santosh: "Simulated annealing in convex bodies and an $O^*(n^4)$ volume algorithm". J. Comput. System Sci. 72 (2006), no. 2, 392-417. However, I am not aware of an implementation available. In particular, polymake does not do that (as we are less interested in approximate results).

Thank you very much for the response and the references. I contacted Santosh Vempala and he kindly sent me a link to a recent paper and an associated MATLAB implementation:

B. Cousins and S. Vempala, A Cubic Algorithm for Computing Gaussian Volume. 2013. arXiv:1306.5829.