PARALLEL ALGORITHMS FOR DIGITAL SIGNAL PROCESSING

RICHARD P. BRENT

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 [1] with that of Gentleman and Kung [4].

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

Only the Abstract is given here. The full paper appeared as [2]. Toeplitz systems often arise in digital signal processing, and are considered in a companion paper [3].

References

1. A. W. Bojanczyk, R. P. Brent and H. T. Kung, “Numerically stable solution of dense systems of linear equations using mesh-connected processors”, SIAM J. Scientific and Statistical Computing 5 (1984), 95–104. MR 85b:65026. Also appeared as Report TR-CS-81-01, Department of Computer Science, ANU; and as Report TR-CS-81-119, Department of Computer Science, CMU (May 1981), 23 pp. rpb065.

2. R. P. Brent, “Parallel algorithms for digital signal processing”, Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms (Proceedings NATO ASI, Leuven, Belgium, August 1988, edited by G. H. Golub and P. Van Dooren), NATO ASI Series F: Computer and Systems Sciences, Vol. 70, Springer-Verlag, 1991, 93–110. ISBN 3-540-52300-6. rpb110.

1991 Mathematics Subject Classification. Primary 65Y05; Secondary 65F05, 65F25, 65Y10, 68Q35.

Key words and phrases. Signal processing, systolic algorithm, fast algorithm, parallel algorithm, Gaussian elimination, least squares, singular value decomposition, SVD, orthogonal factorization, QR factorization.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1991, Springer-Verlag.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb110a typeset using AMS-L^{A}TEX

3. R. P. Brent, “Parallel algorithms for Toeplitz systems”, Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms (edited by G. H. Golub and P. Van Dooren), rpb111.

4. W. M. Gentleman and H. T. Kung, “Matrix triangularization by systolic arrays”, Proc. SPIE, Volume 298, Real-Time Signal Processing IV, SPIE, August 1981.

Computer Sciences Laboratory, Australian National University, Canberra E-mail address: rpb@cslab.anu.edu.au