Generalised matrix inversion and rank computation by successive matrix powering

Chen, Lujuan ; Krishnamurthy, E. V. ; Macleod, Iain (1994) Generalised matrix inversion and rank computation by successive matrix powering Parallel Computing, 20 (3). pp. 297-311. ISSN 0167-8191

Full text not available from this repository.

Official URL: http://linkinghub.elsevier.com/retrieve/pii/S01678...

Related URL: http://dx.doi.org/10.1016/S0167-8191(06)80014-1

Abstract

Computation of the generalised inverse A+ and rank of an arbitrary (including singular and rectangular) matrix A has many applications. This paper derives an iterative scheme to approximate the generalised 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 generalised inverse of A can be computed in parallel time ranging from O(log n) to O(log2 n), similar to previous methods. The rank of matrix A is obtained along with the generalised inverse. The successive matrix squaring algorithm is generalised to higher-order schemes, where the composite matrix is repeatedly raised to an integer power l>2. This form of expression leads to a simplified notation compared with that of earlier methods, and helps to clarify the relationship between l, the order of the iterative scheme and K, the number of iterations. In particular, the accuracy achieved in approximating A+ is a function only of the magnitude of lK and does not depend on the particular values chosen for l and K; we argue that there is no obvious advantage in choosing l other than 2. Our derived error bound for the approximation to A+ is tighter than that previously established. The same bound applies to the rank. Numerical experiments with different test matrices (square, rectangular, complex, singular, etc.) illustrate the method. They further demonstrate that our tighter error bound provides a useful guide to the number of iterations required. In the examples given, the specified accuracy was achieved after the calculated number of iterations, but no earlier. Implementation studies on a general-purpose parallel machine (CM-5) demonstrated a smaller than expected penalty for direct squaring of matrix T in comparison with multiplication of its component block matrices. For special-purpose VLSI architectures, the simple structure of the matrix squaring algorithm leads to a straightforward parallel implementation with low communication overheads.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Complexity; Data-parallel Computation; Generalised Inverse; Moore-penrose Inverse; Parallelism; Rank Computation; Repeated Squaring; Systolic Architectures
ID Code:28173
Deposited On:14 Dec 2010 08:14
Last Modified:04 Jun 2011 06:58

Repository Staff Only: item control page