A parallel algorithm for the reduction to tridiagonal form for eigendecomposition

Abstract

A new algorithm for the orthogonal reduction of a symmetric matrix to tridiagonal form is developed and analysed. It uses a Cholesky factorization of the original matrix and the rotations are applied to the factors. The idea is similar to the one used for the one-sided Jacobi algorithms [B. Zhou and R. Brent, A Parallel Ordering Algorithm for Efficient One-Sided Jacobi SVD Computations, Proc. Sixth IASTED-ISMM International Conference on Parallel and Distributed Computing and Systems, pp. 369{372, 1994.]. The algorithm uses little communication, accesses data with stride one and is to a large extent independent of data distribution. It has been implemented on the Fujitsu VPP 500. The algorithm is designed to be the first step of an eigensolver so the procedure for accumulating transforms for eventual calculation of eigenvectors is given. Show more