UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Efficient and Accurate Parallel Inversion of the Gamma Distribution

Luu, T; (2015) Efficient and Accurate Parallel Inversion of the Gamma Distribution. SIAM Journal on Scientific Computing , 37 (1) C122 - C141. 10.1137/14095875X. Green open access

[thumbnail of 95875.pdf]
Available under License : See the attached licence file.

Download (420kB)


A method for parallel inversion of the gamma distribution is described. This is very desirable for random number generation in Monte Carlo simulations where gamma variates are required. Let $\alpha$ be a fixed but arbitrary positive real number. Explicitly, given a list of uniformly distributed random numbers our algorithm applies the quantile function (inverse CDF) of the gamma distribution with shape parameter $\alpha$ to each element. The result is, therefore, a list of random numbers distributed according to the said distribution. The output of our algorithm has accuracy close to a choice of single- or double-precision machine epsilon. Inversion of the gamma distribution is traditionally accomplished using some form of root finding. This is known to be computationally expensive. Our algorithm departs from this paradigm by using an initialization phase to construct, on the fly, a piecewise Chebyshev polynomial approximation to a transformation function, which can be evaluated very quickly during variate generation. The Chebyshev polynomials are high order, for good accuracy, and generated via recurrence relations derived from nonlinear second order ODEs. A novelty of our approach is that the same change of variable is applied to each uniform random number before evaluating the transformation function. This is particularly amenable to implementation on SIMD architectures, whose performance is sensitive to frequently diverging execution flows due to conditional statements (branch divergence). We show the performance of a CUDA GPU implementation of our algorithm (called Quantus) is within an order of magnitude of the time to compute the normal quantile function.

Type: Article
Title: Efficient and Accurate Parallel Inversion of the Gamma Distribution
Open access status: An open access version is available from UCL Discovery
DOI: 10.1137/14095875X
Publisher version: http://dx.doi.org/10.1137/14095875X
Language: English
Additional information: © 2015, Society for Industrial and Applied Mathematics
Keywords: gamma distribution, quantile function, inverse CDF, parallel inversion, GPU, CUDA, quantile mechanics, Monte Carlo, copula, Quantus
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
URI: https://discovery.ucl.ac.uk/id/eprint/1463470
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item