Parallel algorithms for digital signal processing

110. R. P. Brent, Parallel algorithms for digital signal processing, Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms (edited by G. H. Golub and P. Van Dooren), Springer-Verlag, 1991, 93-110.

Abstract: dvi (3K), pdf (77K), ps (31K).

Paper: dvi (21K), pdf (119K), ps (63K).


This paper provides an introduction to some parallel algorithms relevant to digital signal processing. First we introduce some basic concepts such as speedup and efficiency of parallel algorithms. We also outline some practical parallel computer architectures: pipelined, SIMD and MIMD machines, hypercubes and systolic arrays.

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.


Toeplitz systems often arise in digital signal processing, and are considered in a companion paper [111].

Go to next publication

Return to Richard Brent's index page