Editing Divide-and-conquer eigenvalue algorithm (section)

==Analysis==

W will use the [[Master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]] to analyze the running time.  Remember that above we stated we choose <math>n \approx m/2</math>.  We can write the [[recurrence relation]]:
:<math>T(m) = 2 \times T\left(\frac{m}{2}\right) + \Theta(m^{2})</math>
In the notation of the Master theorem, <math>a = b = 2</math> and thus <math>\log_{b} a = 1</math>.  Clearly, <math>\Theta(m^{2}) = \Omega(m^{1})</math>, so we have
:<math>T(m) = \Theta(m^{2})</math>

Above, we pointed out that reducing a Hermitian matrix to tridiagonal form takes <math>\frac{4}{3}m^{3}</math> flops.  This dwarfs the running time of the divide-and-conquer part, and at this point it is not clear what advantage the divide-and-conquer algorithm offers over the QR algorithm (which also takes <math>\Theta(m^{2})</math> flops for tridiagonal matrices).

The advantage of divide-and-conquer comes when eigenvectors are needed as well.  If this is the case, reduction to tridiagonal form takes <math>\frac{8}{3}m^{3}</math>, but the second part of the algorithm takes <math>\Theta(m^{3})</math> as well.  For the QR algorithm with a reasonable target precision, this is <math>\approx 6 m^{3}</math>, whereas for divide-and-conquer it is <math>\approx \frac{4}{3}m^{3}</math>.  The reason for this improvement is that in divide-and-conquer, the <math>\Theta(m^{3})</math> part of the algorithm (multiplying <math>Q</math> matrices) is separate from the iteration, whereas in QR, this must occur in every iterative step.  Adding the <math>\frac{8}{3}m^{3}</math> flops for the reduction, the total improvement is from <math>\approx 9 m^{3}</math> to <math>\approx 4 m^{3}</math> flops.

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 <math>Q</math> and the vectors <math>z</math> 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.