WZ分解的一种新的并行算法

本文对n阶非奇异实稠密矩阵A的WZ分解提出了一种新的并行算法。用n~2台处理机,我们可以在3n-2步内求得矩阵A的WZ分解。该算法与文献1]中的方法相结合,可得并行求解线性方程组的另一种有效算法。文中所提及的算法均适用于SIMD型并行计算机。

A New Parallel Algorithm with WZ Factorization

The parallel solution for linear algebraic equations Ax = b, where the coefficient matrix A is a non-singular matrix of order n, is an attractive problem. Usually, the direct parallel solution used is based on the LU factorization of matrix A. Soon after Prof. D. Evans et al. proposed in 1979 a novel approach to the factorization of coefficient matrix A, the Quadrant Interlocking Factorization(QIF), another useful direct parallel method for solving linear equations, a modified QIF method or WZ factorization, was further suggested. However, the algorithm for the modified method is of low efficiency. A new parallel algorithm developed by the author for the WZ factorization of non-singular real dense matrix A is proposed. A series of matrices are constructed recursively with no division operation used. Then with the elements of these matrices, the WZ factorization of the matrix A will be found by a parallel division. If n2 processors are available, the time steps to conplete the WZ factorization of the matrix A would be 3n - 2. The modified QIF method is therefore improved. The proposed algorithms are suitable for use on a parallel computer of SIMD type.