Performance and stability of direct methods for computing generalized inverses of the graph Laplacian (Q2208933): Difference between revisions

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.