Calculating $n$-dimensional hypervolumes ($n sim 50$), for example

Question

I have a question regarding efficient and possibly simple algorithms for computing volumes of $n$-dimensional polytopes.
The polytope of concern isn't arbitrary: it is obtained by applying a linear transformation to a unit hypercube, whose associated matrix has the form $I - L$, where $I$ is identity matrix and $L$ is an arbitrary (in reality sparse) matrix with zeros on its diagonal.
The main difficulty of the problem is that I do not need to calculate the whole volume of the polytope, but only the volume of the part lying in the first hyperoctant (i.e. whose point have all the coordinates positive). So what I really need is an algorithm to compute quickly and efficiently the volume of the intersection of a polytope and the first hyperoctant.
If it helps to know the context of the question, I am doing research in the field of complex networks, where $L$ is the adjacency matrix of a $E-R$ network. The hypervolume which I am concerned with would be a sort of a measure of resiliency of the network.

i9Fn · Answer

I'm not an expert but I think I can at least point you at the right direction.
Exact computation of volume is #P-Hard when given only vertices or only halfspaces. You can find a relevant discussion in MO979. Some software for exact computation: cdd, lrs, vinci and Qhull.
The dimension of your polytope is not very large and its H-representation (representing polytope by bounding halfspaces) requires $2n$ halfspaces for the cube after a linear transformation and another $n$ for intersecting the first hyperoctant/nonnegative orthant. The low number of halfspaces is a positive as it is much easier to compute volume when there are few halfspaces.
In the last 30 years, there has been progress in algorithms for efficiently sampling polytopes. For introduction, see Geometric Random Walks:  A Survey by Santosh Vempala and How to compute the volume in high dimension? by Miklós Simonovits. In [1], Lee and Vempala give an algorithm to compute volume of a polytope up to $epsilon$ multiplicative error in $O(mn^{2/3}epsilon^{-2}cdot mn^{w-1})$ where $n$ is number of dimension and $m$ is number of halfspaces/linear inequalities and logarithmic factors are suppressed. So for polytopes likes yours it should run in $O(n^{w+1+2/3}epsilon^{-2})$.
Some software for volume approximation: VolEsti (implements Hamiltonian Monte Carlo), polytopewalk (Vaidya walk and John walk), polyrun (Hit-and-Run, BallWalk, SphereWalk, GridWalk), PolytopeSamplerMatlab (Hamiltonian Monte Carlo) of those only VolEsti seems as mature as cdd, you can find comparsion of VolEsti to mc-stan HMC here. Out of all software mentioned I'll guess VolEsti is your best choice.
Also, are you trying to optimize the volume of the polytope subject on some constraints on $L$?
[1]: Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation by Yin Tat Lee, Santosh S. Vempala, https://arxiv.org/pdf/1710.06261.pdf

Calculating $n$-dimensional hypervolumes ($n sim 50$), for example

One Answer

Add your own answers!

Ask a Question