IMPROVED PARALLEL COMPUTATIONS WITH TOEPLITZ-LIKE AND HANKEL-LIKE MATRICES

The known fast algorithms for computations with general Toeplitz, Hank el, Toeplitz-like, and Hankel-like matrices are inherently sequential. We develop some new techniques in order to devise fast parallel algor ithms for such computations, including the evaluation of Krylov sequen ces for such matrices, traces of their power sums, characteristic poly nomials, and generalized inverses. This has further extensions to comp uting the solution or a least-squares solution to a linear system of e quations with such a matrix and to several polynomial computations (su ch as computing the gcd, lcm, Pade approximation, and extended Euclide an scheme for two polynomials), as well as to computing the minimum sp an of a linear recurrence sequence. The algorithms can be applied over any field of constants, with the resulting advantages of using modula r arithmetic. The algorithms consist of simple computational blocks (m ostly reduced to fast Fourier transforms) and have potential practical value. We also develop the techniques for extending all our results t o the case of matrices representable as the sums of Toeplitz-like and Hankel-like matrices.