UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Fast and accurate parallel computation of quantile functions for random number generation

Luu, T; (2016) Fast and accurate parallel computation of quantile functions for random number generation. Doctoral thesis , UCL (University College London). Green open access

[img]
Preview
Text
Luu_thesis.pdf

Download (1MB) | Preview

Abstract

The fast and accurate computation of quantile functions (the inverse of cumulative distribution functions) is very desirable for generating random variates from non-uniform probability distributions. This is because the quantile function of a distribution monotonically maps uniform variates to variates of the said distribution. This simple fact is the basis of the inversion method for generating non-uniform random numbers. The inversion method enjoys many significant advantages, which is why it is regarded as the best choice for random number generation. Quantile functions preserve the underlying properties of the uniform variates, which is beneficial for a number of applications, especially in modern computational finance. For example, copula and quasi-Monte Carlo methods are significantly easier to use with inversion. Inversion is also well suited to variance reduction techniques. However, for a number of key distributions, existing methods for the computational of their quantile functions are too slow in practice. The methods are also unsuited to execution on parallel architectures such as GPUs and FPGAs. These parallel architectures have become very popular, because they allow simulations to be sped up and enlarged. The original contribution of this thesis is a collection of new and practical numerical algorithms for the normal, gamma, non-central χ2 and skew-normal quantile functions. The algorithms were developed with efficient parallel computation in mind. Quantile mechanics—the differential approach to quantile functions—was used with inventive changes of variables and numerical methods to create the algorithms. The algorithms are faster or more accurate than the current state of the art on parallel architectures. The accuracy of GPU implementations of the algorithms have been benchmarked against independent CPU implementations. The results indicate that the quantile mechanics approach is a viable and powerful technique for developing quantile function approximations and algorithms.

Type: Thesis (Doctoral)
Title: Fast and accurate parallel computation of quantile functions for random number generation
Event: UCL (University College London)
Open access status: An open access version is available from UCL Discovery
Language: English
UCL classification: UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
URI: http://discovery.ucl.ac.uk/id/eprint/1482128
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item