Parallel two-stage reduction to Hessenberg form using dynamic scheduling on shared-memory architectures

We consider parallel reduction of a real matrix to Hessenberg form using orthogonal transformations. Standard Hessenberg reduction algorithms reduce the columns of the matrix from left to right in either a blocked or unblocked fashion. However, the standard blocked variant performs 20% of the computations in terms of matrix–vector multiplications. We show that a two-stage approach consisting of an intermediate reduction to block Hessenberg form speeds up the reduction by avoiding matrix–vector multiplications. We describe and evaluate a new high-performance implementation of the two-stage approach that attains significant speedups over the one-stage approach. The key components are a dynamically scheduled implementation of Stage 1 and a blocked, adaptively load-balanced implementation of Stage 2.

► A dynamically scheduled shared-memory implementation of a two-stage reduction to Hessenberg form is presented and evaluated.
► Experiments show that the intermediate block Hessenberg form needs to have a relatively small number of non-zero sub-diagonals due to a performance trade-off between the two stages.