An Input/Output Efficient Algorithm for Hessenberg Reduction

摘要

Reduction of an N × N nonsymmetric matrix to Hessenberg form which takes O(N3) flops and O(N3/B) I/Os is a major performance bottleneck in the computing of its eigenvalues. Usually to improve the performance, this Hessenberg reduction is computed in two steps: the first one reduces the matrix to a banded Hessenberg form, and the second one further reduces it to Hessenberg form by incorporating more matrix-matrix operations in the computation. We analyse the two steps of the Hessenberg reduction problem on the external memory model (of Aggarwal and Vitter) for their I/O complexities. We propose and analyse a tile based algorithm for the first step of the reduction and show that it takes O(N3/Bmin{t,M}) I/Os. For the reduction of a banded Hessenberg matrix of bandwidth t to Hessenberg form, we propose an algorithm, which uses tight packing of bulges, and requires only O(t2N2/B + N3/tB) I/Os. Combining the results of the two steps of the reduction, we show that the Hessenberg reduction can be performed in O(N3/MB) I/Os, when N is sufficiently large. To the best of our knowledge, the proposed algorithm is the first I/O optimal algorithm for Hessenberg reduction; the worst case I/O complexity matches the known lower bound of the problem.