Adaptive low-rank methods for problems on Sobolev spaces with error control in $L_2$

Bachmayr, M.¹ ; Dahmen, W.² 

¹ Sorbonne Universités, UPMC Université Paris 06, CNRS, UMR 7598, Laboratoire Jacques-Louis Lions, 4 place Jussieu, 75005, Paris, France.
² Institut für Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, 52056 Aachen, Germany.

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 50 (2016) no. 4, pp. 1107-1136.

Résumé

Low-rank tensor methods for the approximate solution of second-order elliptic partial differential equations in high dimensions have recently attracted significant attention. A critical issue is to rigorously bound the error of such approximations, not with respect to a fixed finite dimensional discrete background problem, but with respect to the exact solution of the continuous problem. While the energy norm offers a natural error measure corresponding to the underlying operator considered as an isomorphism from the energy space onto its dual, this norm requires a careful treatment in its interplay with the tensor structure of the problem. In this paper we build on our previous work on energy norm-convergent subspace-based tensor schemes contriving, however, a modified formulation which now enforces convergence only in $L_2$. In order to still be able to exploit the mapping properties of elliptic operators, a crucial ingredient of our approach is the development and analysis of a suitable asymmetric preconditioning scheme. We provide estimates for the computational complexity of the resulting method in terms of the solution error and study the practical performance of the scheme in numerical experiments. In both regards, we find that controlling solution errors in this weaker norm leads to substantial simplifications and to a reduction of the actual numerical work required for a certain error tolerance.

Détail

Reçu le : 2014-12-12
Accepté le : 2015-09-10
DOI : 10.1051/m2an/2015071

Classification : 41A46, 41A63, 65D99, 65J10, 65N12, 65N15
Keywords: low-rank tensor approximation, adaptive methods, high-dimensional elliptic problems, preconditioning, computational complexity

Bibliographie

R. Andreev and C. Tobler, Multilevel preconditioning and low rank tensor iteration for space-time simultaneous discretizations of parabolic PDEs. Numer. Linear Algebra Appl. 22 (2015) 317–337. | Zbl | MR | DOI

M. Bachmayr, Adaptive Low-Rank Wavelet Methods and Applications to Two-Electron Schrödinger Equations. Ph.D. thesis, RWTH Aachen (2012).

M. Bachmayr and W. Dahmen, Adaptive low-rank methods: Problems on Sobolev spaces. Preprint arXiv:1407.4919 [math.NA] (2014). | MR

M. Bachmayr and W. Dahmen, Adaptive near-optimal rank tensor approximation for high-dimensional operator equations. Found. Comput. Math. 15 (2015) 839–898. | Zbl | MR | DOI

J. Ballani and L. Grasedyck, A projection method to solve linear systems in tensor format. Numer. Linear Algebra Appl. 20 (2013) 27–43. | Zbl | MR | DOI

G. Beylkin and L. Monzón, Approximation by exponential sums revisited. Appl. Comput. Harmon. Anal. 28 (2010) 131–149. | Zbl | MR | DOI

M. Billaud-Friess, A. Nouy and O. Zahm, A tensor approximation method based on ideal minimal residual formulations for the solution of high-dimensional problems. ESAIM: M2AN 48 (2014) 1777–1806. | Zbl | MR | mathdoc-id | DOI

S.C. Brenner and L.R. Scott, The Mathematical Theory of Finite Element Methods. 3rd edition. Vol. 15 of Texts Appl. Math. Springer (2008) | Zbl | MR

A. Cohen, W. Dahmen and R. Devore, Adaptive wavelet methods for elliptic operator equations: Convergence rates. Math. Comput. 70 (2001) 27–75. | Zbl | MR | DOI

W. Dahmen, Stability of multiscale transformations. J. Fourier Anal. Appl. 2 (1996) 341–361. | Zbl | MR

W. Dahmen, R. DeVore, L. Grasedyck and E. Süli, Tensor-sparsity of solutions to high-dimensional elliptic partial differential equations. Found. Comput. Math. (2015) DOI: . | DOI | MR

T.J. Dijkema, C. Schwab and R. Stevenson, An adaptive wavelet method for solving high-dimensional elliptic PDEs. Constr. Approx. 30 (2009) 423–455. | Zbl | MR | DOI

S.V. Dolgov and D.V. Savostyanov, Alternating minimal energy methods for linear systems in higher dimensions. SIAM J. Sci. Comput. 36 (2014) A2248–A2271. | Zbl | MR | DOI

G.C. Donovan, J.S. Geronimo and D.P. Hardin, Orthogonal polynomials and the construction of piecewise polynomial smooth wavelets. SIAM J. Math. Anal. 30 (1999) 1029–1056. | Zbl | MR | DOI

L. Grasedyck, Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure. Computing 72 (2004) 247–265. | Zbl | MR | DOI

L. Grasedyck, Hierarchical singular value decomposition of tensors. SIAM J. Matrix Anal. Appl. 31 (2010) 2029–2054. | Zbl | MR | DOI

L. Grasedyck, D. Kressner and C. Tobler. A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen 36 (2013) 53–78. | Zbl | MR | DOI

W. Hackbusch, Entwicklungen nach Exponentialsummen. Technical Report 4, MPI Leipzig (2005).

W. Hackbusch, Tensor Spaces and Numerical Tensor Calculus. Vol. 42 of Springer Series Comput. Math. Springer-Verlag Berlin Heidelberg (2012). | Zbl | MR

W. Hackbusch and B.N. Khoromskij, Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. Part I. Separable approximation of multi-variate functions. Computing 76 (2006) 177–202. | Zbl | MR | DOI

W. Hackbusch and S. Kühn, A new scheme for the tensor representation. J. Fourier Anal. Appl. 15 (2009) 706–722. | Zbl | MR | DOI

B.N. Khoromskij, Tensor-structured preconditioners and approximate inverse of elliptic operators in $R^d$. Constr. Approx. 30 (2009) 599–620. | Zbl | MR | DOI

B.N. Khoromskij, $O\left(dlogN\right)$-quantics approximation of $N$-d tensors in high-dimensional numerical modeling. Constr. Approx. 34 (2011) 257–280. | Zbl | MR | DOI

D. Kressner and C. Tobler. Preconditioned low-rank methods for high-dimensional elliptic PDE eigenvalue problems. Comput. Methods Appl. Math. 11 (2011) 363–381. | Zbl | MR | DOI

D. Kressner and A. Uschmajew, On low-rank approximability of solutions to high-dimensional operator equations and eigenvalue problems. Preprint arXiv:1406.7026 [math.NA] (2014). | MR

D. Kressner, M. Steinlechner and A. Uschmajew, Low-rank tensor methods with subspace correction for symmetric eigenvalue problems. SIAM J. Sci. Comput. 36 (2014) A2346–A2368. | Zbl | MR | DOI

I.V. Oseledets, Tensor-train decomposition. SIAM J. Sci. Comput. 33 (2011) 2295–2317. | Zbl | MR | DOI

I. Oseledets and E. Tyrtyshnikov, Breaking the curse of dimensionality, or how to use SVD in many dimensions. SIAM J. Scientific Comput. 31 (2009) 3744–3759. | Zbl | MR | DOI

F. Stenger, Numerical Methods Based on Sinc and Analytic Functions. Vol. 20 of Springer Series Comput. Math. Springer-Verlag (1993). | Zbl | MR

L.R. Tucker, Some mathematical notes on three-mode factor analysis. Psychometrika 31 (1966) 279–311. | MR | DOI