Finding off-diagonal entries of the inverse of a large symmetric sparse matrix

摘要

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.