Down and Up the Representation Tree
B. N. Parlett
University of California at Berkeley
Abstract: In a previous communication we have shown how to compute accurate, and therefore orthogonal, eigenvectors for eigenvalues with large relative separations from the rest of the spectrum of a relatively robust representation of a symmetric tridiagonal matrix T. A relatively robust representation (rep, for short) is a suitable factorization of a translate of T. Here we address the general case. The spectrum of T may have several clusters of close eigenvalues and there may be clusters within clusters within clusters. In order to secure large relative gaps for each eigenvalue it will be necessary to employ shifts very close to each cluster. The associated representations are best represented by a rooted tree.
The root is the original rep. Each internal node is one of the reps and is associated with a particular subset of the spectrum. The children of a node belong to subsets of the parent's set. Each subset is characterized by there being no large relative gaps between the eigenvalues (as seen by the parent) in the subset. Finally each leaf corresponds to a rep from which a single eigenvector is computed.
The previous communication mentioned at the beginnig ensures that each computed eigenvector has tiny residual norm and O(n*eps) orthogonality with respect to the parent of its leaf.
Sometimes the tree is shallow but whenever there is a tight cluster within a cluster the tree's height increases by one. We explain how the tree is constructed and we show that the residual norms and mutual orthogonality are harmed little as the tree is mounted from the leaves. Finally all residual norms are related to the root and the bound on orthogonality for the whole set is still O(n*eps).
Authors: B.N.Parlett and I.S.Dhillon.