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

Parallel Jacobi-like algorithms are presented for computing a singular-value decomposition of an m × n matrix (m n) and an eigenvalue decomposition of an n × 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 10). A square array of O(n² ) processors with nearest-neighbor communication is proposed for the eigenvalue problem; the associated algorithm requires time $O(nS)$.