The Orthogonal Rayleigh Quotient Iteration (ORQI) method Original Research Article

This paper presents a new method for computing all the eigenvectors of a real n×n symmetric band matrix T. The algorithm computes an orthogonal matrix Q=[q1,…,qn] and a diagonal matrix Λ=diag{λ1,…,λn} such that TQ=QΛ. The basic ideas are rather simple. Assume that q1,…,qk−1 and λ1,…,λk−1 have already been computed. Then qk is obtained via the Rayleigh Quotient Iteration (RQI) method. Starting from an arbitrary vector u0 the RQI method generates a sequence of vectors uℓ, ℓ=1,2,… , and a sequence of scalars ρℓ, ℓ=0,1,2,… The theory tells us that these two sequences converge (almost always) to an eigenpair (ρ*,u*). The appeal of the RQI method comes from the observation that the final rate of convergence is cubic. Furthermore, if the starting point is forced to satisfy qTiu0=0 for i=1,…,k−1, as our method does, then all the coming vectors, uℓ,ℓ=1,2,… , and their limit point, u*, should stay orthogonal to q1,…,qk−1. In practice orthogonality is lost because of rounding errors. This difficulty is resolved by successive orthogonalization of uℓ against q1,…,qk−1. The key for effective implementation of the algorithm is to use a selective orthogonalization scheme in which uℓ is orthogonalized only against “close” eigenvectors. That is, uℓ is orthogonalized against qi only if ρℓ−λiless-than-or-equals, slantγ where γ is a small threshold value, e.g., γ=short parallelTshort parallel∞/1000. An essential feature of the proposed orthogonalization scheme is the use of reorthogonalization. The ORQI method is supported by forward and backward error analysis. Preliminary experiments on medium-size problems (nless-than-or-equals, slant1000) are quite encouraging. The average number of iterations per eigenvector was less than 13, while the overall number of flops required for orthogonalizations is often below n3/2.