Parallel computational algorithms are presented for inversion of certain classes of Toeplitz matrix (i.e., matrices for which ai,j = &agr;i-j. Let A be a circulant Toeplitz matrix of order n, and let L and U be the strictly lower triangular matrix and the upper triangular matrix whose sum is A. For any real &egr;, denote A&egr; = L&egr;+ . A parallel algorithm is presented for inverting any nonsingular A&egr; with &egr;=O, in 6 log n + 6 parallel steps with 2n processors. In this paper, log n denotes :9Ilog2n:9I. When &egr; = O then A&egr; reduces to an upper triangular Toeplitz matrix AO, whose inverse can be approximated to any desired accuracy by inverting A&egr;, for sufficiently small &egr;. The exact inverse of AO can be computed by interpolation from the inverses of A&egr;, for suitable values of &egr;. If AO has upper bandwidth k+1, then AO can be inverted exactly in 6 long n + log(k+1) + 7 parallel steps, with 5n(k+1)/2 processors. A comparable algorithm is presented for Toeplitz matrices with general band structure.
The definitions of band structure given in this paper are not clear. On p. 268-269, the condition ak,1 :9I O should probably be changed to a a1,k+1 :9I O. On p. 275, the condition ak1 :9I O should probably be changed to ak+1.1 :9I O.
