Systolic architecture for matrix triangularisation with partial pivoting

A systolic array for triangularisation of dense matrices, using Gaussian elimination with partial pivoting, is presented. The adopted algorithm is a slightly modified version of the traditional partial-pivoting algorithm. The modification is aimed at eliminating the need for global communications, without jeopardising the numerical stability of the algorithm. The array triangularises an n*n dense matrix in O(n²) time without any need for costly inter-iteration I/O. The processing elements (PEs) are very simple and all data communications are strictly local. It is shown that an extended array (with n extra PEs) can solve a dense system of equations in O(n²) time. It is also shown that the same array can be modified to implement a scaled column-pivoting strategy.