Algorithms for numerical integration in high and infinite dimensions: Analysis, applications and implementation

Abstract

Approximating high and infinite dimensional integrals numerically is in general a very difficult problem. However, it is also one that arises in several applications from statistics, finance and uncertainty quantification, thus motivating a real need for the development and analysis of efficient algorithms. The difficulty lies in the fact that in general high-dimensional problems suffer from the curse of dimensionality where the cost of an approximation rises exponentially with dimension. However, knowing certain properties of the integrands allows one to identify problems that do not suffer from the curse and for which efficient algorithms can be developed.

In this thesis we study numerical integration algorithms, specifically Quasi-Monte Carlo (QMC) quadrature rules and the Multivariate Decomposition Method (MDM), when bounds on the first mixed derivatives are known. The focus in this thesis is on analysis and development of algorithms, a new application for QMC methods from the field of uncertainty quantification and efficient strategies for implementing numerical integration algorithms.

The main results of this thesis are as follows. First, we present a full error analysis for the application of QMC methods to approximate the expectation of the smallest eigenvalue of an elliptic differential operator with coefficients that are parametrised by infinitely-many stochastic variables. Eigenvalue problems are used to model many physical situations in engineering and the natural sciences, and this problem is motivated by uncertainty quantification of such problems. It also represents a new application for QMC methods. Second, we provide explicit details and numerical results on how to efficiently implement the Multivariate Decomposition Method (MDM) for approximating infinite-dimensional integrals. The third contribution of this thesis is a new method of constructing optimal active sets for use in the MDM. Finally, we present two user-friendly Component-by-Component algorithms for constructing QMC lattice rules, which automatically choose good function space weight parameters. In all cases we present numerical results that display the advantages of the algorithms, and where appropriate substantiate our corresponding theoretical results.