Fast Sparse Selected Inversion
Fast Sparse Selected Inversion
复制标题
快速稀疏选择反演
DOI：
--
复制
发表时间：
2015
影响因子：
1.5
通讯作者：
V. Balakrishnan
中科院分区：
文献类型：
--
作者：
J. Xia;Yuanzhe Xi;S. Cauley;V. Balakrishnan
提出了一种利用多波前法和秩结构快速提取稀疏对称矩阵A逆矩阵对角块的结构化选择求逆方法。当$A$由某些偏微分方程的离散化产生并且具有低秩性质（因子分解中的中间稠密矩阵具有小的非对角数值秩）时，可以快速计算$A^{-1}$的对角块和某些非对角块（需要找到$A^{-1}$的对角块）的结构化近似。一个结构化的多锋LDL分解首先计算$A$与一个组装树的前向遍历，这产生了一个序列的本地数据稀疏的因素。这些因子用于结构化反演的树的向后遍历。反演中的中间操作以分层半可分离或低秩形式执行。在数据稀疏性假设和适当的秩条件下，理论结构反演方法可以有效地提高反演精度。
We propose a fast structured selected inversion method for extracting the diagonal blocks of the inverse of a sparse symmetric matrix $A$, using the multifrontal method and rank structures. When $A$ arises from the discretization of some PDEs and has a low-rank property (the intermediate dense matrices in the factorization have small off-diagonal numerical ranks), structured approximations of the diagonal blocks and certain off-diagonal blocks of $A^{-1}$ (that are needed to find the diagonal blocks of $A^{-1}$) can be quickly computed. A structured multifrontal LDL factorization is first computed for $A$ with a forward traversal of an assembly tree, which yields a sequence of local data-sparse factors. The factors are used in a backward traversal of the tree for the structured inversion. The intermediate operations in the inversion are performed in hierarchically semiseparable or low-rank forms. With the assumptions of data sparsity and appropriate rank conditions, the theoretical structured inversion co...