NDLI: Fast QMC Matrix-Vector Multiplication

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kuo, Frances Y. Dick, Josef Schwab, Christoph Le Gia, Quoc T.
Copyright Year	2015
Abstract	Quasi--Monte Carlo (QMC) rules $1/N \sum_{n=0}^{N-1} f(\boldsymbol{y}_n A)$ can be used to approximate integrals of the form $\int_{[0,1]^s} f(\boldsymbol{y} A) \,\mathrm{d} \boldsymbol{y}$, where $A$ is a matrix and $\boldsymbol{y}$ is a row vector. This type of integral arises, for example, from the simulation of a normal distribution with a general covariance matrix, from the approximation of the expectation value of solutions of PDEs with random coefficients, or from applications from statistics. In this paper we design QMC quadrature points $\boldsymbol{y}_0, \ldots, \boldsymbol{y}_{N-1} \in [0,1]^s$ such that for the matrix $Y = (\boldsymbol{y}_{0}^\top, \ldots, \boldsymbol{y}_{N-1}^\top)^\top$ whose rows are the quadrature points, one can use the fast Fourier transform to compute the matrix-vector product $Y \boldsymbol{a}^\top$, $\boldsymbol{a} \in \mathbb{R}^s$, in $\mathcal{O}(N \log N)$ operations and at most $2(s-1)$ extra additions. The proposed method can be applied to lattice rules, polynomial lattice rules, and a certain type of Korobov $p$-set and even works if the point set $\boldsymbol{y}_0, \ldots, \boldsymbol{y}_{N-1}$ is transformed to another domain $U \subseteq \mathbb{R}^s$ by a coordinatewise mapping $\phi$ which is the same in each coordinate. The approach is illustrated computationally by three numerical experiments. The first test considers the generation of points with normal distribution and a general covariance matrix, the second test applies QMC to high-dimensional, affine-parametric, elliptic PDEs with uniformly distributed random coefficients, and the third test addresses finite element discretizations of elliptic PDEs with high-dimensional, log-normal random input data. All numerical tests show a significant speedup of the computation times of the fast QMC matrix method compared to a conventional implementation as the dimension becomes large.
Starting Page	A1436
Ending Page	A1450
Page Count	15
File Format	PDF
ISSN	10648275
DOI	10.1137/151005518
e-ISSN	10957197
Issue Number	3
Volume Number	37
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2015-06-02
Access Restriction	Subscribed
Subject Keyword	Monte Carlo methods polynomial lattice rule quasi--Monte Carlo PDEs with random input high-dimensional integration Korobov $p$-set fast Fourier transform lattice rule
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in