, so we have Remember that above we pointed out that reducing a Hermitian matrix to tridiagonal form takes 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 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 , but the second part of the algorithm takes as well. For the QR algorithm with a reasonable target precision, this is , whereas for divide-and-conquer it is . The reason for this improvement is that in divide-and-conquer, the part of the algorithm (multiplying 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 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 and the vectors 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 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. References . Numerical linear algebra Divide-and-conquer algorithms