Fast triangularization of a symmetric tridiagonal matrix

A simple linear systolic array is presented for triangularizing a symmetric tridiagonal matrix by Gaussian Elimination using nearest neighbor pivoting. The array consists of three cells requiring an area bounded by four simple inner product cells. The design can compute the elimination in time 2_n + k₁ for the simple point case and using an implicit 2*2 block structuring of data produces an almost eliminated form in time n + k₂. The implicit result can be fully eliminated by only a constant number of extra operations independent of the matrix order (n), where k, and k2 are constants.