Fast Reduction to Hessenberg Form on Multicore Processors

Lars Karlsson
Department of Computing Science
Umeå University


The Hessenberg form of a matrix is often used as a preprocessing step in numerical algorithms. For example, solvers for Sylvester equations, shifted linear systems, and the nonsymmetric eigenvalue problem typically rely on reduction to Hessenberg form. However, the standard algorithm for Hessenberg reduction is quite slow since 20% of the flops are applied in terms of matrix-vector products. In this talk, we describe a new blocked algorithm designed for multicore architectures. By better utilizing the memory hierarchy, the new algorithm is faster than standard Hessenberg reduction even though it requires 60 % more flops.