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:
“The failure of academic feminists to recognize difference as a crucial strength is a failure to reach beyond the first patriarchal lesson. In our world, divide and conquer must become define and empower.”
—Audre Lorde (1934–1992)
“We have to divide mother love with our brothers and sisters. Our parents can help us cope with the loss of our dream of absolute love. But they cannot make us believe that we haven’t lost it.”
—Judith Viorst (20th century)
“To have the fear of God before our eyes, and, in our mutual dealings with each other, to govern our actions by the eternal measures of right and wrong:MThe first of these will comprehend the duties of religion;Mthe second, those of morality, which are so inseparably connected together, that you cannot divide these two tables ... without breaking and mutually destroying them both.”
—Laurence Sterne (1713–1768)