Divide-and-conquer Eigenvalue Algorithm - Conquer

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, where is the last row of and is the first row of . It is now elementary to show that

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, where is diagonal with distinct entries and is any vector with nonzero entries.

If w_i is zero, (,d_i) is an eigenpair of since .

If is an eigenvalue, we have:

where is the corresponding eigenvector. Now

Keep in mind that is a nonzero scalar. Neither nor are zero. If were to be zero, would be an eigenvector of by . If that were the case, would contain only one nonzero position since is distinct diagonal and thus the inner product can not be zero after all. Therefore, we have:

or written as a scalar equation,

This equation is known as the secular equation. The problem has therefore been reduced to finding the roots of the rational function defined by the left-hand side of this equation.

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 flops (for an -degree rational function), making the cost of the iterative part of this algorithm .