Parallel algorithms for Toeplitz systems
111. 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),
Springer-Verlag, 1991, 75-92.
Abstract:
dvi (3K),
pdf (75K),
ps (30K).
Paper:
dvi (22K),
pdf (119K),
ps (63K).
Abstract
We describe some parallel algorithms for the solution of
Toeplitz linear systems and Toeplitz least squares problems.
First we consider the parallel implementation of the Bareiss algorithm
(which is based on the classical Schur algorithm). The alternative
Levinson algorithm is less suited to parallel implementation because
it involves inner products.
The Bareiss algorithm computes the LU factorization of the Toeplitz
matrix T without pivoting, so can be unstable. For this reason, and
also for the application to least squares problems, it is natural to
consider algorithms for the QR factorization of T. The first
O(n2) serial algorithm for this problem was given by
Sweet (1984),
but Sweet's algorithm seems difficult to implement in parallel.
Also, despite the fact that it computes an orthogonal factorization
of T, Sweet's algorithm can be numerically unstable.
We describe an algorithm of
Bojanczyk, Brent and de Hoog [92]
for the QR factorization problem, and show that it is suitable for
parallel implementation. This algorithm overcomes some (but not all)
of the numerical difficulties of Sweet's algorithm. We
briefly compare some other algorithms, such as the "lattice" algorithm
of Cybenko and the "generalized Schur" algorithm of Chun,
Kailath and Lev-Ari.
Comments
This is a companion paper to [110].
A preliminary version appeared as [108].
For more recent results, see Brent et al
[ 143,
144,
177].
Go to next publication
Return to Richard Brent's index page