An Efficient Parallel Version of the Householder-QL Matrix Diagonalisation Algorithm

In this paper we report an effective parallelisation of the Householder routine for the reduction of a real symmetric matrix to tri-diagonal form and the QL algorithm for the diagonalisation of the resulting matrix. The Householder algorithm scales like $\alpha N^3/P+\beta N^2 \log_2(P)$ and the QL algorithm like $\gamma N^2 + \delta N^3/P$ as the number of processors $P$ is increased for fixed problem size. The constant parameters $\alpha$, $\beta$, $\gamma$ and $\delta$ are obtained empirically. When the eigenvalues only are required the Householder method scales as above while the QL algorithm remains sequential. The code is implemented in c in conjunction with the Message Passing Interface (MPI) libraries and verified on a sixteen node IBM SP2 and for real matrices that occur in the simulation of properties of crystalline material