Numerical analysis Eigenvalue computations Theorem

Divide-and-conquer eigenvalue algorithm

Builds on Tridiagonal matrix Symmetric matrix Diagonal matrix Eigenvalue Eigenvector Orthogonal matrix

Statement

Let $T \in \R^{n \times n}$ be a symmetric tridiagonal matrix with diagonal entries $a_1, \dots, a_n$ and off-diagonal entries $b_1, \dots, b_{n-1}$ , and let $1 \le k < n$ with $\beta = b_k$ .

(Splitting.) Let $T_1$ be the leading $k \times k$ block of $T$ with $a_k$ replaced by $a_k - \beta$ , and $T_2$ the trailing $(n-k) \times (n-k)$ block with $a_{k+1}$ replaced by $a_{k+1} - \beta$ . With $u = e_k + e_{k+1}$ , $T = \begin{pmatrix} T_1 & 0 \\ 0 & T_2 \end{pmatrix} + \beta \, u u^T.$ If $T_i = Q_i D_i Q_i^T$ with $Q_i$ orthogonal and $D_i$ diagonal, then $T = Q (D + \beta z z^T) Q^T$ with $Q = \mathrm{diag}(Q_1, Q_2)$ , $D = \mathrm{diag}(D_1, D_2)$ and $z = Q^T u$ .
(Secular equation.) Let $D = \mathrm{diag}(d_1, \dots, d_n)$ with $d_1 < d_2 < \cdots < d_n$ , let $z \in \R^n$ have all entries nonzero, and let $\beta > 0$ . Then the eigenvalues of $D + \beta z z^T$ are the $n$ roots of $f(\lambda) = 1 + \beta \sum_{i=1}^{n} \frac{z_i^2}{d_i - \lambda},$ they satisfy $d_1 < \lambda_1 < d_2 < \lambda_2 < \cdots < d_n < \lambda_n$ , and $(D - \lambda_j I)^{-1} z$ is an eigenvector for $\lambda_j$ .

Remarks

Part 1 is a direct check of entries: $u u^T$ has ones exactly in positions $(k, k)$ , $(k, k+1)$ , $(k+1, k)$ , $(k+1, k+1)$ . For part 2, if $(D + \beta z z^T) x = \lambda x$ and $\lambda$ is not a $d_i$ , then $x = -\beta (z^T x)(D - \lambda I)^{-1} z$ with $z^T x \ne 0$ , and taking the inner product with $z$ gives $f(\lambda) = 0$ . Since $f'(\lambda) = \beta \sum_i z_i^2/(d_i - \lambda)^2 > 0$ and $f$ goes from $-\infty$ to $+\infty$ between consecutive poles, and from $-\infty$ to $1$ after $d_n$ , there is exactly one root in each of these $n$ intervals. For $\beta < 0$ the interlacing is reversed: $\lambda_1 < d_1 < \lambda_2 < \cdots < \lambda_n < d_n$ . If some $z_i = 0$ or some $d_i$ coincide, then some $d_i$ is already an eigenvalue and the problem is reduced in size first; this step is called deflation.

The algorithm applies the splitting recursively, solves the small problems directly, and merges with the secular equation. Each root is found by a safeguarded Newton-type iteration on $f$ in its interval. Computing the eigenvectors in a numerically orthogonal way needs a careful recomputation of $z$ , due to Gu and Eisenstat.

Going deeper

For a student

Symmetric eigenvalue problems are first reduced to tridiagonal form by orthogonal transformations, so this algorithm handles the core step. It is among the fastest methods when all eigenvalues and eigenvectors are wanted, because deflation is frequent in practice and the merges use matrix multiplication. The interlacing in part 2 is a rank-one analogue of the Cauchy interlacing theorem. The method was proposed by Cuppen in 1981.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Diagonal matrix concept
Eigenvalue concept
Eigenvector concept
Orthogonal matrix concept
Symmetric matrix concept
Tridiagonal matrix concept
Divide-and-conquer eigenvalue algorithm statement

Tag	`BJE8P9TH88`
URI	`m2://BJE8P9TH88`
Kind	statement, theorem
Writing	W0 stub
MSC	65F15
Status	This copy of the site has no build data. Run `m2 status BJE8P9TH88`.
About	Eigenvalue algorithm
Uses	Tridiagonal matrix, Symmetric matrix, Diagonal matrix, Eigenvalue, Eigenvector, Orthogonal matrix
Same as	Wikidata Q5283998 Wikipedia Divide-and-conquer eigenvalue algorithm