GeomScale / volesti

Practical volume computation and sampling in high dimensions
GNU Lesser General Public License v3.0
144 stars 113 forks source link

Wrong volume computation #219

Closed masinag closed 2 years ago

masinag commented 2 years ago

I'm currently using VolEsti to compute the integral of polynomials over polytopes. Generally it works very well, however I noticed that sometimes the output is very far from the expected result. For instance, I had to compute the volume of the following HPolytope. I have a file polytope.hrep containing:

32 11
-76389 0 0 0 0 0 0 1 0 0 0 
8233704 0 0 0 0 0 0 -1 0 0 0 
0 0 0 1 0 0 0 0 0 0 0 
9 0 0 -1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 
9 0 0 0 0 0 0 0 0 0 -1 
0 0 0 0 0 0 0 0 0 1 0 
9 0 0 0 0 0 0 0 0 -1 0 
0 0 0 0 1 0 0 0 0 0 0 
9 0 0 0 -1 0 0 0 0 0 0 
36028797018963968 0 0 0 0 0 0 0 -129658016926324768 -8556591871763881 0 
0 0 0 0 0 0 0 0 1 0 0 
9 0 0 0 0 0 0 0 -1 0 0 
0 1 0 0 0 0 0 0 0 0 0 
9 -1 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 
9 0 -1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 0 
9 0 0 0 0 0 -1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 
8 0 0 0 0 -1 0 0 0 0 0 
1350371 0 0 0 0 0 0 -1 0 0 0 
5 0 0 0 0 -2 0 0 0 0 0 
5 -2 0 0 0 0 0 0 0 0 0 
-2228053 0 0 0 0 0 0 2 0 0 0 
7 0 0 0 0 0 0 0 -2 0 0 
5 0 0 0 0 0 0 0 -2 0 0 
3 -2 0 0 0 0 0 0 0 0 0 
-3 0 0 0 0 2 0 0 0 0 0 
7 0 0 0 0 0 -2 0 0 0 0 
-5 0 0 0 0 0 2 0 0 0 0 
5 0 0 0 0 0 0 0 0 -1 0

If I try to compute the volume of this polytope using the code of examples/hpolytope-volume/hpolytopeVolume.cpp, the output I get is:

Using Cooling Balls method: 18395.5
Using Cooling Gaussians method: 105710
Using Sequence of Balls method: 206202

However, by computing the volume of this polytope with other tools such as LattE Integrale, with:

integrate --valuation=volume --cone-decompose polytope.hrep

The value I obtain is much bigger: 1360743071.7557908012968907483976 This value should be correct since I obtain the same result with symbolic integration methods.

Any guess on why this happens? Can it be something related to loss of floating point precision?

masinag commented 2 years ago

Solved by using CoolingBalls with CDHR random walk