Abstracts: Beresford Parlett
A Simple Explanation of the MRRR Algorithm
The MRRR algorithm for computing eigenvectors of a real symmetric tridiagonal matrix T is a sophisticated version of inverse iteration. It ensures that the computed eigenvectors are nearly orthogonal without using Gram-Schmidt.
The talk will explain the ideas involved and will show the algorithm in action on interesting cases.
More details:
A key idea is the factorization T - wI = LDL' and the calculation of eigenpairs of LDL', each of which has a residual that is small relative to its eigenvalue. This can be achieved for LDL' but cannot always be achieved for T. If an eigenvalue of LDL' has a reasonably large relative gap with respect to its neighbours, its eigenvector will have good orthogonality with all other eigenvectors.
Another key property is that one LDL' factorization can be transformed to one for a different w in such a way that the transformation is exact when small relative perturbations are made to the coefficients of both. It is important to avoid a shift w that leads to growth (large elements in D).
In the MRRR method, a tree is established with an LDL' factorization at each node and with each child LDL' obtained stably from its parent's LDL'. Each wanted eigenpair is available as an eigenvalue of a leaf LDL' that is relatively well separated from all other eigenvalues and therefore has an eigenvector that is nearly orthogonal to all the other eigenvectors.