Alternating minimal energy methods for linear systems in higher dimensions. Part I: SPD systems
This work provides a new algorithmic framework for efficiently solving high-dimensional SPD linear systems, which is important for computational science and engineering applications involving tensor-structured data.
The paper introduces rank-adaptive alternating minimal energy methods for solving high-dimensional linear systems in the tensor train format, achieving convergence comparable to DMRG-type algorithms with linear complexity in mode size and dimension.
We introduce a family of numerical algorithms for the solution of linear system in higher dimensions with the matrix and right hand side given and the solution sought in the tensor train format. The proposed methods are rank--adaptive and follow the alternating directions framework, but in contrast to ALS methods, in each iteration a tensor subspace is enlarged by a set of vectors chosen similarly to the steepest descent algorithm. The convergence is analyzed in the presence of approximation errors and the geometrical convergence rate is estimated and related to the one of the steepest descent. The complexity of the presented algorithms is linear in the mode size and dimension and the convergence demonstrated in the numerical experiments is comparable to the one of the DMRG--type algorithm.