Editing Divide-and-conquer eigenvalue algorithm (section)

==Background==
As with most eigenvalue algorithms for Hermitian matrices, divide-and-conquer begins with a reduction to [[Tridiagonal matrix|tridiagonal]] form.  For an <math>m \times m</math> matrix, the standard method for this, via [[Householder reflection]]s, takes <math>\frac{4}{3}m^{3}</math> floating point operations, or <math>\frac{8}{3}m^{3}</math> if [[eigenvector]]s 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]]
:<math>T = \begin{bmatrix} T_{1} & 0 \\ 0 & T_{2}\end{bmatrix}.</math>
The eigenvalues and eigenvectors of <math>T</math> are simply those of <math>T_{1}</math> and <math>T_{2}</math>, 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.

For the rest of this article, we will assume the input to the divide-and-conquer algorithm is an <math>m \times m</math> real symmetric tridiagonal matrix <math>T</math>.  The algorithm can be modified for Hermitian matrices.