The Implicit QR Algorithm
In modern computational practice, the QR algorithm is performed in an implicit version which makes the use of multiple shifts easier to introduce. The matrix is first brought to upper Hessenberg form as in the explicit version; then, at each step, the first column of is transformed via a small-size Householder similarity transformation to the first column of (or ), where, of degree, is the polynomial that defines the shifting strategy (often, where and are the two eigenvalues of the trailing principal submatrix of, the so-called implicit double-shift). Then successive Householder transformation of size are performed in order to return the working matrix to upper Hessenberg form. This operation is known as bulge chasing, due to the peculiar shape of the non-zero entries of the matrix along the steps of the algorithm. As in the first version, deflation is performed as soon as one of the sub-diagonal entries of is sufficiently small.
Read more about this topic: QR Algorithm
Famous quotes containing the word implicit:
“A piece of advice always contains an implicit threat, just as a threat always contains an implicit piece of advice.”
—José Bergamín (1895–1983)