# Fast Reduction to Hessenberg Form on Multicore Processors

**Lars Karlsson
**

Department of Computing Science

Umeå University

Umeå

### Abstract:

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.