## 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).

## Abstract

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.

## Comments

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