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.
As with most eigenvalue algorithms for Hermitian matrices, divide-and-conquer begins with a reduction to tridiagonal form. For an
m x m
4 | |
3 |
m3
8 | |
3 |
m3
In certain cases, it is possible to deflate an eigenvalue problem into smaller problems. Consider a block diagonal matrix
T=\begin{bmatrix}T1&0\ 0&T2\end{bmatrix}.
T
T1
T2
For the rest of this article, we will assume the input to the divide-and-conquer algorithm is an
m x m
T
The divide part of the divide-and-conquer algorithm comes from the realization that a tridiagonal matrix is "almost" block diagonal.
The size of submatrix
T1
n x n
T2
(m-n) x (m-n)
T
n
n ≈ m/2
We write
T
The only difference between
T1
\hat{T}1
tnn
\hat{T}1
tnn-\beta
\hat{T}2
tn+1,n+1
tn+1,n+1-\beta
The remainder of the divide step is to solve for the eigenvalues (and if desired the eigenvectors) of
\hat{T}1
\hat{T}2
\hat{T}1=Q1D1
T | |
Q | |
1 |
\hat{T}2=Q2D2
T | |
Q | |
2 |
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
zT=
T | |
(q | |
1 |
T | |
,q | |
2 |
)
T | |
q | |
1 |
Q1
T | |
q | |
2 |
Q2
T=\begin{bmatrix}Q1&\ &Q2\end{bmatrix}\left(\begin{bmatrix}D1&\ &D2\end{bmatrix}+\betazzT\right)\begin{bmatrix}
T | |
Q | |
1 |
&\ &
T | |
Q | |
2 |
\end{bmatrix}
The remaining task has been reduced to finding the eigenvalues of a diagonal matrix plus a rank-one correction. Before showing how to do this, let us simplify the notation. We are looking for the eigenvalues of the matrix
D+wwT
D
w
w=\sqrt{|\beta|} ⋅ z
The case of a zero entry is simple, since if wi is zero, (
ei
ei
D+wwT
(D+wwT)ei=Dei=diei
If
λ
(D+wwT)q=λq
q
(D-λI)q+w(wTq)=0
q+(D-λI)-1w(wTq)=0
wTq+wT(D-λI)-1w(wTq)=0
wTq
w
q
wTq
q
D
(D+wwT)q=λq
q
D
wTq
1+wT(D-λI)-1w=0
1+
m | |
\sum | |
j=1 |
| |||||||
dj-λ |
=0.
All general eigenvalue algorithms must be iterative, and the divide-and-conquer 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
\Theta(m)
m
\Theta(m2)
W will use the master theorem for divide-and-conquer recurrences to analyze the running time. Remember that above we stated we choose
n ≈ m/2
T(m)=2 x T\left(
m | |
2 |
\right)+\Theta(m2)
a=b=2
logba=1
\Theta(m2)=\Omega(m1)
T(m)=\Theta(m2)
Above, we pointed out that reducing a Hermitian matrix to tridiagonal form takes
4 | |
3 |
m3
\Theta(m2)
The advantage of divide-and-conquer comes when eigenvectors are needed as well. If this is the case, reduction to tridiagonal form takes
8 | |
3 |
m3
\Theta(m3)
≈ 6m3
≈
4 | |
3 |
m3
\Theta(m3)
Q
8 | |
3 |
m3
≈ 9m3
≈ 4m3
Practical use of the divide-and-conquer 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
z
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.