I/O efficient QR and QZ algorithms
Sraban Kumar Mohanty, Sajith Gopalan · 2012
The QR algorithm solves the standard eigenvalue problem. Analogously, the QZ-algorithm solves the generalised eigenvalue problem. Both are iterative algorithms. We study these algorithms on the External Memory model introduced by Aggarwal and Vitter and analyse them for their I/O and seek complexities. We analyse the multi shift QR algorithm [1]; this algorithm chases m × m bulges, where m is the number of shifts, using both matrix-vector and matrix-matrix operations. We also investigate the small-bulge multishift QR algorithm [2] which was proposed to avoid the phenomenon called shift blurring. We propose a tile based small-bulge multi shift QR algorithm which is scalable and more amenable for multicore architecture than the traditional panel based algorithms and that under certain conditions of the number of shifts has better seek and I/O complexities. We prove analogous results for the QZ algorithm [3] too.