Sparse finite element methods for operator equations with stochastic data

Petersdorff, Tobias von, and Schwab, Christoph. "Sparse finite element methods for operator equations with stochastic data." Applications of Mathematics 51.2 (2006): 145-180. <http://eudml.org/doc/33249>.

@article{Petersdorff2006,
abstract = {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.},
author = {Petersdorff, Tobias von, Schwab, Christoph},
journal = {Applications of Mathematics},
keywords = {wavelet compression of operators; random data; Monte-Carlo method; wavelet finite element method; wavelet compression of operators; random data; Monte-Carlo method; wavelet finite element method; strongly elliptic operator; mean field problem; algorithm; moment; sparse tensor product; Galerkin approximation; multilevel preconditioning},
language = {eng},
number = {2},
pages = {145-180},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Sparse finite element methods for operator equations with stochastic data},
url = {http://eudml.org/doc/33249},
volume = {51},
year = {2006},
}

TY - JOUR
AU - Petersdorff, Tobias von
AU - Schwab, Christoph
TI - Sparse finite element methods for operator equations with stochastic data
JO - Applications of Mathematics
PY - 2006
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 51
IS - 2
SP - 145
EP - 180
AB - 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.
LA - eng
KW - wavelet compression of operators; random data; Monte-Carlo method; wavelet finite element method; wavelet compression of operators; random data; Monte-Carlo method; wavelet finite element method; strongly elliptic operator; mean field problem; algorithm; moment; sparse tensor product; Galerkin approximation; multilevel preconditioning
UR - http://eudml.org/doc/33249
ER -