Solution of linear systems and matrix inversion in the TT-format

Sergey Dolgov and Ivan V. Oseledets

Contact the author: Please use for correspondence this email.
Submission date: 27. Apr. 2011 (revised version: May 2011)
Pages: 25
published in: SIAM journal on scientific computing, 34 (2012) 5, p. A2718-A2739 
DOI number (of the published article): 10.1137/110833142
Bibtex
MSC-Numbers: 65F30, 65F50, 65N35, 65F10
Keywords and phrases: TT-format, solution of linear systems, high-dimensional problems, DMRG
Download full preprint: PDF (562 kB)

Abstract:
Tensors arise naturally in high-dimensional problems in chemistry, financial mathematics and many others. The numerical treatment of such kind of problems is difficult due to the curse of dimensionality: the number of unknowns and computational complexity grows exponentially with the dimension of the problem. To break the curse of dimensionality, low-parametric representations, or formats have to be used. In this paper we make use of the TT-format which is one of the most effective stable representations of high-dimensional tensors. Basic linear algebra operations in the TT-format are now well-developed. Our goal is to provide a ``black-box''-type solver for linear systems where both the matrix and the right-hand side are in the TT-format. An efficient DMRG (Density Matrix Renormalization Group) method is proposed, and several tricks are employed to make it work. The numerical experiments confirm the effectiveness of our approach.