Toeplitz Monte Carlo
Tóm tắt
Motivated mainly by applications to partial differential equations with random coefficients, we introduce a new class of Monte Carlo estimators, called Toeplitz Monte Carlo (TMC) estimator, for approximating the integral of a multivariate function with respect to the direct product of an identical univariate probability measure. The TMC estimator generates a sequence
$$x_1,x_2,\ldots $$
of i.i.d. samples for one random variable and then uses
$$(x_{n+s-1},x_{n+s-2}\ldots ,x_n)$$
with
$$n=1,2,\ldots $$
as quadrature points, where s denotes the dimension. Although consecutive points have some dependency, the concatenation of all quadrature nodes is represented by a Toeplitz matrix, which allows for a fast matrix–vector multiplication. In this paper, we study the variance of the TMC estimator and its dependence on the dimension s. Numerical experiments confirm the considerable efficiency improvement over the standard Monte Carlo estimator for applications to partial differential equations with random coefficients, particularly when the dimension s is large.
Tài liệu tham khảo
Cliffe, K.A., Giles, M.B., Scheichl, R., Teckentrup, A.L.: Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Comput. Vis. Sci. 14, 3–15 (2011)
Devroye, L.: Non-uniform Random Variate Generation. Springer, New York (1986)
Dick, J., Kuo, F.Y., Le Gia, Q.T., Schwab, C.: Fast QMC matrix-vector multiplication. SIAM J. Sci. Comput. 37, A1436–A1450 (2015)
Dick, J., Kuo, F.Y., Le Gia, Q.T., Schwab, C.: Multilevel higher order QMC Petrov–Galerkin discretization for affine parametric operator equations. SIAM J. Numer. Anal. 54, 2541–2568 (2016)
Feischl, M., Kuo, F.Y., Sloan, I.H.: Fast random field generation with \(H\)-matrices. Numer. Math. 140, 639–676 (2018)
Frigo, M., Johnson, S.G.: The design and implementation of FFTW3. Proc. IEEE 93, 216–231 (2005)
Giles, M.B.: Multilevel Monte Carlo path simulation. Oper. Res. 56, 607–617 (2008)
Giles, M.B., Kuo, F.Y., Sloan, I.H., Waterhouse, B.J.: Quasi-Monte Carlo for finance applications. ANZIAM J. 50, C308–C323 (2008)
Hoeffding, W.: A class of statistics with asymptotically normal distribution. Ann. Math. Stat. 19, 293–325 (1948)
Kuo, F.Y., Sloan, I.H., Wasilkowski, G., Woźniakowski, H.: On decompositions of multivariate functions. Math. Comp. 79, 953–966 (2010)
Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems. Volume II: Standard Information for Functionals. EMS Tracts in Mathematics, vol. 12. European Mathematical Society, Zürich (2010)
Owen, A.B.: Monte Carlo theory, methods and examples. http://statweb.stanford.edu/~owen/mc/ (2019). Accessed 4 Mar 2020
Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)
Sloan, I.H., Woźniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals? J. Complex. 14, 1–33 (1998)
Sobol’, I.M.: Sensitivity estimates for nonlinear mathematical models. Math. Mod. Comp. Exp. 1, 407–414 (1993)
Teckentrup, A.L., Scheichl, R., Giles, M.B., Ullmann, E.: Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients. Numer. Math. 125, 569–600 (2013)