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

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.