Department of Computing Science
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.