Systolic computation of QZ matrix decomposition

Abstract

Four new triangular systolic arrays for QZ matrix decomposition based on the block Givens and Householder transformations are described. Their performance is compared with the traditional point rotator and point reflector for the QR matrix decomposition. The comparison is based on the detailed discussion of the length of global time step Δ t which synchronizes the array, the number of required processors and the area defined by the vertical and horizontal links used in the array for the data pipelining. It turns out that the most efficient array for the QZ matrix decomposition is the one which implements the block Givens rotation with an encoder and decoder in the diagonal and nondiagonal processors, respectively. This array is almost perfectly balanced as opposed to the well known triangular array for QR matrix decompositon designed by W. M. Gentleman and H. T. Kung.

Keywords:

• Givens transformation
• Householder transformation
• triangular systolic array
• QR matrix decomposition
• QZ matrix decomposition

C.R. Categories:

• F.1.1
• G.1.3
• C.1.3

^† Dept of Computing, Nottingham Trent University.

^∗ Institute for Informatics, Slovak Academy of Sciences, Bratislava, and Nuclear Power Plant Research Institute, Trnava, Slovakia. Funded by the Royal Society Postdoctoral Fellowship Programme.

^† Dept of Computing, Nottingham Trent University.

^∗ Institute for Informatics, Slovak Academy of Sciences, Bratislava, and Nuclear Power Plant Research Institute, Trnava, Slovakia. Funded by the Royal Society Postdoctoral Fellowship Programme.

Notes

^† Dept of Computing, Nottingham Trent University.

^∗ Institute for Informatics, Slovak Academy of Sciences, Bratislava, and Nuclear Power Plant Research Institute, Trnava, Slovakia. Funded by the Royal Society Postdoctoral Fellowship Programme.