×

A parallel algorithm for computing the group inverse via Perron complementation. (English) Zbl 1093.65041

A parallel algorithm is given for computing the group inverse of a singular M-matrix of the form \(A=I-T\), where \(T\) is irreducible and stochastic. Numerical evidence is presented that shows that the proposed algorithm is more efficient compared with the direct computation of the inverse. It is pointed out that, for the set of examples tested, the savings in the number of floating point operations are roughly 50% for matrices of size ranging from \(n=50\) to \(n=1600\). An asymptotic analysis is given that shows that the proposed algorithm saves approximately 12.5% of multiplication operations if it is implemented in a purely serial fashion.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
15B51 Stochastic matrices
15A09 Theory of matrix inversion and generalized inverses
65Y05 Parallel numerical computation