2019/05/14 by Chalkis, Apostolos, Emiris, Ioannis Z., Fisikopoulos, Vissarion
#52-04 #52-08 #52B11 #68-04 #Computational Geometry (cs.CG) #FOS: Computer and information sciences #G.3 #G.4
paper · doi:10.48550/arxiv.1905.05494
We tackle the problem of efficiently approximating the volume of convex polytopes, when these are given in three different representations: H-polytopes, which have been studied extensively, V-polytopes, and zonotopes (Z-polytopes). We design a novel practical Multiphase Monte Carlo algorithm that leverages random walks based on billiard trajectories, as well as a new empirical convergence tests and a simulated annealing schedule of adaptive convex bodies. After tuning several parameters of our proposed method, we present a detailed experimental evaluation of our tuned algorithm using a rich dataset containing Birkhoff polytopes and polytopes from structural biology. Our open-source implementation tackles problems that have been intractable so far, offering the first software to scale up in thousands of dimensions for H-polytopes and in the hundreds for V- and Z-polytopes on moderate hardware. Last, we illustrate our software in evaluating Z-polytope approximations.