Fast sparse selected inversion

Jianlin Xia, Yuanzhe Xi, Stephen Cauley, Venkataramanan Balakrishnan

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

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 cost is proportional to the matrix size n times a low-degree polylogarithmic function of n after structured factorizations. The memory counts are similar. In comparison, existing direct selected inversion methods cost O(n3/2) flops in two dimensions and O(n2) flops in three dimensions for both the factorization and the inversion, with O(n4/3) memory in three dimensions. Additional formulas for efficient structured operations are also derived. Numerical tests on two- and three-dimensional discretized PDEs and more general sparse matrices are done to demonstrate the performance.

Original languageEnglish (US)
Pages (from-to)1283-1314
Number of pages32
JournalSIAM Journal on Matrix Analysis and Applications
Volume36
Issue number3
DOIs
StatePublished - 2015

Keywords

  • Data sparsity
  • Fast selected inversion
  • HSS matrix
  • Linear complexity
  • Low-rank property
  • Structured multifrontal method

Fingerprint Dive into the research topics of 'Fast sparse selected inversion'. Together they form a unique fingerprint.

Cite this