The running time of an algorithm depends on both arithmetic and communication (i.e., data movement)
costs, and the relative costs of communication are growing over time. In this work, we present sequential and
parallel algorithms for tridiagonalizing a symmetric band matrix that asymptotically reduce communication
compared to previous approaches.
The tridiagonalization of a symmetric band matrix is a key kernel in solving the symmetric eigenvalue
problem for both full and band matrices. In order to preserve sparsity, tridiagonalization routines use
annihilate-and-chase procedures that previously have suered from poor data locality. We improve data
locality by reorganizing the computation and obtain asymptotic improvements. We consider the cases of
computing eigenvalues only and of computing eigenvalues and all eigenvectors.