ALTERNATING MINIMAL ENERGY METHODS FOR LINEAR SYSTEMS IN HIGHER DIMENSIONS
ALTERNATING MINIMAL ENERGY METHODS FOR LINEAR SYSTEMS IN HIGHER DIMENSIONS
复制标题
DOI：
10.1137/140953289
复制
发表时间：
2014-01-01
影响因子：
3.1
通讯作者：
Savostyanov, Dmitry V.
中科院分区：
文献类型：
--
作者：
Dolgov, Sergey V.;Savostyanov, Dmitry V.
提出了求解高维对称正定(SPD)线性方程组的算法，给出了该算法的矩阵和右端，并以低秩格式进行求解。类似于密度矩阵重整化群(DMRG)算法，我们的方法随后优化张量积格式的分量。为了提高算法的收敛速度，我们采用不精确的梯度方向来扩展搜索空间。通过对最速下降法的分析，证明了算法的几何收敛性质，并估计了算法的收敛速度。该算法的复杂度在模式的大小和维度上都是线性的，其收敛性能与DMRG算法相当甚至更好。在数值实验中，我们表明所提出的方法对于非SPD系统也是有效的，例如，由描述介观尺度上的基因调控模型的化学主方程产生的系统。
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.