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

被引:30
作者
Dahmen, Wolfgang [1 ]
DeVore, Ronald [2 ]
Grasedyck, Lars [1 ]
Suli, Endre [3 ]
机构
[1] Rhein Westfal TH Aachen, Inst Geometrie & Prakt Math, Templergraben 55, D-52056 Aachen, Germany
[2] Texas A&M Univ, Dept Math, College Stn, TX 77840 USA
[3] Univ Oxford, Math Inst, Andrew Wiles Bldg,Woodstock Rd, Oxford OX2 6GG, England
基金
美国国家科学基金会;
关键词
High-dimensional elliptic PDEs; Tensor-sparsity models; Regularity theorems; Exponential sums of operators; Dunford integral; Complexity bounds; PRODUCT APPROXIMATION; OPERATORS; RANK;
D O I
10.1007/s10208-015-9265-9
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A recurring theme in attempts to break the curse of dimensionality in the numerical approximation 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 of functions, which can be written as a sum of rank-one tensors using a total of at most 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 of the elliptic PDE can be approximated with a certain rate in the norm of by elements of , then the solution can be approximated in from to accuracy for any . 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 to which 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.
引用
收藏
页码:813 / 874
页数:62
相关论文
共 37 条
[1]  
[Anonymous], 1985, MONOGRAPHS STUDIES M
[2]  
Bachmayr M., 2012, THESIS
[3]   Adaptive Near-Optimal Rank Tensor Approximation for High-Dimensional Operator Equations [J].
Bachmayr, Markus ;
Dahmen, Wolfgang .
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2015, 15 (04) :839-898
[4]   O(N2.7799) COMPLEXITY FOR N BY N APPROXIMATE MATRIX MULTIPLICATION [J].
BINI, D ;
CAPOVANI, M ;
ROMANI, F ;
LOTTI, G .
INFORMATION PROCESSING LETTERS, 1979, 8 (05) :234-235
[5]   Approximation of 1/x by exponential sums in [1, ∞) [J].
Braess, D ;
Hackbusch, W .
IMA JOURNAL OF NUMERICAL ANALYSIS, 2005, 25 (04) :685-697
[6]  
Braess D., 1986, NONLINEAR APPROXIMAT
[7]  
Braess D, 2009, MULTISCALE, NONLINEAR AND ADAPTIVE APPROXIMATION, P39, DOI 10.1007/978-3-642-03413-8_3
[8]  
BREZIS H, 1983, COLLECTION MATH APPL
[9]   ANALYTIC REGULARITY AND POLYNOMIAL APPROXIMATION OF PARAMETRIC AND STOCHASTIC ELLIPTIC PDE'S [J].
Cohen, Albert ;
Devore, Ronald ;
Schwab, Christoph .
ANALYSIS AND APPLICATIONS, 2011, 9 (01) :11-47
[10]   Convergence Rates of Best N-term Galerkin Approximations for a Class of Elliptic sPDEs [J].
Cohen, Albert ;
DeVore, Ronald ;
Schwab, Christoph .
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2010, 10 (06) :615-646