Higher order QMC Galerkin discretization for parametric operator equations

Abstract

We construct quasi-Monte Carlo methods to approximate the expected values of linear functionals of Galerkin discretizations of parametric operator equations which depend on a possibly infinite sequence of parameters. Such problems arise in the numerical solution of differential and integral equations with random field inputs. We analyze the regularity of the solutions with respect to the parameters in terms of the rate of decay of the fluctuations of the input field. If $p\in (0,1]$ denotes the "summability exponent" corresponding to the fluctuations in affine-parametric families of operators, then we prove that deterministic "interlaced polynomial lattice rules" of order $\alpha =\lfloor 1/p\rfloor +1$ in $s$ dimensions with $N$ points can be constructed using a fast component-by-component algorithm, in $\mathcal{O}(\alpha sN\log N+{\alpha }^2{s}^{2}N)$ operations, to achieve a convergence rate of $\mathcal{O}(N^{-1/p})$, with the implied constant independent of $s$. This dimension-independent convergence rate is superior to the rate $\mathcal{O}(N^{-1/p+1/2})$, for $2/3\le p\le 1$ recently established for randomly shifted lattice rules under comparable assumptions. In our analysis we use a non-standard Banach space setting and introduce "smoothness-driven product and order dependent (SPOD)" weights for which we show fast CBC construction.

Equation (3.7) in published version is not correct as stated. This file contains the correct formula

References in corpus (1)

• The decay of the Walsh coefficients of smooth functions

Cited by in corpus (16)

• Parallel cross interpolation for high-precision calculation of high-dimensional integrals
• The construction of good lattice rules and polynomial lattice rules
• Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights
• Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions
• A universal median quasi-Monte Carlo integration
• Optimal order quadrature error bounds for infinite-dimensional higher order digital sequences
• An explicit construction of optimal order quasi-Monte Carlo rules for smooth integrands
• Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration
• Richardson extrapolation of polynomial lattice rules
• Convergence of adaptive stochastic collocation with finite elements
• Scaled lattice rules for integration on ${\mathbb{R}}^d$ achieving higher-order convergence with error analysis in terms of orthogonal projections onto periodic spaces
• MDFEM: Multivariate decomposition finite element method for elliptic PDEs with lognormal diffusion coefficients using higher-order QMC and FEM
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• MDFEM: Multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM
• Richardson extrapolation allows truncation of higher order digital nets and sequences
• Constructing lattice points for numerical integration by a reduced fast successive coordinate search algorithm