Bidiagonalization and symmetric tridiagonalization by systolic arrays

Abstract

A systolic algorithm and an array for bidiagonalization of an nxn matrix in O(nlog(2)n) time, using O(n to the 2nd power) cells are given. Bandedness of the input matrix may be effectively exploited. If the matrix is banded, with p nonzero subdiagonals and q nonzero superdiagonals, then 4nln(p + q) + O(n) clocks and 2n(p + q) + O((p + q) to the 2nd power + n) cells are needed. This is faster than the best previously reported result by the factor log(2)e = 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.