Volume 53, pp. 439-458, 2020.

Performance and stability of direct methods for computing generalized inverses of the graph Laplacian

Michele Benzi, Paraskevi Fika, and Marilena Mitrouli

Abstract

We consider the computation of generalized inverses of the graph Laplacian for both undirected and directed graphs, with a focus on the group inverse and the closely related absorption inverse. These generalized inverses encode valuable information about the underlying graph as well as the regular Markov process generated by the graph Laplacian. In [Benzi et al., Linear Algebra Appl., 574 (2019), pp. 123–152], both direct and iterative numerical methods have been developed for the efficient computation of the absorption inverse and related quantities. In this work, we present two direct algorithms for the computation of the group inverse and the absorption inverse. The first is based on the Gauss-Jordan elimination and the reduced row echelon form of the Laplacian matrix and the second on the bottleneck matrix, the inverse of a submatrix of the Laplacian matrix. These algorithms can be faster than the direct algorithms proposed in [Benzi et al., Linear Algebra Appl., 574 (2019), pp. 123–152].

Full Text (PDF) [933 KB], BibTeX

Key words

Laplacian matrix, group inverse, absorption inverse, Gauss-Jordan method

AMS subject classifications

15A09, 05C50, 65F50

< Back