Premium
On computing the inverse of a sparse matrix
Author(s) -
Niessner H.,
Reichert K.
Publication year - 1983
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.1620191009
Subject(s) - diagonal , inverse , inversion (geology) , diagonally dominant matrix , main diagonal , band matrix , sparse matrix , algorithm , diagonal matrix , mathematics , gaussian elimination , matrix (chemical analysis) , block matrix , computer science , symmetric matrix , square matrix , pure mathematics , geometry , gaussian , eigenvalues and eigenvectors , physics , invertible matrix , materials science , composite material , paleontology , structural basin , quantum mechanics , biology
Abstract The Gauss‐Jordan inversion algorithm requires 0( n 3 ) arithmetic operations. In some practical applications, like state estimation or short‐circuit calculation in power systems, the given matrix is sparse and only part of the inverse is needed. Most frequently in the diagonal dominant case this is the diagonal. There are two ways to exploit sparsity to determine elements of the inverse: 1 Columnwise inversion via the solution of sparse linear systems with columns of the unit matrix as right‐hand sides. 2 Application of the algorithm of Takahashi et al 6 . The latter algorithm arises very naturally from multiplying the left‐ and right‐hand factors of the Zollenkopf bifactorization in reverse order. We indicate how computing time can be gained in the important symmetric diagonal dominant case if only part of the diagonal is needed and compare computing times of the method of Takahasi et al. 6 with several variants of columnwise inversion. Whereas most of the theory holds for general matrices, experiments are performed on the symmetric diagonal dominant case. For band matrices the operation count is 0( n ) both for computing a column of the inverse by columnwise inversion and the diagonal by the algorithm of Takahashi et al 6 .