Comparing VEGAS and CUHRE
Marc Paterno
6/10/2020
Purpose of this document
This document shows a comparison of the speed of the VEGAS and CUHRE algorithms, as implemented in the CUBA (http://www.feynarts.de/cuba/) library, and wrapped by cubacpp (https://bitbucket.org/mpaterno/cubacpp).
The algorithms
vegas is the Vegas algorithm of Lepage, as implemented in the CUBA library. This version uses quasi-random (low-descrepency sequence) numbers, rather than pseudo-random numbers. cuhre_0 is the serial CUHRE algorithm, as implemented in the CUBA library, using flag = 0. This version uses all the volumes produced by the algorithm for determining the final result. cuhre_1 is the serial CUHRE algorithm, as implemented in the CUBA library, using flag = 4. This version uses only the final set of volumes produced by the algorithm for determining the final result.
The integrand
The integrand used for this compa rison is:
\[ k (u v +w^{y} x y / (1 + u) + z^2) \]
where \(k\) is a normalization constant that yields an integral of 1 over the unit hypercube.
\[ k = 12 / (7 - 6 {\log(2)}^2 + \log(64)).\]
The approximate value of the \(k\) is 1.44994692592726.
Testing environment
These tests were run on a MacBook Pro laptop.
The MacBook machine used in these tests has a single 4-core 2.9 GHz Intel Core i7 processor.
Description of the dataframe
- alg: the name of the algorithm
- epsrel: the fractional error target
- value: the estimated value of the integral
- errorest: the estimated error for the result
- error: the absolute difference between the estimated value and the true value
- neval: the number of function evaluations used
- nregions: the number of regions used
- time: the time in milliseconds for the calculation
- r: ratio of (errorest/(epsrel*value)); this should be less than 1 if the algorithm has converged
A value of NA indicates that the algorithm did not converge, but rather stopped because the maximum number of function evaluations had been reached.
| alg | epsrel | value | errorest | error | neval | nregions | time | r |
|---|---|---|---|---|---|---|---|---|
| cuhre_0 | 1.000e-03 | 1.000014 | 6.813956e-04 | 1.394056e-05 | 2265 | 3 | 2.083650e-01 | 0.6813861 |
| cuhre_1 | 1.000e-03 | 1.000009 | 7.615604e-04 | 9.263730e-06 | 2265 | 3 | 2.200410e-01 | 0.7615535 |
| vegas | 1.000e-03 | 1.000225 | 9.519328e-04 | 2.254385e-04 | 45000 | -1 | 4.794768e+00 | 0.9517187 |
| cuhre_0 | 2.000e-04 | 1.000009 | 1.714239e-04 | 9.175899e-06 | 3171 | 4 | 2.186780e-01 | 0.8571118 |
| cuhre_1 | 2.000e-04 | 1.000009 | 1.771206e-04 | 8.853961e-06 | 3171 | 4 | 2.608430e-01 | 0.8855950 |
| vegas | 2.000e-04 | 1.000028 | 1.981247e-04 | 2.766858e-05 | 976000 | -1 | 6.678195e+01 | 0.9905958 |
| cuhre_0 | 4.000e-05 | 1.000002 | 3.321969e-05 | 1.895981e-06 | 6795 | 8 | 4.678000e-01 | 0.8304906 |
| cuhre_1 | 4.000e-05 | 1.000001 | 3.402270e-05 | 8.177256e-07 | 7701 | 9 | 6.027950e-01 | 0.8505666 |
| vegas | 4.000e-05 | 1.000002 | 3.996686e-05 | 2.182901e-06 | 23947000 | -1 | 1.544547e+03 | 0.9991695 |
| cuhre_0 | 8.000e-06 | 1.000001 | 7.077168e-06 | 6.572862e-07 | 10419 | 12 | 8.259690e-01 | 0.8846451 |
| cuhre_1 | 8.000e-06 | 1.000000 | 7.518407e-06 | 4.231055e-07 | 11325 | 13 | 1.038269e+00 | 0.9398009 |
| vegas | 8.000e-06 | 1.000000 | 7.997558e-06 | 1.333272e-07 | 593284500 | -1 | 3.941426e+04 | 0.9996947 |
| cuhre_0 | 1.600e-06 | 1.000000 | 1.538230e-06 | 1.955625e-07 | 15855 | 18 | 9.655430e-01 | 0.9613938 |
| cuhre_1 | 1.600e-06 | 1.000000 | 1.558443e-06 | 5.951059e-08 | 18573 | 21 | 1.124534e+00 | 0.9740269 |
| vegas | 1.600e-06 | 1.000000 | 1.599887e-06 | 6.675906e-09 | 14778257500 | -1 | 9.294607e+05 | 0.9999294 |
| cuhre_0 | 3.200e-07 | 1.000000 | 2.900560e-07 | 2.725430e-08 | 24009 | 27 | 1.555943e+00 | 0.9064250 |
| cuhre_1 | 3.200e-07 | 1.000000 | 2.544270e-07 | 2.755303e-10 | 28539 | 32 | 2.014472e+00 | 0.7950844 |
| vegas | 3.200e-07 | NA | NA | NA | 100004999500 | -1 | 6.315728e+06 | NA |
| cuhre_0 | 6.400e-08 | 1.000000 | 5.734008e-08 | 6.350508e-10 | 33975 | 38 | 2.474530e+00 | 0.8959388 |
| cuhre_1 | 6.400e-08 | 1.000000 | 6.290317e-08 | 4.330504e-10 | 40317 | 45 | 2.469669e+00 | 0.9828620 |
| cuhre_0 | 1.280e-08 | 1.000000 | 1.244865e-08 | 1.854636e-10 | 47565 | 53 | 3.220923e+00 | 0.9725508 |
| cuhre_1 | 1.280e-08 | 1.000000 | 1.263798e-08 | 3.263740e-10 | 58437 | 65 | 4.004860e+00 | 0.9873422 |
| cuhre_0 | 2.560e-09 | 1.000000 | 2.484014e-09 | 7.028640e-11 | 66591 | 74 | 3.839072e+00 | 0.9703180 |
| cuhre_1 | 2.560e-09 | 1.000000 | 2.504138e-09 | 7.034600e-12 | 86523 | 96 | 5.623580e+00 | 0.9781789 |
| cuhre_0 | 5.120e-10 | 1.000000 | 4.985302e-10 | 2.541900e-11 | 96489 | 107 | 6.767722e+00 | 0.9736918 |
| cuhre_1 | 5.120e-10 | 1.000000 | 4.957671e-10 | 1.985310e-11 | 130011 | 144 | 9.323732e+00 | 0.9682951 |
| cuhre_0 | 1.024e-10 | 1.000000 | 1.023238e-10 | 2.040930e-11 | 135447 | 150 | 9.699859e+00 | 0.9992559 |
| cuhre_1 | 1.024e-10 | 1.000000 | 1.015635e-10 | 1.482100e-12 | 198867 | 220 | 1.368961e+01 | 0.9918311 |
| cuhre_0 | 2.048e-11 | 1.000000 | 2.033960e-11 | 4.259500e-12 | 195243 | 216 | 1.369018e+01 | 0.9931440 |
| cuhre_1 | 2.048e-11 | 1.000000 | 2.031300e-11 | 3.831000e-13 | 321177 | 355 | 2.347410e+01 | 0.9918462 |
| cuhre_0 | 4.096e-12 | 1.000000 | 4.088200e-12 | 6.646000e-13 | 298527 | 330 | 1.948158e+01 | 0.9981045 |
| cuhre_1 | 4.096e-12 | 1.000000 | 4.084600e-12 | 7.090000e-14 | 533181 | 589 | 4.092434e+01 | 0.9972285 |
| cuhre_0 | 8.192e-13 | 1.000000 | 8.174000e-13 | 3.496000e-13 | 451641 | 499 | 3.048375e+01 | 0.9977582 |
| cuhre_1 | 8.192e-13 | 1.000000 | 8.189000e-13 | 2.300000e-14 | 933633 | 1031 | 6.108619e+01 | 0.9996011 |
| cuhre_0 | 1.638e-13 | 1.000000 | 1.632000e-13 | 3.870000e-14 | 719817 | 795 | 4.582027e+01 | 0.9960272 |
| cuhre_1 | 1.638e-13 | 1.000000 | 1.637000e-13 | 8.500000e-15 | 1633065 | 1803 | 8.042235e+01 | 0.9991479 |
| cuhre_0 | 3.280e-14 | 1.000000 | 3.280000e-14 | 1.920000e-14 | 1158321 | 1279 | 5.711238e+01 | 0.9997623 |
| cuhre_1 | 3.280e-14 | 1.000000 | 3.280000e-14 | 7.900000e-15 | 2813583 | 3106 | 1.365229e+02 | 0.9998782 |
| cuhre_0 | 6.600e-15 | 1.000000 | 6.600000e-15 | 8.900000e-15 | 1852317 | 2045 | 8.788493e+01 | 0.9995200 |
| cuhre_1 | 6.600e-15 | 1.000000 | 6.600000e-15 | 7.900000e-15 | 5215389 | 5757 | 2.850798e+02 | 0.9997298 |
| cuhre_0 | 1.300e-15 | 1.000000 | 1.300000e-15 | 7.500000e-15 | 2961261 | 3269 | 1.433044e+02 | 0.9995995 |
As a measure of the innate “efficiency” of each algorithm, we consider how many function evaluations are required to obtain a given fractional error tolerance.
Analysis
For this integrand, the CUHRE algorithm requires far fewer function evaluations than VEGAS to achieve a given relative error tolerance. Except for low accuracies the cuhre_0 algorithm requires fewer function evaluations than cuhre_1.
Time and function evaluations
Does the number of function evaluations make a good proxy for the time spent in integrating? It appears so, at least approximately.
Error estimate and function evaluations
For the rest of the analysis, we compare only cuhre_0 and cuhre_1.
The following table shows the number of calls to achieve a given error tolerance, and the ratio r of the number required for cuhre_1/cuhre_0.
| epsrel | cuhre_0 | cuhre_1 | r |
|---|---|---|---|
| 1.000e-03 | 2265 | 2265 | 1.000000 |
| 2.000e-04 | 3171 | 3171 | 1.000000 |
| 4.000e-05 | 6795 | 7701 | 1.133333 |
| 8.000e-06 | 10419 | 11325 | 1.086957 |
| 1.600e-06 | 15855 | 18573 | 1.171429 |
| 3.200e-07 | 24009 | 28539 | 1.188679 |
| 6.400e-08 | 33975 | 40317 | 1.186667 |
| 1.280e-08 | 47565 | 58437 | 1.228571 |
| 2.560e-09 | 66591 | 86523 | 1.299320 |
| 5.120e-10 | 96489 | 130011 | 1.347418 |
| 1.024e-10 | 135447 | 198867 | 1.468227 |
| 2.048e-11 | 195243 | 321177 | 1.645012 |
| 4.096e-12 | 298527 | 533181 | 1.786039 |
| 8.190e-13 | 451641 | 933633 | 2.067202 |
| 1.640e-13 | 719817 | 1633065 | 2.268722 |
| 3.300e-14 | 1158321 | 2813583 | 2.429018 |
| 7.000e-15 | 1852317 | 5215389 | 2.815603 |
| 1.000e-15 | 2961261 | NA | NA |