The divide part of the divide-and-conquer algorithm comes from the realization that a tridiagonal matrix is "almost" block diagonal.
The size of submatrix we will call, and then is . Note that the remark about being almost block diagonal is true regardless of how is chosen (i.e., there are many ways to so decompose the matrix). However, it makes sense, from an efficiency standpoint, to choose .
We write as a block diagonal matrix, plus a rank-1 correction:
The only difference between and is that the lower right entry in has been replaced with and similarly, in the top left entry has been replaced with .
The remainder of the divide step is to solve for the eigenvalues (and if desired the eigenvectors) of and, that is to find the diagonalizations and . This can be accomplished with recursive calls to the divide-and-conquer algorithm, although practical implementations often switch to the QR algorithm for small enough submatrices.
Read more about this topic: Divide-and-conquer Eigenvalue Algorithm
Famous quotes containing the word divide:
“Child of Light! thy limbs are burning
Through the vest which seems to hide them;
As the radiant lines of morning
Through the clouds ere they divide them;
And this atmosphere divinest
Shrouds thee wheresoe’er thou shinest.”
—Percy Bysshe Shelley (1792–1822)
“We know only a single science, the science of history. One can look at history from two sides and divide it into the history of nature and the history of men. However, the two sides are not to be divided off; as long as men exist the history of nature and the history of men are mutually conditioned.”
—Karl Marx (1818–1883)
“The king said, -Divide the living boy in two; then give half to the one, and half to the other. But the woman whose son was alive said to the king -because compassion for her son burned within her - -Please, my lord, give her the living boy; certainly do not kill him! The other said, -It shall be neither mine nor yours; divide it. Then the king responded: -Give the first woman the living boy; do not kill him. She is his mother.”
—Bible: Hebrew, 1 Kings. 3:25-37.
Solomon resolves a dispute between two women over a child. Solomon’s wisdom was proven by this story.