Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint
10/2013

Alternating minimal energy methods for linear systems in higher dimensions. Part I: SPD systems

Sergey Dolgov and Dmitry Savostyanov

Abstract

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.

Received:
Jan 25, 2013
Published:
Feb 5, 2013
MSC Codes:
15A69, 33F05, 65F10
Keywords:
high-dimensional problems, tensor train format, ALS, DMRG, steepest descent, convergence rate, superfast algorithms

Related publications

Preprint
2013 Repository Open Access
Sergey Dolgov and Dmitry V. Savostyanov

Alternating minimal energy methods for linear systems in higher dimensions. Pt. 1 : SPD systems