×

zbMATH — the first resource for mathematics

Sparse finite element methods for operator equations with stochastic data. (English) Zbl 1164.65300
Summary: Let \(A\: V\to V'\) 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 finite element method (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\geq 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.

MSC:
65C05 Monte Carlo methods
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
60H25 Random operators and equations (aspects of stochastic analysis)
60H15 Stochastic partial differential equations (aspects of stochastic analysis)
65C30 Numerical solutions to stochastic differential and integral equations
65T60 Numerical methods for wavelets
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
PDF BibTeX Cite
Full Text: DOI EuDML
References:
[1] I. Babuška: On randomized solution of Laplace’s equation. Čas. Pěst. Mat. 86 (1961), 269–276. · Zbl 0116.10503
[2] I. Babuška: Error-bounds for finite element method. Numer. Math. 16 (1971), 322–333. · Zbl 0214.42001
[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. · Zbl 1080.65003
[4] V. I. Bogachev: Gaussian Measures. AMS Mathematical Surveys and Monographs Vol. 62. AMS, Providence, 1998.
[5] L. Breiman: Probability. Addison-Wesley, Reading, 1968.
[6] W. A. Light, E.W. Cheney: Approximation Theory in Tensor Product Spaces. Lecture Notes in Mathematics Vol. 1169. Springer-Verlag, Berlin, 1985. · Zbl 0575.41001
[7] P. G. Ciarlet: The Finite Element Method for Elliptic Problems. Elsevier Publ. North Holland, Amsterdam, 1978.
[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. · Zbl 1113.65114
[9] W. Dahmen, R. Stevenson: Element-by-element construction of wavelets satisfying stability and moment conditions. SIAM J. Numer. Anal. 37 (1999), 319–352. · Zbl 0942.65130
[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. · Zbl 0524.65019
[11] M. Griebel, P. Oswald, T. Schiekofer: Sparse grids for boundary integral equations. Numer. Math. 83 (1999), 279–312. · Zbl 0935.65131
[12] S. Hildebrandt, N. Wienholtz: Constructive proofs of representation theorems in separable Hilbert space. Commun. Pure Appl. Math. 17 (1964), 369–373. · Zbl 0131.13401
[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. · Zbl 0352.45016
[14] S. Janson: Gaussian Hilbert Spaces. Cambridge University Press, Cambridge, 1997. · Zbl 0887.60009
[15] S. Larsen: Numerical analysis of elliptic partial differential equations with stochastic input data. Doctoral Dissertation. Univ. of Maryland, 1985.
[16] M. Ledoux, M. Talagrand: Probability in Banach Spaces. Isoperimetry and Processes. Springer-Verlag, Berlin, 1991. · Zbl 0748.60004
[17] P. Malliavin: Stochastic Analysis. Springer-Verlag, Berlin, 1997. · Zbl 0878.60001
[18] W. McLean: Strongly Elliptic Systems and Boundary Integral Equations. Cambridge University Press, Cambridge, 2000. · Zbl 0948.35001
[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.
[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. · Zbl 1038.65129
[21] T. von Petersdorff, C. Schwab: Wavelet approximations for first kind boundary integral equations in polygons. Numer. Math. 74 (1996), 479–516. · Zbl 0863.65074
[22] T. von Petersdorff, C. Schwab: Numerical solution of parabolic equations in high dimensions. M2AN, Math. Model. Numer. Anal. 38 (2004), 93–127. · Zbl 1083.65095
[23] R. Schneider: Multiskalen-und Wavelet-Matrixkompression. Advances in Numerical Mathematics. Teubner, Stuttgart, 1998.
[24] C. Schwab, R. A. Todor: Sparse finite elements for elliptic problems with stochastic loading. Numer. Math. 95 (2003), 707–734. · Zbl 1044.65085
[25] C. Schwab, R. A. Todor: Sparse finite elements for stochastic elliptic problems–higher order moments. Computing 71 (2003), 43–63. · Zbl 1044.65006
[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
[27] V. N. Temlyakov: Approximation of Periodic Functions. Nova Science Publ., New York, 1994.
[28] G.W. Wasilkowski, H. Wozniakowski: Explicit cost bounds of algorithms for multivariate tensor product problems. J. Complexity 11 (1995), 1–56. · Zbl 0819.65082
[29] N. Wiener: The homogeneous Chaos. Amer. J. Math. 60 (1938), 987–936. · JFM 64.0887.02
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.