Parallel eigenvalue decomposition for Toeplitz and related matrices

Parallel algorithms for computing the eigenvalues and eigenvectors of real, symmetric Toeplitz and Toeplitz-related low-displacement-rank matrices (e.g. sample covariance matrices) are presented. In particular, the parallel implementation of a class of modified Rayleigh-quotient iteration methods is discussed. Apart from parallel factorization of Toeplitz and Toeplitz-related matrices, other levels of inherent parallelism are exploited, rendering higher efficiency for parallel implementation of these algorithms. Specifically, a parallel multisectioning method is developed on a linear array of locally connected processors