A divide-and-conquer method for tridiagonalizing symmetric matrices with repeated eigenvalues
Christian H Bischof, Xin Sun · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
The authors describe a divide-and-conquer tridiagonalization approach for matrices with repeated eigenvalues. The algorithm hinges on the fact that, loosely speaking, a symmetric matrix with bandwidth b and k distinct eigenvalues must be block diagonal with diagonal blocks of size at most bk. A slight modification of the usual orthogonal bandreduction algorithm allows them to reveal this structure, which then leads to parallelism in the form of independent diagonal blocks. Compared to the usual Householder reduction algorithm, the approach allows significantly more scope for the exploitation of parallelism and can reduce the number of floating-point operations by up to 50%. The actual savings depend very much on the number of distinct eigenvalues, but at worst it behaves exactly like the usual tridiagonalization procedure. They also mention how the resulting tridiagonal structure can be employed very advantageously in determining range and nullspaces of symmetric matrices with two distinct eigenvalues, one of which is zero.