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

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.


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


Full Text: DOI Link