Alternating minimal energy methods for linear systems in higher dimensions

Sergey V. Dolgov, Dmitry V. Savostyanov

Research output: Contribution to journalArticlepeer-review

82 Citations (Scopus)
60 Downloads (Pure)

Abstract

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
Volume36
Issue number5
Early online date25 Sep 2014
DOIs
Publication statusPublished - 31 Dec 2014

Keywords

  • 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

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

Cite this