Stability of Low-Rank Tensor Representations and Structured Multilevel Preconditioning for Elliptic PDEs
Open Access
- 23 January 2020
- journal article
- research article
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 20 (5) , 1175-1236
Abstract
Folding grid value vectors of size $$2^L$$ into Lth-order tensors of mode size $$2\times \cdots \times 2$$ , combined with low-rank representation in the tensor train format, has been shown to result in highly efficient approximations for various classes of functions. These include solutions of elliptic PDEs on nonsmooth domains or with oscillatory data. This tensor-structured approach is attractive because it leads to highly compressed, adaptive approximations based on simple discretizations. Standard choices of the underlying bases, such as piecewise multilinear finite elements on uniform tensor product grids, entail the well-known matrix ill-conditioning of discrete operators. We demonstrate that, for low-rank representations, the use of tensor structure itself additionally introduces representation ill-conditioning, a new effect specific to computations in tensor networks. We analyze the tensor structure of a BPX preconditioner for a second-order linear elliptic operator and construct an explicit tensor-structured representation of the preconditioner, with ranks independent of the number L of discretization levels. The straightforward application of the preconditioner yields discrete operators whose matrix conditioning is uniform with respect to the discretization parameter, but in decompositions that suffer from representation ill-conditioning. By additionally eliminating certain redundancies in the representations of the preconditioned discrete operators, we obtain reduced-rank decompositions that are free of both matrix and representation ill-conditioning. For an iterative solver based on soft thresholding of low-rank tensors, we obtain convergence and complexity estimates and demonstrate its reliability and efficiency for discretizations with up to $$2^{50}$$ nodes in each dimension.
Keywords
All Related Versions
Funding Information
- Johannes Gutenberg-Universität Mainz
This publication has 50 references indexed in Scilit:
- Iterative Methods Based on Soft Thresholding of Hierarchical TensorsFoundations of Computational Mathematics, 2016
- Tensor Networks and Hierarchical Tensors for the Solution of High-Dimensional Partial Differential EquationsFoundations of Computational Mathematics, 2016
- Adaptive Low-Rank Methods: Problems on Sobolev SpacesSIAM Journal on Numerical Analysis, 2016
- Multilevel preconditioning and low‐rank tensor iteration for space–time simultaneous discretizations of parabolic PDEsNumerical Linear Algebra with Applications, 2014
- Adaptive Near-Optimal Rank Tensor Approximation for High-Dimensional Operator EquationsFoundations of Computational Mathematics, 2014
- A projection method to solve linear systems in tensor formatNumerical Linear Algebra with Applications, 2012
- A basic norm equivalence for the theory of multilevel methodsNumerische Mathematik, 1993
- Parallel multilevel preconditionersMathematics of Computation, 1990
- The $h{\text{ - }}p$ Version of the Finite Element Method for Domains with Curved BoundariesSIAM Journal on Numerical Analysis, 1988
- Regularity of the Solution of Elliptic Problems with Piecewise Analytic Data. Part I. Boundary Value Problems for Linear Elliptic Equation of Second OrderSIAM Journal on Mathematical Analysis, 1988