Premium
Finding off‐diagonal entries of the inverse of a large symmetric sparse matrix
Author(s) -
Eastwood Shawn,
Wan Justin W. L.
Publication year - 2013
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.1826
Subject(s) - diagonal , inverse , mathematics , diagonal matrix , node (physics) , matrix (chemical analysis) , combinatorics , vertex (graph theory) , algorithm , block matrix , band matrix , square matrix , symmetric matrix , eigenvalues and eigenvectors , geometry , graph , materials science , physics , structural engineering , quantum mechanics , engineering , composite material
SUMMARY The method fast inverse using nested dissection (FIND) was proposed to calculate the diagonal entries of the inverse of a large sparse symmetric matrix. In this paper, we show how the FIND algorithm can be generalized to calculate off‐diagonal entries of the inverse that correspond to ‘short’ geometric distances within the computational mesh of the original matrix. The idea is to extend the downward pass in FIND that eliminates all nodes outside of each node cluster. In our advanced downwards pass, it eliminates all nodes outside of each ‘node cluster pair’ from a subset of all node cluster pairs. The complexity depends on how far ( i , j ) is from the main diagonal. In the extension of the algorithm, all entries of the inverse that correspond to vertex pairs that are geometrically closer than a predefined length limit l will be calculated. More precisely, let α be the total number of nodes in a two‐dimensional square mesh. We will show that our algorithm can compute O ( α 3 ∕ 2 + 2 ε ) entries of the inverse in O ( α 3 ∕ 2 + 2 ε ) time where l = O ( α 1 ∕ 4 + ε ) and 0 ≤ ε ≤ 1 ∕ 4. Numerical examples are given to illustrate the efficiency of the proposed method. Copyright © 2012 John Wiley & Sons, Ltd.