Improved Parallel Computations with Toeplitz-like and Hankel-like Matrices

TitleImproved Parallel Computations with Toeplitz-like and Hankel-like Matrices
Publication TypeTechnical Report
Year of Publication1992
AuthorsBini, D., & Pan V.
Other Numbers757

The known parallel algorithms for computations with general Toeplitz, Hankel, Toeplitz-like, and Hankel-like matrices are inherently sequential. We develop some new techniques in order to devise fast parallel algorithms for such computations, including the evaluation of Krylov sequences for such matrices, traces of their power sums, characteristic polynomials and generalized inverses. This has further extensions to computing the solution or a least-squares solution to a linear system of equations with such a matrix and to several polynomial evaluations (such as computing gcd, lcm, Pade approximation and extended Euclidean scheme for two polynomials), as well as to computing the minimum span of a linear recurrence sequence. The algorithms can be applied over any field of constants, with the resulting advantages of using modular arithmetic. The algorithms consist of simple computational blocks (mostly reduced to fast Fourier transforms, FFT's) and have potential practical value. We also develop the techniques for extending all our results to the case of matrices representable as the sums of Toeplitz-like and Hankel-like matrices and in addition show some more minor innovations, such as an improvement of the transition to the solution to a Toeplitz linear system Tx=b from two computed columns of T^-1.

Bibliographic Notes

ICSI Technical Report TR-92-052

Abbreviated Authors

D. Bini and V. Pan

ICSI Publication Type

Technical Report