PARALLEL ALGORITHMS FOR TOEPLITZ SYSTEMS

RICHARD P. BRENT

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(n^{2}) serial algorithm for this problem was given by Sweet [5], 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 [1] 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

Only the Abstract is given here. The full paper appeared as [3], and a preliminary version appeared as [2]. For more recent results, see [4].

References

1. A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, “QR factorization of Toeplitz matrices”, Numerische Mathematik 49 (1986), 81–94. MR 87k:65050. rpb092.

2. 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.

3. R. P. Brent, “Parallel algorithms for Toeplitz systems”, Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms (Proc. 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, 75–92. ISBN 3-540-52300-6. rpb111.

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. rpb111a typeset using AMS-L^{A}TEX

4. A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, Stability Analysis of Fast Toeplitz Linear System Solvers, Report CMA-MR17-91, Centre for Mathematical Analysis, ANU, August 1991, 23 pp. rpb126.

5. D. R. Sweet, “Fast Toeplitz orthogonalization”, Numerische Mathematik 43 (1984), 1–21.

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