Alternating minimal energy methods for linear systems in higher dimensions

Sergey V. Dolgov, Dmitry V. Savostyanov

Research output: Contribution to journalArticlepeer-review

130 Citations (SciVal)
110 Downloads (Pure)


We propose algorithms for the solution of high-dimensional symmetrical positive definite (SPD) linear systems with the matrix and the right-hand side given and the solution sought in a low-rank format. Similarly to density matrix renormalization group (DMRG) algorithms, our methods optimize the components of the tensor product format subsequently. To improve the convergence, we expand the search space by an inexact gradient direction. We prove the geometrical convergence and estimate the convergence rate of the proposed methods utilizing the analysis of the steepest descent algorithm. The complexity of the presented algorithms is linear in the mode size and dimension, and the demonstrated convergence is comparable to or even better than the one of the DMRG algorithm. In the numerical experiment we show that the proposed methods are also efficient for non-SPD systems, for example, those arising from the chemical master equation describing the gene regulatory model at the mesoscopic scale.

Original languageEnglish
Pages (from-to)A2248-A2271
Number of pages24
JournalSIAM Journal on Scientific Computing
Issue number5
Early online date25 Sept 2014
Publication statusPublished - 31 Dec 2014


  • Alternating linear scheme
  • Chemical master equation
  • Density matrix renormalization group
  • High-dimensional problems
  • Poisson equation
  • Steepest descent
  • Tensor train format

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Alternating minimal energy methods for linear systems in higher dimensions'. Together they form a unique fingerprint.

Cite this