Volume Computation and Sampling

A MATLAB implementation that computes the volume of and samples from a convex body within a target relative error.

The volume algorithm we implemented is based on the following paper. Our implementation is available for download from MATLAB File Exchange (a more current version is maintained on Github) and detailed experimental results are described in our paper.

Overview

To use the implementation, you need to have a description of your convex body as an intersection of halfspaces (i.e. a polyhedron) and an ellipsoid. We provide some example polytopes and ellipsoids to get you started. For instance, if you want to compute the volume of a 40-dimensional cube within 20% relative error, you can type: In addition, if you wanted to obtain a single random point approximately from the uniform distribution over the same 40-dimensional cube, you can type: Please refer to the README for a brief introduction for how to use the implementation.

Download

The implementation is available for download from MATLAB File Exchange, and a potentially more current version is available from Github.

For testing the accuracy of our program, we created parallel wrappers in C and MPI to call the MATLAB program many times on a cluster. In case you will find such files useful, you can download them by clicking here.

COBRA Toolbox

In collaboration with the developers of the COBRA Toolbox, we have recently integrated a variant of the sampling procedure for use in generating random samples from a metabolic network.

Additional Info

This implementation was created by Ben Cousins and Santosh Vempala. Feel free to contact us with any questions, and you are free to use the above code without permission, it is under the BSD license.