Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions

Sergey Dolgov, Dmitry Savostyanov

Research output: Contribution to journalArticlepeer-review

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
DOIs
Publication statusPublished - 25 Sept 2014

Bibliographical note

© 2014 Society for Industrial and Applied Mathematics

Keywords

  • high-dimensional problems
  • tensor train format
  • alternating linear scheme
  • density matrix renormalization group
  • steepest descent
  • Poisson equation
  • chemical master equation

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