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.
Reviewer: R. P. Tewarson (Stony Brook)
MSC:
65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
15B51 | Stochastic matrices |
15A09 | Theory of matrix inversion and generalized inverses |
65Y05 | Parallel numerical computation |