A probing method for computing the diagonal of a matrix inverse

Jok M. Tang, Yousef Saad

Research output: Contribution to journalArticle

60 Scopus citations

Abstract

The computation of some entries of a matrix inverse arises in several important applications in practice. This paper presents a probing method for determining the diagonal of the inverse of a sparse matrix in the common situation when its inverse exhibits a decay property, i.e. when many of the entries of the inverse are small. A few simple properties of the inverse suggest a way to determine effective probing vectors based on standard graph theory results. An iterative method is then applied to solve the resulting sequence of linear systems, from which the diagonal of the matrix inverse is extracted. The results of numerical experiments are provided to demonstrate the effectiveness of the probing method.

Original languageEnglish (US)
Pages (from-to)485-501
Number of pages17
JournalNumerical Linear Algebra with Applications
Volume19
Issue number3
DOIs
StatePublished - May 1 2012

Keywords

  • Covariance matrices
  • Graph theory
  • Green's functions
  • Krylov-subspace methods
  • Matrix diagonal extraction
  • Probing
  • Sparse approximate inverses

Fingerprint Dive into the research topics of 'A probing method for computing the diagonal of a matrix inverse'. Together they form a unique fingerprint.

  • Cite this