Previous |  Up |  Next


Title: Sparse finite element methods for operator equations with stochastic data (English)
Author: von Petersdorff, Tobias
Author: Schwab, Christoph
Language: English
Journal: Applications of Mathematics
ISSN: 0862-7940 (print)
ISSN: 1572-9109 (online)
Volume: 51
Issue: 2
Year: 2006
Pages: 145-180
Summary lang: English
Category: math
Summary: Let $A\: V\rightarrow V^{\prime }$ be a strongly elliptic operator on a $d$-dimensional manifold $D$ (polyhedra or boundaries of polyhedra are also allowed). An operator equation $Au=f$ with stochastic data $f$ is considered. The goal of the computation is the mean field and higher moments $\mathcal M^1 u\in V$, $\mathcal M^2u\in V\otimes V$, $\ldots $, $\mathcal M^k u \in V\otimes \cdots \otimes V$ of the solution. We discretize the mean field problem using a FEM with hierarchical basis and $N$ degrees of freedom. We present a Monte-Carlo algorithm and a deterministic algorithm for the approximation of the moment $\mathcal M^k u$ for $k\ge 1$. The key tool in both algorithms is a “sparse tensor product” space for the approximation of $\mathcal M^k u$ with $O(N (\log N)^{k-1})$ degrees of freedom, instead of $N^k$ degrees of freedom for the full tensor product FEM space. A sparse Monte-Carlo FEM with $M$ samples (i.e., deterministic solver) is proved to yield approximations to ${\mathcal M}^k u$ with a work of $O(M N(\log N)^{k-1})$ operations. The solutions are shown to converge with the optimal rates with respect to the Finite Element degrees of freedom $N$ and the number $M$ of samples. The deterministic FEM is based on deterministic equations for ${\mathcal M}^k u$ in $D^k\subset \mathbb{R}^{kd}$. Their Galerkin approximation using sparse tensor products of the FE spaces in $D$ allows approximation of ${\mathcal M}^k u$ with $O(N(\log N)^{k-1})$ degrees of freedom converging at an optimal rate (up to logs). For nonlocal operators wavelet compression of the operators is used. The linear systems are solved iteratively with multilevel preconditioning. This yields an approximation for $\mathcal M^k u$ with at most $O(N (\log N)^{k+1})$ operations. (English)
Keyword: wavelet compression of operators
Keyword: random data
Keyword: Monte-Carlo method
Keyword: wavelet finite element method
MSC: 60H15
MSC: 65C05
MSC: 65F10
MSC: 65N30
idZBL: Zbl 1164.65300
idMR: MR2212311
DOI: 10.1007/s10492-006-0010-1
Date available: 2009-09-22T18:25:23Z
Last updated: 2020-07-02
Stable URL:
Reference: [1] I. Babuška: On randomized solution of Laplace’s equation.Čas. Pěst. Mat. 86 (1961), 269–276.
Reference: [2] I.  Babuška: Error-bounds for finite element method.Numer. Math. 16 (1971), 322–333. MR 0288971, 10.1007/BF02165003
Reference: [3] I.  Babuška, R.  Tempone, and G.  Zouraris: Galerkin finite element approximations of stochastic elliptic partial differential equations.SIAM J. Numer. Anal. 42 (2004), 800–825. MR 2084236, 10.1137/S0036142902418680
Reference: [4] V. I.  Bogachev: Gaussian Measures. AMS Mathematical Surveys and Monographs Vol.  62.AMS, Providence, 1998. MR 1642391
Reference: [5] L.  Breiman: Probability.Addison-Wesley, Reading, 1968. Zbl 0174.48801, MR 0229267
Reference: [6] W. A.  Light, E. W.  Cheney: Approximation Theory in Tensor Product Spaces. Lecture Notes in Mathematics Vol. 1169.Springer-Verlag, Berlin, 1985. MR 0817984, 10.1007/BFb0075392
Reference: [7] P. G.  Ciarlet: The Finite Element Method for Elliptic Problems.Elsevier Publ. North Holland, Amsterdam, 1978. Zbl 0383.65058, MR 0520174
Reference: [8] M.  Dahmen, H. Harbrecht, and R.  Schneider: Compression techniques for boundary integral equations—optimal complexity estimates.SIAM J. Numer. Anal. 43 (2006), 2251–2271. MR 2206435, 10.1137/S0036142903428852
Reference: [9] W.  Dahmen, R.  Stevenson: Element-by-element construction of wavelets satisfying stability and moment conditions.SIAM J.  Numer. Anal. 37 (1999), 319–352. MR 1742747, 10.1137/S0036142997330949
Reference: [10] S. C.  Eisenstat, H. C.  Elman, M. H.  Schultz: Variational iterative methods for nonsymmetric systems of linear equations.SIAM J.  Numer. Anal. 20 (1983), 345–357. MR 0694523, 10.1137/0720023
Reference: [11] M.  Griebel, P.  Oswald, T.  Schiekofer: Sparse grids for boundary integral equations.Numer. Math. 83 (1999), 279–312. MR 1712687, 10.1007/s002110050450
Reference: [12] S. Hildebrandt, N. Wienholtz: Constructive proofs of representation theorems in separable Hilbert space.Commun. Pure Appl. Math. 17 (1964), 369–373. MR 0166608, 10.1002/cpa.3160170309
Reference: [13] G. C.  Hsiao, W. L.  Wendland: A finite element method for some integral equations of the first kind.J.  Math. Anal. Appl. 58 (1977), 449–481. MR 0461963, 10.1016/0022-247X(77)90186-X
Reference: [14] S.  Janson: Gaussian Hilbert Spaces.Cambridge University Press, Cambridge, 1997. Zbl 0887.60009, MR 1474726
Reference: [15] S.  Larsen: Numerical analysis of elliptic partial differential equations with stochastic input data.Doctoral Dissertation, Univ. of Maryland, 1985.
Reference: [16] M.  Ledoux, M.  Talagrand: Probability in Banach Spaces. Isoperimetry and Processes.Springer-Verlag, Berlin, 1991. MR 1102015
Reference: [17] P.  Malliavin: Stochastic Analysis.Springer-Verlag, Berlin, 1997. Zbl 0878.60001, MR 1450093
Reference: [18] W. McLean: Strongly Elliptic Systems and Boundary Integral Equations.Cambridge University Press, Cambridge, 2000. Zbl 0948.35001, MR 1742312
Reference: [19] J. C.  Nédélec, J. P.  Planchard: Une méthode variationelle d’éléments finis pour la résolution numérique d’un problème extérieur dans $\mathbb{R}^3$.RAIRO Anal. Numér. 7 (1973), 105–129. MR 0424022
Reference: [20] G. Schmidlin, C. Lage, and C. Schwab: Rapid solution of first kind boundary integral equations in $\mathbb{R}^3$.Eng. Anal. Bound. Elem. 27 (2003), 469–490. 10.1016/S0955-7997(02)00156-X
Reference: [21] T. von Petersdorff, C. Schwab: Wavelet approximations for first kind boundary integral equations in polygons.Numer. Math. 74 (1996), 479–516. MR 1414419, 10.1007/s002110050226
Reference: [22] T. von Petersdorff, C. Schwab: Numerical solution of parabolic equations in high dimensions.M2AN, Math. Model. Numer. Anal. 38 (2004), 93–127. MR 2073932, 10.1051/m2an:2004005
Reference: [23] R. Schneider: Multiskalen- und Wavelet-Matrixkompression. Advances in Numerical Mathematics.Teubner, Stuttgart, 1998. MR 1623209
Reference: [24] C. Schwab, R. A.  Todor: Sparse finite elements for elliptic problems with stochastic loading.Numer. Math. 95 (2003), 707–734. MR 2013125, 10.1007/s00211-003-0455-z
Reference: [25] C. Schwab, R. A.  Todor: Sparse finite elements for stochastic elliptic problems—higher order moments.Computing 71 (2003), 43–63. MR 2009650, 10.1007/s00607-003-0024-4
Reference: [26] S. A.  Smolyak: Quadrature and interpolation formulas for tensor products of certain classes of functions.Sov. Math. Dokl. 4 (1963), 240–243. Zbl 0202.39901
Reference: [27] V. N.  Temlyakov: Approximation of Periodic Functions.Nova Science Publ., New York, 1994. MR 1373654
Reference: [28] G. W.  Wasilkowski, H. Wozniakowski: Explicit cost bounds of algorithms for multivariate tensor product problems.J.  Complexity 11 (1995), 1–56. MR 1319049, 10.1006/jcom.1995.1001
Reference: [29] N.  Wiener: The homogeneous Chaos.Amer. J.  Math. 60 (1938), 987–936. Zbl 0019.35406, MR 1507356, 10.2307/2371268


Files Size Format View
AplMat_51-2006-2_4.pdf 524.3Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo