Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions

By Sergey V. Dolgov, Dmitry V. Savostyanov. 2013

100 citations recorded by the source corpus.

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.

Subfields: Computational Mathematics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

1. V. Dolgov
2. Dmitry V. Savostyanov
3. Boris N. Khoromskij
4. Ivan V. Oseledets
5. E. E. Tyrtyshnikov
6. Sergey V. Dolgov
7. Vladimir A. Kazeev
8. Christine Tobler

In Computational Theory and Mathematics

1. V. Dolgov
2. Dmitry V. Savostyanov
3. Ivan V. Oseledets
4. Boris N. Khoromskij
5. E. E. Tyrtyshnikov
6. Sergey V. Dolgov
7. Christine Tobler
8. Venera Khoromskaia

In Numerical Analysis

1. V. Dolgov
2. Dmitry V. Savostyanov

Citations in the corpus

• A literature survey of low‐rank tensor approximation techniques (2013, neutral): “The combination of ALS with the TT decomposition has been considered in [66–68, 125].”
• Low-rank solvers for unsteady Stokes–Brinkman optimal control problem with random data (2016, unknown): “The DMRG algorithm with a single center site [55] uses the surrogate of the Krylov vector, and the Alternating Minimal Energy (AMEn) method [13] uses the actual residual, which was later adopted for eigenvalue problems as well [23, 28].”
• ALTERNATING MINIMAL ENERGY METHODS FOR LINEAR SYSTEMS IN HIGHER DIMENSIONS∗ (2014, methodology): “We have recently proposed the AMEn algorithm for linear systems [3, 4], that also injects the gradient direction in the optimisation step, but in a way that allows to prove the global convergence of the resulted scheme.”
• Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions (2016, unknown): “hich takes all possible combinations of values of indices, i1,i2,. . .,iN, for in = 1,2,. . ., In, n = 1,2,. . ., N and in a specific order. Multi–indices can be defined using two different conventions [90]: 1.Little-endian convention (reverse lexicographic ordering) i1i2 iN = i1 +(i2 1)I1 +(i3 1)I1I2”