Deterministic algorithm for optimising the direction numbers of the Sobol’ sequence
Keywords:
quasi-Monte Carlo method, Sobol’ sequence, High Performance ComputinAbstract
The quasi-Monte Carlo (QMC) methods use deterministic, usually low-discrepancy sequences, to improve the order of convergence when compared with Monte Carlo methods dealing with the same problem. Although this improved convergence depends on the smoothness properties of the functions under consideration and sometimes cannot be established theoretically, good practical results were obtained in many areas, notably in Financial Mathematics. Most of the QMC methods do not depend on particular properties of the sequences used beyond their good distribution in a suitable multidimensional space. Many families of low-discrepancy sequences have been studies, with the family of the Sobol sequences being not only one of the oldest but also the most popular in practical applications. Since these sequences have many free parameters, it is desirable to have methods to obtain a good set of parameters, suitable for a wide class of problems. In this work we propose a fully deterministic method for optimisation of the direction numbers of the Sobol sequences that is flexible in taking into account smoothness properties of the potential sub-integral functions. We demonstrate how by implementing this algorithm on modern GPUs it is possible to obtain good sets of direction numbers within a reasonable timeframe. The numerical tests demonstrate the significant advantage in terms of accuracy that is observed, which makes the corresponding QMC methods even more competitive.
References
E. Atanassov, S. Ivanovska, A. Karaivanova. Optimization of the Direction Numbers of the Sobol Sequences. Studies in Computational Intelligence, 902 SCI, 2021, 145–154.
NVIDIA CUDA Toolkit. https://developer.nvidia.com/cuda-toolkit. Last accessed 7 Feb 2021.
A. Owen. Scrambling Sobol’ and Niederreiter-Xing points. Journal of Complexity, 14 (1998), 466–489.
Software for generating the Sobol sequences by BRODA. https://www.broda.co.uk/software.html. Last accessed 7 Feb 2021.
IEEE Standard for Floating-Point Arithmetic. In: IEEE Std 754-2008 , 1–70, 29 Aug. 2008, doi: 10.1109/IEEESTD.2008.4610935.
L. Kuipers, H. Niederreiter. Uniform Distribution of Sequences, New York, Dover Publications, 2006.
N. M. Korobov. The approximate computation of multiple integrals. Dokl. Akad. Nauk SSSR, 124 (1959), 1207–1210 (in Russian).
I. M. Sobol’. On the distribution of points in a cube and the approximate evaluation of integrals. Comput. Math. Math. Phys., 7 (1967), 86–112.
I. M. Sobol’, D. Asotsky, A. Kreinin, S. Kucherenko. Construction and Comparison of High-Dimensional Sobol’ Generators. Wilmott, Nov 2012, 64–79.
E. I. Atanassov. On the dyadic diaphony of the Sobol’ sequences. LNCS, 2179 (2001), 133–140.
S. Joe, F. Y. Kuo. Remark on Algorithm 659: Implementing Sobol’s quasirandom sequence generator. ACM Trans. Math. Softw., 29 (2003), 49–57.
S. Joe, F. Y. Kuo. Constructing Sobol sequences with better two-dimensional projections. SIAM J. Sci. Comput., 30, (2008) 2635–2654.
E. Kovaleva (under supervision by C. Lemieux) Genetic Algorithm for searching parameters of Sobol sequence, 2013, https://uwaterloo.ca/computational-mathematics/sites/ca.computational-mathematics/files/uploads/files/kovaleva_project.pdf
I. Sobol’, D. Asotsky, A. Kreinin, S. Kucherenko. Construction and comparison of high-dimensional Sobol generators. Wilmott J., 56 (2011), 64–79.
P. Zinterhof. Uber einige Abschatzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden, Sitzungsber. iisterr. Akad. Wiss. Math.-Naturwiss. Kl. II 185 (1976), 121–132.
P. Zinterhof, H. Stegbuchner. Trigonometrische Approximation mit Gleichverteilungsmethoden, Studia Sci. Math. Hungar., 13, No 3–4 (1978), 273–289.
S. Kucherenko, B. Feil, N. Shah, W. Mauntz. The identification of model effective dimensions using global sensitivity analysis. Reliability Engineering and System Safety, 96 (2011), 440–449.
R. Liu, A. Owen. Estimating mean dimensionality of analysis of variance decompositions. Journal of the American Statistical Association 101, No 474 (2006), 712–721.
