A systolic algorithm for solving dense linear systems (Q679296)

This paper presents a systolic algorithm to solve the dense linear equations of type \(Ax=b\) where \(A\) is an arbitrary \(n\times n\) matrix and \(b\) is an \(n\times 1\) column vector. An important consideration is that an existing pivot row can be replaced by a new privot row during the execution of the elementary row operation on \(A\). The computational model used to solve \(Ax=b\) is a two-dimensional systolic array which consists of \(n\) linear systolic arrays. For \(1\leq i\leq n\), the \(i\)th linear array is responsible to eliminate the \(i\)th unknown variable \(x_i\) of \(x\). This algorithm requires \(4n\) time steps to solve the linear system. The design process and correctness proof are analysed in detail.