 Divideandconquer eigenvalue algorithm

Divideandconquer 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 divideandconquer 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.
Here we present the simplest version of a divideandconquer algorithm, similar to the one originally proposed by Cuppen in 1981. Many details that lie outside the scope of this article will be omitted; however, without considering these details, the algorithm is not fully stable.
Contents
Background
As with most eigenvalue algorithms for Hermitian matrices, divideandconquer begins with a reduction to tridiagonal form. For an matrix, the standard method for this, via Householder reflections, takes flops, or 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
The eigenvalues and eigenvectors of T are simply those of T_{1} and T_{2}, 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 divideandconquer.
For the rest of this article, we will assume the input to the divideandconquer algorithm is an real symmetric tridiagonal matrix T. Although the algorithm can be modified for Hermitian matrices, we do not give the details here.
Divide
The divide part of the divideandconquer algorithm comes from the realization that a tridiagonal matrix is "almost" block diagonal.
The size of submatrix T_{1} we will call , and then T_{2} is . Note that the remark about T being almost block diagonal is true regardless of how n is chosen (i.e., there are many ways to so decompose the matrix). However, it makes sense, from an efficiency standpoint, to choose .
We write T as a block diagonal matrix, plus a rank1 correction:
The only difference between T_{1} and is that the lower right entry t_{nn} in has been replaced with t_{nn} − β and similarly, in the top left entry t_{n + 1,n + 1} has been replaced with t_{n + 1,n + 1} − β.
The remainder of the divide step is to solve for the eigenvalues (and if desired the eigenvectors) of and , that is to find the diagonalizations and . This can be accomplished with recursive calls to the divideandconquer algorithm, although practical implementations often switch to the 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?
First, define , where is the last row of Q_{1} and is the first row of Q_{2}. It is now elementary to show that
The remaining task has been reduced to finding the eigenvalues of a diagonal matrix plus a rankone correction. Before showing how to do this, let us simplify the notation. We are looking for the eigenvalues of the matrix D + ww^{T}, where D is diagonal with distinct entries and w is any vector with nonzero entries.
If w_{i} is zero, (e_{i},d_{i}) is an eigenpair of D + ww^{T} since (D + ww^{T})e_{i} = De_{i} = d_{i}e_{i}.
If λ is an eigenvalue, we have:
 (D + ww^{T})q = λq
where q is the corresponding eigenvector. Now
 (D − λI)q + w(w^{T}q) = 0
 q + (D − λI) ^{− 1}w(w^{T}q) = 0
 w^{T}q + w^{T}(D − λI) ^{− 1}w(w^{T}q) = 0
Keep in mind that w^{T}q is a nonzero scalar. Neither w nor q are zero. If w^{T}q were to be zero, q would be an eigenvector of D by (D + ww^{T})q = λq. If that were the case, q would contain only one nonzero position since D is distinct diagonal and thus the inner product w^{T}q can not be zero after all. Therefore, we have:
 1 + w^{T}(D − λI) ^{− 1}w = 0
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 lefthand side of this equation.
All general eigenvalue algorithms must be iterative, and the divideandconquer algorithm is no different. Solving the nonlinear secular equation requires an iterative technique, such as the Newton–Raphson method. However, each root can be found in O(1) iterations, each of which requires Θ(m) flops (for an mdegree rational function), making the cost of the iterative part of this algorithm Θ(m^{2}).
Analysis
As is common for divide and conquer algorithms, we will use the Master theorem to analyze the running time. Remember that above we stated we choose . We can write the recurrence relation:
In the notation of the Master theorem, a = b = 2 and thus log _{b}a = 1. Clearly, Θ(m^{2}) = Ω(m^{1}), so we have
 T(m) = Θ(m^{2})
Remember that above we pointed out that reducing a Hermitian matrix to tridiagonal form takes flops. This dwarfs the running time of the divideandconquer part, and at this point it is not clear what advantage the divideandconquer algorithm offers over the QR algorithm (which also takes Θ(m^{2}) flops for tridiagonal matrices).
The advantage of divideandconquer comes when eigenvectors are needed as well. If this is the case, reduction to tridiagonal form takes , but the second part of the algorithm takes Θ(m^{3}) as well. For the QR algorithm with a reasonable target precision, this is , whereas for divideandconquer it is . The reason for this improvement is that in divideandconquer, the Θ(m^{3}) part of the algorithm (multiplying Q matrices) is separate from the iteration, whereas in QR, this must occur in every iterative step. Adding the flops for the reduction, the total improvement is from to flops.
Practical use of the divideandconquer algorithm has shown that in most realistic eigenvalue problems, the algorithm actually does better than this. The reason is that very often the matrices Q and the vectors z 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 rank1 corrections are used to guarantee stability; some variants even use rank2 corrections.^{[citation needed]}
There exist specialized rootfinding techniques for rational functions that may do better than the NewtonRaphson method in terms of both performance and stability. These can be used to improve the iterative part of the divideandconquer algorithm.
The divideandconquer algorithm is readily parallelized, and linear algebra computing packages such as LAPACK contain highquality parallel implementations.
References
 Demmel, James W. (1997), Applied Numerical Linear Algebra, Philadelphia, PA: Society for Industrial and Applied Mathematics, ISBN 0898713897, MR1463942.
Numerical linear algebra Key concepts Problems Hardware Software Categories:
Wikimedia Foundation. 2010.