AN IMPROVED NEWTON ITERATION FOR THE GENERALIZED INVERSE OF A MATRIX, WITH APPLICATIONS
AN IMPROVED NEWTON ITERATION FOR THE GENERALIZED INVERSE OF A MATRIX, WITH APPLICATIONS
复制标题
DOI：
10.1137/0912058
复制
发表时间：
1991-09-01
期刊：
影响因子：
--
通讯作者：
SCHREIBER, R
中科院分区：
文献类型：
--
作者：
PAN, V;SCHREIBER, R
潘和赖夫已经表明，牛顿迭代可以用来计算逆的n × n，良好的条件矩阵在并行时间O（log 2 n），这种计算是处理器效率。 由于该算法实质上是一系列矩阵-矩阵乘法，因此可以在脉动阵列和并行计算机上高效地实现。牛顿法在算术运算量方面是昂贵的。 本文用几种新的加速方法来降低牛顿法的计算量。 对于任意输入矩阵，加速比为2;对于对称正定矩阵，加速比为4。 文中还指出，加速过程是切比雪夫加速的一种形式，而牛顿方法则是用Neumann级数近似的.此外，对于一些重要的相关问题，本文还发展了类牛顿过程. 它还示出了如何计算最近的矩阵较低的秩到一个给定的矩阵A，广义逆这些附近的矩阵，它们的秩（作为一个函数的距离从A），和投影到子空间跨越奇异向量，这样的计算是很重要的信号处理应用。 此外，它表明，牛顿法的数值不稳定性时，适用于一个奇异矩阵，从这些改进的方法。 最后，使用这些工具来设计新的多对数时间并行算法的奇异值分解进行了探索。
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.