Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions

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 comp...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on scientific computing 2014-01, Vol.36 (5), p.A2248-A2271
Main Authors: Dolgov, Sergey V., Savostyanov, Dmitry V.
Format: Article
Language:English
Subjects:
Algorithms
Convergence
Density
Format
Linear systems
Mathematical analysis
Mathematical models
Production methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1064-8275
1095-7197
DOI:10.1137/140953289