DMRG Approach to Fast Linear Algebra in the TT-Format

By Ivan V. Oseledets. 2011

77 citations recorded by the source corpus.

Abstract In this paper, the concept of the DMRG minimization scheme is extended to several important operations in the TT-format, like the matrix-by-vector product and the conversion from the canonical format to the TT-format. Fast algorithms are implemented and a stabilization scheme based on randomization is proposed. The comparison with the direct method is performed on a sequence of matrices and vectors coming as approximate solutions of linear systems in the TT-format. A generated example is provided to show that randomization is really needed in some cases. The matrices and vectors used are available from the author or at http://spring.inm.ras.ru/osel

Subfields: Applied Mathematics, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

1. E. E. Tyrtyshnikov
2. Vladimir A. Kazeev
3. Boris N. Khoromskij
4. Sergey V. Dolgov
5. Ivan V. Oseledets
6. Dmitry V. Savostyanov

In Computational Theory and Mathematics

1. Sergey V. Dolgov
2. Boris N. Khoromskij
3. Vladimir A. Kazeev
4. Ivan V. Oseledets
5. Dmitry V. Savostyanov
6. E. E. Tyrtyshnikov
7. Christine Tobler
8. Venera Khoromskaia

In Computer Networks and Communications

1. Boris N. Khoromskij
2. Vladimir A. Kazeev
3. E. E. Tyrtyshnikov
4. Sergey V. Dolgov

Citations in the corpus

• A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Later on, the ideas of DMRG have been picked up and extended to other applications in the numerical analysis community in a series of papers [65,124,127,160,171,206].”
• Two-level Tucker-TT-QTT format for optimized tensor calculus (2012, background): “Sometimes, several technical tricks have to be added [42, 51], which are reasonable in certain cases.”
• Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions (2013, unknown): “For ALS there is also a lack of convergence estimates both in the classical papers [16, 4], and in the recent ones, where ALS was applied to the Tucker model [5, 33], tensor trains [29], hierarchical Tucker format [25] and high–dimensional interpolation [34].”
• Multilevel Toeplitz Matrices Generated by Tensor-Structured Vectors and Convolution with Logarithmic Complexity (2013, methodology): “The DMRG algorithm for matrix-vector multiplication is presented in [42].”
• Tensors-structured Numerical Methods in Scientific Computing: Survey on Recent Advances (2012, methodology): “The DMRG approach to fast linear algebra in the TT-format was addressed in [75].”