Performance and stability of direct methods for computing generalized inverses of the graph Laplacian (Q2208933)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Performance and stability of direct methods for computing generalized inverses of the graph Laplacian |
scientific article |
Statements
Performance and stability of direct methods for computing generalized inverses of the graph Laplacian (English)
0 references
28 October 2020
0 references
The authors present and study two direct algorithms for computing particular generalized inverses of graph Laplacians: the group inverse and the absorption inverse. The group generalized inverse of a square matrix \(A\) is the unique \(A^\sharp\) such that \(AA^\sharp A=A\), \(A^\sharp AA^\sharp=A^\sharp\) and \(AA^\sharp=A^\sharp A\), while absorption inverse further generalizes group inverse for graphs with absorption. The authors first improve the direct method they previously developed in [Linear Algebra Appl. 574, 123--158 (2019; Zbl 1433.65065)], and show that this improvement is forward stable with high relative component-wise accuracy. The second proposed algorithm is based on bottleneck matrices, which represents inverses of the principal \((n-1)\times(n-1)\)-minors of the Laplacian, with lower numerical stability than the first method. Experimental results show that both methods presented here provide faster algorithms for handling dense problems.
0 references
Laplacian matrix
0 references
group inverse
0 references
absorption inverse
0 references
Gauss-Jordan method
0 references
forward stability
0 references