Multi-phase Systolic Algorithms for Spectral Decomposition

Abstract

In this paper, we propose two multi-phase systolic algorithms to solve the spectral decomposition problem based on the QR algorithm. The spectral decomposition is one of the most computationally intensive modern signal processing operations. While the QR algorithm is well known to be an effective method to solve the eigenvalue problem, there is still no single systolic array architecture that can compute the unitary Q matrix readily and perform the QR algorithm efficiently. Previous methods using the QR algorithm had communication problems among different architectures. In this paper, two arrays, a triangular and a rectangular, are presented to implement the multi-phase algorithms. Details on these multi-phase operations of the QR algorithm as well as architectural consequences and performance evaluation are discussed in the paper. Efficient fault-tolerant schemes for these multi-phase operations are also considered.