Bidiagonalization and symmetric tridiagonalization by systolic arrays

We give a systolic algorithm and array for bidiagonalization of ann × n matrix inO(n logn) time, usingO(n2) cells. Bandedness of the input matrix may be effectively exploited. If the matrix is banded, withp nonzero subdiagonals andq nonzero superdiagonals, then 4n ln(p+q)+O(n) clocks and 2n(p+q)+O((p+q)2+n) cells are needed. This is faster than the best previously reported result by the factor log2e=1.44.... Moreover, in contrast to earlier systolic designs, which require the matrix to be preloaded into the array and the result matrix extracted after bidiagonalization, the present arrays are pipelined.