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:
“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)
“It was not reason that besieged Troy; it was not reason that sent forth the Saracen from the desert to conquer the world; that inspired the crusades; that instituted the monastic orders; it was not reason that produced the Jesuits; above all, it was not reason that created the French Revolution. Man is only great when he acts from the passions; never irresistible but when he appeals to the imagination.”
—Benjamin Disraeli (1804–1881)
“There are very few things impossible in themselves; and we do not want means to conquer difficulties so much as application and resolution in the use of means.”
—François, Duc De La Rochefoucauld (1613–1680)