The Solution of Singular-Value and Symmetric Eigenvalue Problems on Multiprocessor Arrays

Abstract

Parallel Jacobi-like algorithms are presented for computing a singular-value decomposition of an $m \times n$ matrix $(m \geqq n)$ and an eigenvalue decomposition of an $n \times n$ symmetric matrix. A linear array of $O(n)$ processors is proposed for the singular-value problem; the associated algorithm requires time $O(mnS)$, where S is the number of sweeps (typically $S \leqq 10$). A square array of $O(n^2 )$ processors with nearest-neighbor communication is proposed for the eigenvalue problem; the associated algorithm requires time $O(nS)$.