595

RWTH Publication No: 956765 2019 
TITLE 
Stability of LowRank Tensor Representations and Structured Multilevel Preconditioning for Elliptic PDEs 
AUTHORS 
Markus Bachmayr, Vladimir Kazeev 
ABSTRACT 
Folding grid value vectors of size 2L into Lth order tensors of mode sizes 2×⋯×2, combined with lowrank representation in the tensor train format, has been shown to lead to highly efficient approximations for various classes of functions. These include solutions of elliptic PDEs on nonsmooth domains or with oscillatory data. This tensorstructured approach is attractive because it leads to highly compressed, adaptive approximations based on simple discretizations. Standard choices of the underlying basis, such as piecewise multilinear finite elements on uniform tensor product grids, entail the wellknown matrix illconditioning of discrete operators. We demonstrate that for lowrank representations, the use of tensor structure itself additionally introduces representation illconditioning, a new effect specific to computations in tensor networks. We analyze the tensor structure of a BPX preconditioner for secondorder linear elliptic operators and construct an explicit tensorstructured 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 illconditioning. By additionally eliminating certain redundancies in the representations of the preconditioned discrete operators, we obtain reducedrank decompositions that are free of both matrix and representation illconditioning. For an iterative solver based on soft thresholding of lowrank tensors, we obtain convergence and complexity estimates and demonstrate its reliability and efficiency for discretizations with up to 250 nodes in each dimension. 
KEYWORDS 
elliptic boundary value problems, multilevel preconditioning, tensor decompo
sitions, representation condition number, solver complexity 
DOI 
10.1007/s1020802009446z 
PUBLICATION 
Found Comput Math 20, 1175–1236 (2020) 