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 wi is zero, (,di) 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 .
Read more about this topic: Divide-and-conquer Eigenvalue Algorithm
Famous quotes containing the word conquer:
“Only a fully trained Jedi knight with the Force as his ally will conquer Vader and his emperor. If you end your training now—if you choose the quick and easy path, as Vader did—you will become an agent of evil.”
—Leigh Brackett (1915–1978)
“The great end of all religion ... is to purify our hearts—and conquer our passions—and in a word, to make us wiser and better men—better neighbours—better citizens—and better servants of GOD.”
—Laurence Sterne (1713–1768)
“If you would conquer Love, he must be fought
At his first onslaught; sprinkle but a drop
Of water, the new-kindled flame expires.”
—Ovid (Publius Ovidius Naso)