AN IMPROVED NEWTON ITERATION FOR THE GENERALIZED INVERSE OF A MATRIX, WITH APPLICATIONS

被引:108
作者
PAN, V
SCHREIBER, R
机构
[1] RES INST ADV COMP SCI,MOFFETT FIELD,CA 94035
[2] CUNY HERBERT H LEHMAN COLL,DEPT MATH,BRONX,NY 10468
来源
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING | 1991年 / 12卷 / 05期
关键词
MATRIX COMPUTATION; MOORE-PENROSE GENERALIZED INVERSE; SINGULAR VALUE DECOMPOSITION; NEWTON ITERATION; PARALLEL COMPUTING;
D O I
10.1137/0912058
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Pan and Reif have shown that Newton iteration may be used to compute the inverse of an n x n, well-conditioned matrix in parallel time O(log2 n) and that this computation is processor efficient. Since the algorithm essentially amounts to a sequence of matrix-matrix multiplications, it can be implemented with great efficiency on systolic arrays and parallel computers. Newton's method is expensive in terms of the arithmetic operation count. In this paper the cost of Newton's method is reduced with several new acceleration procedures. A speedup by a factor of two is obtained for arbitrary input matrices; for symmetric positive definite matrices, the factor is four. It is also shown that the accelerated procedure is a form of Tchebychev acceleration, whereas Newton's method uses a Neumann series approximation. In addition, Newton-like procedures are developed for a number of important related problems. It is also shown how to compute the nearest matrices of lower rank to a given matrix A, the generalized inverses of these nearby matrices, their ranks (as a function of their distances from A), and projections onto subspaces spanned by singular vectors; such computations are important in signal processing applications. Furthermore, it is demonstrated that the numerical instability of Newton's method when applied to a singular matrix is absent from these improved methods. Finally, the use of these tools to devise new polylog time parallel algorithms for the singular value decomposition is explored.
引用
收藏
页码:1109 / 1130
页数:22
相关论文
共 17 条
[1]  
Ben-Israel A., 1966, SIAM J NUMER ANAL, V3, P410, DOI DOI 10.1137/0703035
[2]   A NOTE ON AN ITERATIVE METHOD FOR GENERALIZED INVERSION OF MATRICES [J].
BENISRAEL, A .
MATHEMATICS OF COMPUTATION, 1966, 20 (95) :439-+
[3]  
BRENT RP, 1985, J VLSI COMPUT SYST, V1, P242
[4]  
DONGARRA J, 1988, ANLMCSP881
[5]  
FADDEEV DK, 1963, COMPUTATIONAL METHOD
[6]  
Golub G.H., 1996, MATH GAZ, VThird
[7]  
Hillis WD, 1985, CONNECTION MACHINE
[8]   FAST AND EFFICIENT PARALLEL SOLUTION OF DENSE LINEAR-SYSTEMS [J].
PAN, V ;
REIF, J .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1989, 17 (11) :1481-1491
[9]  
PAN V, 1988, 888 STAT U NEW YORK
[10]  
PAN V, 1988, 8828 STAT U NEW YORK