Old and new algorithms for Toeplitz systems
108. 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.
Abstract:
dvi (3K),
pdf (67K),
ps (27K).
Paper:
dvi (22K),
pdf (114K),
ps (59K).
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(n2) algorithms.
Comments
A revision appeared as [111].
For more recent results, see Brent et al
[ 143,
144,
177].
Go to next publication
Return to Richard Brent's index page