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:
“Mine eye and heart are at a mortal war,
How to divide the conquest of thy sight;
Mine eye my heart thy picture’s sight would bar,
My heart mine eye the freedom of that right.”
—William Shakespeare (1564–1616)
“You see, a person of my acquaintance used to divide people into three categories: those who would prefer to have nothing to hide than have to lie, those who would rather lie than have nothing to hide, and finally those who love both lies and secrets.”
—Albert Camus (1913–1960)
“I divide all literary works into two categories: Those I like and those I don’t like. No other criterion exists for me.”
—Anton Pavlovich Chekhov (1860–1904)