400 | IGPM400.pdf July 2014 |

TITLE | Tensor-Sparsity of Solutions to High-Dimensional Elliptic Partial Differential Equations |

AUTHORS | Wolfgang Dahmen, Ronald Devore, Lars Grasedyck, Endre Süli |

ABSTRACT | A recurring theme in attempts to break the curse of dimensionality in the numerical approximations of solutions to high-dimensional partial differential equations (PDEs) is to employ some form of sparse tensor approximation. Unfortunately, there are only a few results that quantify the possible advantages of such an approach. This paper introduces a class Σn of functions, which can be written as a sum of rank-one tensors using a total of at most n parameters and then uses this notion of sparsity to prove a regularity theorem for certain high-dimensional elliptic PDEs. It is shown, among other results, that whenever the right-hand side f of the elliptic PDE can be approximated with a certain rate O(n-r) in the norm of H -1 by elements of Σn, then the solution u can be approximated in H1 from Σn to accuracy O(n-r ') for any r ' ∈ (0; r). Since these results require knowledge of the eigenbasis of the elliptic operator considered, we propose a second "basis-free" model of tensor sparsity and prove a regularity theorem for this second sparsity model as well. We then proceed to address the important question of the extent such regularity theorems translate into results on computational complexity. It is shown how this second model can be used to derive computational algorithms with performance that breaks the curse of dimensionality on certain model high-dimensional elliptic PDEs with tensor-sparse data. |

KEYWORDS | high-dimensional elliptic PDEs, tensor sparsity models, regularity theorems, exponential sums of operators, Dunford integrals, complexity bounds |

DOI | 10.1007/s10208-015-9265-9 |

PUBLICATION | Foundation of Computational Mathematics 2015, pp 1-62 |