Abstract: dvi (3K), pdf (77K), ps (31K).
Paper: dvi (21K), pdf (119K), ps (63K).
To illustrate the basic concepts and key issues, we consider the problem of parallel solution of a nonsingular linear system. Gaussian elimination with pivoting is difficult to implement on many parallel architectures, but omission of pivoting leads to numerical instability. A solution is to implement a parallel version of the orthogonal (QR) decomposition instead of the triangular (LU) decomposition obtained by Gaussian elimination. We consider as an application the solution of linear least squares problems, and compare the method of Bojanczyk, Brent and Kung [65] with that of Gentleman and Kung.
Many problems in digital signal processing are easy to solve if we can find the singular value decomposition (SVD) of a rectangular matrix, or the eigenvalues and eigenvectors of a symmetric (or Hermitian) matrix. We describe some good parallel algorithms for these problems. Often the parallel algorithms are based on old ideas (such as Jacobi's method for finding the eigenvalues of a symmetric matrix) rather than on a straightforward adaption of the best serial algorithms. The parallel algorithms can be implemented efficiently on systolic arrays, but we also mention how they might be implemented on other parallel architectures.