×

Cubature formulas for multisymmetric functions and applications to stochastic partial differential equations. (English) Zbl 1398.65014

Summary: The numerical solution of stochastic partial differential equations and numerical Bayesian estimation is computationally demanding. If the coefficients in a stochastic partial differential equation exhibit symmetries, they can be exploited to reduce the computational effort. To do so, we show that permutation-invariant functions can be approximated by permutation-invariant polynomials in the space of continuous functions as well as in the space of \(p\)-integrable functions defined on \([0,1]^s\) for \(1\leqslant p<\infty\). We proceed to develop a numerical strategy to compute cubature formulas that exploit permutation-invariance properties related to multisymmetry groups in order to reduce computational work. We show that in a certain sense there is no curse of dimensionality if we restrict ourselves to multisymmetric functions, and we provide error bounds for formulas of this type. Finally, we present numerical results, comparing the proposed formulas to other integration techniques that are frequently applied to high-dimensional problems such as quasi-Monte Carlo rules and sparse grids.

MSC:

65C05 Monte Carlo methods
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
54C35 Function spaces in general topology
58J70 Invariance and symmetry properties for PDEs on manifolds
65D30 Numerical integration
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] T. Bagby, L. Bos, and N. Levenberg, {\it Multivariate simultaneous approximation}, Constr. Approx., 18 (2002), pp. 569-577, . · Zbl 1025.41002
[2] I. Bogaert, {\it Iteration-free computation of Gauss-Legendre quadrature nodes and weights}, SIAM J. Sci. Comput., 36 (2014), pp. A1008-A1026, . · Zbl 1297.65025
[3] P. Bratley and B. L. Fox, {\it Algorithm 659: Implementing Sobol’s quasirandom sequence generator}, ACM Trans. Math. Software, 14 (1988), pp. 88-100. · Zbl 0642.65003
[4] E. Briand, {\it Polynômes Multisymétriques}, thesis, Université Rennes, Rennes, France, 2002, .
[5] R. Cools, {\it An encyclopaedia of cubature formulas}, J. Complexity, 19 (2003), pp. 445-453. · Zbl 1061.41020
[6] P. J. Davis and P. Rabinowitz, {\it Methods of Numerical Integration}, Dover, Mineola, NY, corrected 2nd ed., 2007. · Zbl 1139.65016
[7] E. A. Devuyst and P. V. Preckel, {\it Gaussian cubature: a practitioner’s guide}, Math. Comput. Model., 45 (2007), pp. 787-794, . · Zbl 1133.65002
[8] J. Dick, {\it Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order}, SIAM J. Numer. Anal., 46 (2008), pp. 1519-1553, . · Zbl 1189.42012
[9] J. Dick, F. Y. Kuo, and I. H. Sloan, {\it High-dimensional integration: The quasi-Monte Carlo way}, Acta Numer., 22 (2013), pp. 133-288, . · Zbl 1296.65004
[10] C. Geiersbach, C. Heitzinger, G. Pammer, S. Rigger, and G. Tulzer, {\it A 2D Finite Element Method Solver for Drift-Diffusion-Poisson Systems and Semilinear Poisson Equations}, (2016).
[11] A. Genz, {\it A package for testing multiple integration subroutines}, in Numerical Integration, Dordrecht, the Netherlands, 1987, pp. 337-340.
[12] T. Gerstner and M. Griebel, {\it Dimension-adaptive tensor-product quadrature}, Computing, 71 (2003), pp. 65-87. · Zbl 1030.65015
[13] A. Hinrichs, E. Novak, M. Ullrich, and H. Woźniakowski, {\it The curse of dimensionality for numerical integration of smooth functions}, Math. Comput., 83 (2014), pp. 2853-2863, . · Zbl 1345.65014
[14] A. Hinrichs, E. Novak, M. Ullrich, and H. Woźniakowski, {\it Product rules are optimal for numerical integration in classical smoothness spaces}, J. Complexity, 38 (2017), pp. 39-49. · Zbl 1354.65043
[15] S. Joe and F. Y. Kuo, {\it Remark on algorithm 659: Implementing Sobol’s quasirandom sequence generator}, ACM Trans. Math. Software, 29 (2003), pp. 49-57. · Zbl 1070.65501
[16] D. Nuyens, G. Suryanarayana, and M. Weimar, {\it Rank-\(1\) lattice rules for multivariate integration in spaces of permutation-invariant functions. Error bounds and tractability}, Adv. Comput. Math., 42 (2016), pp. 55-84, . · Zbl 1334.65064
[17] D. Nuyens, G. Suryanarayana, and M. Weimar, {\it Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions}, Constr. Approx., 45 (2017), pp. 311-344, . · Zbl 1375.65001
[18] A. B. Owen, {\it Latin supercube sampling for very high-dimensional simulations}, ACM Trans. Model. Comput. Simul., 8 (1998), pp. 71-102, . · Zbl 0917.65022
[19] G. Pammer and S. Rigger, {\it Multisymmetry}, (2017).
[20] D. Rydh, {\it A minimal set of generators for the ring of multisymmetric functions}, Ann. Inst. Fourier (Grenoble), 57 (2007), pp. 1741-1769, . · Zbl 1130.13005
[21] L. Schläfli, {\it Gesammelte Mathematische Abhandlungen}, Springer Basel, 1953, pp. 9-112. · Zbl 0051.24102
[22] R. Schürer, {\it A comparison between (quasi-)Monte Carlo and cubature rule based methods for solving high-dimensional integration problems}, Math. Comput. Simul., 62 (2003), pp. 509-517. · Zbl 1025.65008
[23] A. Stroud, {\it Approximate calculation of multiple integrals}. Prentice-Hall Ser. Automat. Comput., Prentice-Hall, Englewood Cliffs, NJ, 1971. · Zbl 0379.65013
[24] F. Vaccarino, {\it The ring of multisymmetric functions}, Ann. Inst. Fourier (Grenoble), 55 (2005), pp. 717-731, . · Zbl 1062.05143
[25] M. Weimar, {\it The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces}, J. Approx. Theory, 164 (2012), pp. 1345-1368, . · Zbl 1262.41025
[26] M. Weimar, {\it On lower bounds for integration of multivariate permutation-invariant functions}, J. Complexity, 30 (2014), pp. 87-97, . · Zbl 1297.65024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.