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.

For this analysis, the cuhre_1 algorithm did not converge even for the largest fractional error tolerance.

The integrand

The integrand chosen is: \[ | \cos(4 v +5 w + 6 x +7 y + 8 z)/k |\] with \(k = 0.6371054\). For this integrand, the normalization is approximate (meaning that the true value of the integrand is close to, but not exactly, 1.0).

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

  1. alg: the name of the algorithm
  2. epsrel: the fractional error target
  3. value: the estimated value of the integral
  4. errorest: the estimated error for the result
  5. error: the absolute difference between the estimated value and the true value
  6. neval: the number of function evaluations used
  7. nregions: the number of regions used
  8. time: the time in milliseconds for the calculation
  9. r: ratio of (errorest/(epsrel*value)); this should be less than 1 if the algorithm has converged
  10. converged: boolean showing whether r < 1

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.000000e-02 1.0193570 1.018650e-02 1.935705e-02 635817 1165 3.006238e+01 0.9993064
vegas 1.000000e-02 1.0092280 9.728969e-03 9.228036e-03 2500 -1 3.038654e+00 0.9640011
cuhre_0 5.000000e-03 1.0170300 5.083582e-03 1.703019e-02 1323777 2425 8.198374e+01 0.9996917
vegas 5.000000e-03 1.0017010 4.888609e-03 1.700786e-03 10000 -1 1.156550e+00 0.9760615
cuhre_0 2.500000e-03 1.0111440 2.527704e-03 1.114382e-02 2986347 5470 1.581575e+02 0.9999383
vegas 2.500000e-03 1.0012190 2.475480e-03 1.218622e-03 38500 -1 2.627942e+00 0.9889864
cuhre_0 1.250000e-03 1.0053700 1.256625e-03 5.369960e-03 6476925 11863 4.082045e+02 0.9999304
vegas 1.250000e-03 0.9984410 1.206065e-03 1.558969e-03 162000 -1 1.240528e+01 0.9663586
cuhre_0 6.250000e-04 1.0029770 6.268578e-04 2.977111e-03 13372359 24492 1.140364e+03 0.9999955
vegas 6.250000e-04 0.9992906 6.188393e-04 7.094402e-04 612000 -1 4.327171e+01 0.9908458
cuhre_0 3.125000e-04 1.0027560 3.133610e-04 2.755562e-03 27240213 49891 4.134043e+03 0.9999992
vegas 3.125000e-04 0.9991987 3.106578e-04 8.012821e-04 2425000 -1 1.641250e+02 0.9949022
cuhre_0 1.562500e-04 1.0019870 1.565593e-04 1.987041e-03 55238001 101169 2.568176e+04 0.9999925
vegas 1.562500e-04 0.9992357 1.556219e-04 7.642527e-04 9652500 -1 6.186660e+02 0.9967420
cuhre_0 7.812500e-05 1.0005730 7.816969e-05 5.726994e-04 110611683 202586 1.357410e+05 0.9999990
vegas 7.812500e-05 0.9992532 7.790302e-05 7.468439e-04 38513500 -1 2.217437e+03 0.9979039
cuhre_0 3.906250e-05 0.9999994 3.906236e-05 6.440957e-07 211739073 387801 5.238957e+05 0.9999970
vegas 3.906250e-05 0.9992549 3.902656e-05 7.451491e-04 153467500 -1 8.983060e+03 0.9998249
cuhre_0 1.953125e-05 1.0001000 1.953317e-05 9.960677e-05 419606733 768511 2.236608e+06 0.9999983
vegas 1.953125e-05 0.9992492 1.951648e-05 7.508123e-04 615047500 -1 3.825044e+04 0.9999946

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? For this integral, it seems to be a poor proxy for cuhre_0 and a good proxy for vegas.

Error estimate and function evaluations