稠密方阵求逆及线性方程组求解的无回代心动算法

Systolic Algorithms for Dense Matrix Inversion and Solving Linear Systems Without Back Substitution

本文给出线性方程组求解、方阵求逆的三种无回代心动算法,与文献中的算法相比,不但处理单元统一、数据流动更有规则性,而且具有更小的时空复杂度。对于n阶线性方程组的求解,阵列中有n(n+3)/2个处理单元,需3n—1个单位时间.对于n阶非奇异稠密方阵的求逆,处理时间为4n-2个单位时间;使用Gauss-Jordan消去法时,需n(n+1)个处理单元,使用邻主元素法及Givens旋转法时,需要n(3n+1)/2个处理单元。

Systolic algorithms are given for dense matrix inversion and solution of linear systems without back substitution. Compared with the ones presented in the references listed, the present ones have the merits of uniform processors, regular data movements and lower time-space complexity. For solving linear system with n unknowns, n(n+3)/ 2 processors and 3n-1 time units are needed. For nx n dense matrix inversion, the algorithm needs 4n-2 time units and n(n+l) processors when Gauss-Jordan elimination is used or n(3n+l)/2 processors when Givens rotation used.