Divide-and-conquer eigenvalue algorithms are a class of eigenvalue algorithms for Hermitian or real symmetric matrices that have recently (circa 1990s) become competitive in terms of stability and efficiency with more traditional algorithms such as the QR algorithm. The basic concept behind these algorithms is the divide-and-conquer approach from computer science. An eigenvalue problem is divided into two problems of roughly half the size, each of these are solved recursively, and the eigenvalues of the original problem are computed from the results of these smaller problems.

This article covers the basic idea of the algorithm as originally proposed by Cuppen in 1981, which is not numerically stable without additional refinements.

Background

As with most eigenvalue algorithms for Hermitian matrices, divide-and-conquer begins with a reduction to tridiagonal matrix, the standard method for this, via Householder reflections if eigenvectors are needed as well. There are other algorithms, such as the Arnoldi iteration, which may do better for certain classes of matrices; we will not consider this further here.

In certain cases, it is possible to deflate an eigenvalue problem into smaller problems. Consider a block diagonal matrix

, and it will almost always be faster to solve these two smaller problems than to solve the original problem all at once. This technique can be used to improve the efficiency of many eigenvalue algorithms, but it has special significance to divide-and-conquer.

. The algorithm can be modified for Hermitian matrices.

Divide

The divide part of the divide-and-conquer algorithm comes from the realization that a tridiagonal matrix is "almost" block diagonal.

.

as a block diagonal matrix, plus a rank-1 correction:

.

, that is to find the diagonalizations. This can be accomplished with recursive calls to the divide-and-conquer algorithm, although practical implementations often switch to the implicitly shifted QR algorithm for small enough submatrices.

Conquer

The conquer part of the algorithm is the unintuitive part. Given the diagonalizations of the submatrices, calculated above, how do we find the diagonalization of the original matrix?

. It is now elementary to show that

.

The case of a zero entry is simple, since if wi,di.

is an eigenvalue, we have:

is the corresponding eigenvector. Now

can not be zero after all. Therefore, we have:

or written as a scalar equation,

This equation is known as the secular equation. The problem has therefore been reduced to finding the roots of the rational function defined by the left-hand side of this equation.

Solving the nonlinear secular equation can be done using an iterative technique, such as the Newton–Raphson method. However, each root can be found in O. The fast multipole method operations.

Analysis

W will use the master theorem for divide-and-conquer recurrences. We can write the recurrence relation:

, so we have

flops for tridiagonal matrices).

flops.

tend to be numerically sparse, meaning that they have many entries with values smaller than the floating point precision, allowing for numerical deflation, i.e. breaking the problem into uncoupled subproblems.

Variants and implementation

The algorithm presented here is the simplest version. In many practical implementations, more complicated rank-1 corrections are used to guarantee stability; some variants even use rank-2 corrections.

There exist specialized root-finding techniques for rational functions that may do better than the Newton-Raphson method in terms of both performance and stability. These can be used to improve the iterative part of the divide-and-conquer algorithm.

The divide-and-conquer algorithm is readily parallelized, and linear algebra computing packages such as LAPACK contain high-quality parallel implementations.

References

• .