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 ◊ 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(n2) processors with nearest-neighbour communication is proposed for the eigenvalue