Reduction to condensed form for the eigenvalue problem on distributed memory architectures (Q1201010)

The authors discuss a parallel implementation of the LAPACK routines for reduction of a general matrix to Hessenberg form (and a symmetric matrix to tridiagonal form). The LAPACK project is designed to update the classical sequential codes for shared memory machines and this implementation is for running on the Intel Touchstone Delta. It is assumed the multicomputer has \(p\) nodes \(P_ 0,\dots,P_{p-1}\) connected by some network. If \(A\in \mathbb{R}^{n\times n}\) and the panelwidth \(m\) is such that \(n=r*m\), the partition \(A^{(k)}=(A_ 1^{(k)}A_ 2^{(k)}\dots A_ r^{(k)})\), where \(A_ j^{(k)}\in\mathbb{R}^{n\times m}\) is a panel of width \(m\). A panelwrapped scheme assigns \(A^{(k)}_ j\) to node \(P_{(j-1)\mod p}\), so that \(A_{i+1},A_{i+p+1},\dots\) are assigned to \(P_ i\). The authors then describe both sequential and parallel implementations of the reduction of Hessenberg form (and tridiagonal form in the symmetric case) using Householder transformations and follow with a description of the blocked form of these. The paper concludes with results of extensive numerical experiments with the parallel routines on matrices up to \(n=8000\) in size.