A parallel algorithm for computing the group inverse via Perron complementation

Abstract

A parallel algorithm is presented for computing the group inverse of a singular
M–matrix of the form A = I − T, where T ∈ R^n×n is irreducible and stochastic. The algorithm
is constructed in the spirit of Meyer’s Perron complementation approach to computing the Perron
vector of an irreducible nonnegative matrix. The asymptotic number of multiplication operations
that is necessary to implement the algorithm is analyzed, which shows that the algorithm saves a
significant amount of computation over the direct computation of the group inverse of A.