Alternating minimal energy methods for linear systems in higher dimensions.

22 October 2013
Dmitry Savostyanov

We propose a new algorithm for the approximate solution of large-scale high-dimensional tensor-structured linear systems. It can be applied to high-dimensional differential equations, which allow a low-parametric approximation of the multilevel matrix, right-hand side and solution in a tensor product format. We apply standard one-site tensor optimisation algorithm (ALS), but expand the tensor manifolds using the classical iterative schemes (e.g. steepest descent).  We obtain the rank--adaptive algorithm with the theoretical convergence estimate not worse than the one of the steepest descent, and fast practical convergence, comparable or even better than the convergence of more expensive two-site optimisation algorithm (DMRG).
The method is successfully applied for a high--dimensional problem of quantum chemistry, namely the NMR simulation of a large peptide.

This is a joint work with S.Dolgov (Max-Planck Institute, Leipzig, Germany), supported by RFBR and EPSRC grants.

Keywords: high--dimensional problems, tensor train format, ALS, DMRG, steepest descent, convergence rate, superfast algorithms, NMR.

  • Numerical Analysis Group Internal Seminar