A parallel implementation of an $$O^*(n^4)$$ O ∗ ( n 4 ) volume algorithm

Recently an $$O^*(n^4)$$ O ∗ ( n 4 ) volume algorithm has been presented for convex bodies by Lovasz and Vempala, where $$n$$ n is the number of dimensions of the convex body. Essentially the algorithm consists of several, interlocked simulational steps of slightly different natures. A computer implementation was later developed to gather some information about the numerical aspects of the algorithm, the number of dimensions in the examples was at most 10, and the errors of the results were somewhat dissatisfying. Now we present a parallel version of the improved algorithm, where variance reducing was added to make the algorithm faster, and the use of a GPU with 480 processors made experimentation easier. Computational results for convex bodies in dimensions ranging from 2 to 20 are presented as well. Copyright Springer-Verlag Berlin Heidelberg 2015