OLD AND NEW ALGORITHMS FOR TOEPLITZ SYSTEMS

RICHARD P. BRENT

Abstract

Toeplitz linear systems and Toeplitz least squares problems commonly arise in digital signal processing. In this paper we survey some old, “well known” algorithms, and some recent algorithms, for solving these problems. We concentrate our attention on algorithms which can be implemented efficiently on a variety of parallel machines (including pipelined vector processors and systolic arrays). We distinguish between algorithms which require inner products, and algorithms which avoid inner products, and thus are better suited to parallel implementation on some parallel architectures. Finally, we mention some “asymptotically fast” O(n(log n)^{2}) algorithms and compare them with O(n^{2}) algorithms.

Comments

Only the Abstract is given here. The full paper appeared as [1], and a revision appeared as [2].

References

1. R. P. Brent, “Old and new algorithms for Toeplitz systems”, Proceedings SPIE, Volume 975, Advanced Algorithms and Architectures for Signal Processing III (edited by Franklin T. Luk), SPIE, Bellingham, Washington, 1989, 2–9. ISBN 0-8194-0010-6. Also appeared as Report TR-CS-88-10, Computer Sciences Laboratory, ANU, July 1988, 8 pp. rpb108.

2. 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), NATO ASI Series F: Computer and Systems Sciences, Vol. 70, Springer-Verlag, 1991, 75–92. ISBN 3-540-52300-6. rpb111.

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

1991 Mathematics Subject Classification. Primary 65Y05; Secondary 47B35, 65F05, 65F30, 65Y10. Key words and phrases. Toeplitz matrix, Toeplitz system, systolic algorithm, Bareiss algorithm, fast

algorithm, parallel algorithm.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1991, Springer-Verlag. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb108a typeset using AMS-L^{A}TEX