Publication Details
Title: Improved Parallel Computations with Toeplitz-like and Hankel-like Matrices
Author: D. Bini and V. Pan
Group: ICSI Technical Reports
Date: August 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-052.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-052
Bibliographic Reference:
D. Bini and V. Pan. Improved Parallel Computations with Toeplitz-like and Hankel-like Matrices. ICSI Technical Report TR-92-052, August 1992
Author: D. Bini and V. Pan
Group: ICSI Technical Reports
Date: August 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-052.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-052
Bibliographic Reference:
D. Bini and V. Pan. Improved Parallel Computations with Toeplitz-like and Hankel-like Matrices. ICSI Technical Report TR-92-052, August 1992