An improved Newton iteration for the generalized inverse of a matrix, with applications. (English) Zbl 0733.65023

Pan, Victor; Schreiber, Robert

SIAM J. Sci. Stat. Comput. 12, No. 5, 1109-1130 (1991).

Under the assumption that one has a parallel computer which is able to perform matrix-multiplications very efficiently, the good old Newton- Schulz iteration may be used to compute the inverse of an \(n\times n\) well-conditioned matrix A. The authors accelerate this method with a Chebyshev and an adaptive acceleration using cubic polynomials rather than the quadratics used in Newton’s method. Furthermore they ensure the stability of the method even when A is singular, they compute the matrix A(\(\epsilon\)) and its pseudoinverse \(A^+(\epsilon)\), the rank of A(\(\epsilon\)) and the orthogonal projection P(\(\epsilon\)) onto the range of A(\(\epsilon\)), where A(\(\epsilon\)) is obtained from A by setting to zero any of its singular values that are less than \(\epsilon\). The results have applications to signal processing and to computing the singular value decomposition (SVD) of a matrix. For some cases as ‘number of processors available \(<O(n^ 2)'\) more modestly parallel, but less costly methods for the SVD as the Kogbetliantz method or the cyclic Golub/Reinsch-method should be more efficient. The algorithms are given in some detail as well as experimental results.

Reviewer: N.Köckler (Paderborn)

MSC:

65F20	Numerical solutions to overdetermined systems, pseudoinverses
65F10	Iterative numerical methods for linear systems
15A09	Theory of matrix inversion and generalized inverses

Keywords:

Moore-Penrose generalized inverse; singular value decomposition; parallel computing; comparison of methods; Chebyshev acceleration; Newton-Schulz iteration; stability; pseudoinverse; signal processing; Kogbetliantz method; Golub/Reinsch-method

Software:

BLAS