A SORTED PARTIAL JACOBI METHOD AND ITS CONVERGENCE ANALYSIS

Jacobi methods for computing the eigendecomposition of a class of so-c alled low-rank-plus-shift symmetric matrices are investigated. An orde r-of-magnitude reduction in the computational complexity can be achiev ed for this special class of matrices by terminating the Jacobi sweep early in a cyclic ordering. It is proved that these partial sweeps com bined with sorting the diagonals still deliver quadratic convergence. It is also shown that useful results can still be obtained even if the low-rank-plus-shift structure only holds approximately. (C) 1998 Else vier Science Inc.