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:
“Everything necessarily is or is not, and will be or will not be; but one cannot divide and say that one or the other is necessary. I mean, for example: it is necessary for there to be or not to be a sea-battle tomorrow; but it is not necessary for a sea-battle to take place tomorrow, or for one not to take place—though it is necessary for one to take place or not to take place.”
—Aristotle (384–322 B.C.)
“We may divide characters into flat and round.”
—E.M. (Edward Morgan)
“To divide one’s life by years is of course to tumble into a trap set by our own arithmetic. The calendar consents to carry on its dull wall-existence by the arbitrary timetables we have drawn up in consultation with those permanent commuters, Earth and Sun. But we, unlike trees, need grow no annual rings.”
—Clifton Fadiman (b. 1904)