×

A practical volume algorithm. (English) Zbl 1341.65007

Summary: We present a practical algorithm for computing the volume of a convex body with a target relative accuracy parameter \(\varepsilon >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 by L. Lovász and S. Vempala [J. Comput. Syst. Sci. 72, No. 2, 392–417 (2006; Zbl 1090.68112)] and B. Cousins and S. Vempala [“A cubic algorithm for computing Gaussian volume”, arXiv:1306.5829], 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.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
52A38 Length, area, volume and convex sets (aspects of convex geometry)
90C27 Combinatorial optimization

Citations:

Zbl 1090.68112

Software:

VolEsti; Matlab; Volume
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Genz, A., Bretz, F.: Computation of Multivariate Normal and t Probabilities. Springer, New York (2009) · Zbl 1204.62088
[2] Iyengar, S, Evaluation of normal probabilities of symmetric regions, SIAM J. Sci. Stat. Comput., 9, 812-837, (1988) · Zbl 0642.65098
[3] Kannan, R., Li, G.: Sampling according to the multivariate normal density. In: FOCS ’96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, p. 204. IEEE Computer Society (1996) · Zbl 0941.52003
[4] Martynov, G, Evaluation of the normal distribution function, J. Soviet Math, 77, 1857-1875, (1980) · Zbl 0463.60025
[5] Schellenberger, J; Palsson, B, Use of randomized sampling for analysis of metabolic networks, J. Biol. Chem., 284, 5457-5461, (2009) · Zbl 0890.35017
[6] Somerville, PN, Numerical computation of multivariate normal and multivariate-t probabilities over convex regions, J. Comput. Graph. Stat., 7, 529-545, (1998)
[7] Dyer, M.E., Frieze, A.M., Kannan, R.: A random polynomial time algorithm for approximating the volume of convex bodies. In: STOC, pp. 375-381 (1989) · Zbl 0909.68193
[8] Dyer, ME; Frieze, AM; Kannan, R, A random polynomial-time algorithm for approximating the volume of convex bodies, J. ACM, 38, 1-17, (1991) · Zbl 0799.68107
[9] Lovász, L; Vempala, S, Simulated annealing in convex bodies and an \(O^*(n^4)\) volume algorithm, J. Comput. Syst. Sci., 72, 392-417, (2006) · Zbl 1090.68112
[10] Cousins, B., Vempala, S.: A cubic algorithm for computing Gaussian volume. In: SODA, pp. 1215-1228 (2014) · Zbl 1421.68186
[11] Cousins, B., Vempala, S.: Bypassing KLS: Gaussian cooling and an \(O^*(n^3)\) volume algorithm. In: STOC, pp. 539-548 (2015) · Zbl 1321.68434
[12] Lovász, L., Deák, I.: Computational results of an \(o^*(n^4)\) volume algorithm. Eur. J. Oper. Res. 216 (2012)
[13] Cousins, B., Vempala, S.: Volume computation of convex bodies. MATLAB File Exchange. http://www.mathworks.com/matlabcentral/fileexchange/43596-volume-computation-of-convex-bodies (2013) · Zbl 0799.68107
[14] Emiris, I., Fisikopoulos, V.: Efficient random-walk methods for approximating polytope volume. In: Proceedings of the 30th Annual Symposium on Computational Geometry, p. 318. ACM (2014) · Zbl 1395.68300
[15] Lovász, L; Vempala, S, Hit-and-run from a corner, SIAM J. Comput., 35, 985-1005, (2006) · Zbl 1103.52002
[16] Bourgain, J, Random points in isotropic convex sets, Convex Geom. Anal., 34, 53-58, (1996) · Zbl 0941.52003
[17] Rudelson, M, Random vectors in the isotropic position, J. Funct. Anal., 164, 60-72, (1999) · Zbl 0929.46021
[18] Adamczak, R; Litvak, A; Pajor, A; Tomczak-Jaegermann, N, Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles, J. Am. Math. Soc., 23, 535-561, (2010) · Zbl 1206.60006
[19] Štefankovič, D; Vempala, S; Vigoda, E, Adaptive simulated annealing: a near-optimal connection between sampling and counting, J. ACM, 56, 18-36, (2009) · Zbl 1325.68198
[20] Kannan, R; Lovász, L; Simonovits, M, Random walks and an \(O^*(n^5)\) volume algorithm for convex bodies, Random Struct. Algorithms, 11, 1-50, (1997) · Zbl 0895.60075
[21] Gillman, D.: A Chernoff bound for random walks on expander graphs. In: FOCS, pp. 680-691. IEEE Comput. Soc. Press, Los Alamitos (1993)
[22] Kannan, R; Lovász, L; Simonovits, M, Isoperimetric problems for convex bodies and a localization lemama, Discrete Comput. Geom., 13, 541-559, (1995) · Zbl 0824.52012
[23] Canfield, ER; McKay, B, The asymptotic volume of the Birkhoff polytope, Online J. Anal. Comb., 4, 4, (2009) · Zbl 1193.15034
[24] Chan, C; Robbins, D; Yuen, D, On the volume of a certain polytope, Exp. Math., 9, 91-99, (2000) · Zbl 0960.05004
[25] Loera, JA; Liu, F; Yoshida, R, A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Comb., 30, 113-139, (2009) · Zbl 1187.05009
[26] Pak, I, Four questions on Birkhoff polytope, Ann. Comb., 4, 83-90, (2000) · Zbl 0974.52010
[27] Zeilberger, D.: Proof of a conjecture of Chan, Robbins, and Yuen. Electron. Trans. Numer. Anal. 9, 147-148 (electronic) (1999) [Orthogonal polynomials: numerical and symbolic algorithms (Leganés, 1998)] · Zbl 1187.05009
[28] Beck, M; Pixton, D, The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom., 30, 623-637, (2003) · Zbl 1065.52007
[29] Chan, C; Robbins, D, On the volume of the polytope of doubly stochastic matrices, Exp. Math., 8, 291-300, (1999) · Zbl 0951.05015
[30] Dyer, M; Gritzmann, P; Hufnagel, A, On the complexity of computing mixed volumes, SIAM J. Comput., 27, 356-400, (1998) · Zbl 0909.68193
[31] Cousins, B., Vempala, S.: Volume computation and sampling. http://www.cc.gatech.edu/ bcousins/volume.html (2013) · Zbl 1321.68434
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.