Successive matrix squaring algorithm for parallel computing the weighted generalized inverse AMN+

摘要

We derive a successive matrix squaring (SMS) algorithm to approximate the weighted generalized inverse, which can be expressed in the form of successive squaring of a composite matrix T. Given an m by n matrix A with m≈n, we show that the weighted generalized inverse of A can be computed in parallel time ranging from O(log n) to O(log2 n) provided that there are enough processors to support matrix multiplication in time O(log n).