Parallel algorithms for Toeplitz matrix operations

Algorithms for multiplication and inversion of ToepIitz matrices are presented that take advantage of the special structure of ToepIitz forms and the parallelism offered by concurrent processors. Multiplication of two general n×n Toeplitz matrices is defined on an array of 2n-1 processing elements. A block size may be chosen to effect an appropriate compromise between the number of processors and the amount of overhead due to interprocessor data communication. The parallel algorithm For inversion is based on a method of Justice For inverting a positive definite Toeplitz matrix. The computation, distributed over an array of n processing elements, generates a sequence of orthogonal polynomials from which the elements of the Toeplitz inverse are computed with O(n) concurrency.