I/O Efficient Algorithms for Block Hessenberg Reduction Using Panel Approach

摘要

Reduction to Hessenberg form is a major performance bottleneck in the computation of the eigenvalues of a nonsymmetric matrix; which takes O(N ~3) flops. All the known blocked and unblocked direct Hessenberg reduction algorithms have an I/O complexity of O(N ~3/B). To improve the performance by incorporating matrix-matrix operations in the computation, usually the Hessenberg reduction is computed in two steps: the first reducing the matrix to a banded Hessenberg form, and the second further reducing it to Hessenberg form. We propose and analyse the first step of the reduction, i.e., reduction of a nonsymmetric matrix to banded Hessenberg form of bandwidth t for varying values of N and M (the size of the internal memory), on external memory model introduced by Aggarwal and Vitter for the I/O complexity and show that the reduction can be performed in $O(N^3/min{t,sqrt{M}}B)$ I/Os.