A practical volume algorithm
- We present a practical algorithm for computing the volume of a convex body with a target relative accuracy parameter ?>0. The convex body is given as the intersection of an explicit set of linear inequalities and an ellipsoid. The algorithm is inspired by the volume algorithms in Lovász and Vempala (J Comput Syst Sci 72(2):392–417, 2006) and Cousins and Vempala (SODA, pp. 1215–1228, 2014), but makes significant departures to improve performance, including the use of empirical convergence tests, an adaptive annealing scheme and a new rounding algorithm. We propose a benchmark of test bodies and present a detailed evaluation of our algorithm. Our results indicate that that volume computation and integration might now be practical in moderately high dimension (a few hundred) on commodity hardware.
Metadaten| Author: | Ben Cousins, Santosh Vempala |
|---|
| DOI: | https://doi.org/10.1007/s12532-015-0097-z |
|---|
| ISSN: | 1867-2949 |
|---|
| Parent Title (English): | Mathematical Programming Computation |
|---|
| Publisher: | Springer Science and Business Media LLC |
|---|
| Document Type: | Article |
|---|
| Language: | English |
|---|
| Year of Completion: | 2015 |
|---|
| Tag: | Software; Theoretical Computer Science |
|---|
| Volume: | 8 |
|---|
| Issue: | 2 |
|---|
| Page Number: | 28 |
|---|
| First Page: | 133 |
|---|
| Last Page: | 160 |
|---|
| Mathematical Programming Computation : | MPC 2016 - Issue 2 |
|---|