Constructing lattice points for numerical integration by a reduced fast successive coordinate search algorithm

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:351

Article

Ebert, Adrian¹  Kritzer, Peter² 

[1] Katholieke Univ Leuven, Dept Comp Sci, Celestijnenlaan 200A, B-3001 Leuven, Belgium

[2] Austrian Acad Sci, Johann Radon Inst Computat & Appl Math RICAM, Altenbergerstr 69, A-4040 Linz, Austria

关键词: Numerical integration;    Lattice points;    Polynomial lattice points;    Quasi-Monte Carlo methods;    Weighted function spaces;    Component-by-component construction;   

DOI  :  10.1016/j.cam.2018.10.046

来源: Elsevier

【 摘 要 】

In this paper, we study an efficient algorithm for constructing node sets of high-quality quasi-Monte Carlo integration rules for weighted Korobov, Walsh, and Sobolev spaces. The algorithm presented is a reduced fast successive coordinate search (SCS) algorithm, which is adapted to situations where the weights in the function space show a sufficiently fast decay. The new SCS algorithm is designed to work for the construction of lattice points, and, in a modified version, for polynomial lattice points, and the corresponding integration rules can be used to treat functions in different kinds of function spaces. We show that the integration rules constructed by our algorithms satisfy error bounds of optimal convergence order. Furthermore, we give details on efficient implementation such that we obtain a considerable speed-up of previously known SCS algorithms. This improvement is illustrated by numerical results. The speed-up obtained by our results may be of particular interest in the context of QMC for PDEs with random coefficients, where both the dimension and the required number of points are usually very large. Furthermore, our main theorems yield previously unknown generalizations of earlier results. (C) 2018 Elsevier B.V. All rights reserved.

【 授权许可】

Free