Implementing the qr-algorithm on an array of processors
Robert A. Geijn · 1987
QR algorithms for solving the algebraic eigenvalue problem that initially reduce the matrix to upper Hessenberg form and utilize traditional shifting strategies do not lend themselves to efficient implementation on a grid of processors. This thesis introduces a variation of the QR algorithm that works with the full matrix and show how it can be implemented on a square array of processors. By using a deferred shifting scheme, iterations can be pipelined, thereby reducing processor idle time. A thorough analysis of deferred-shifting techniques show that the asymptotic convergence rate remains acceptable.