PARALLEL COMPUTATION OF POLYNOMIAL GCD AND SOME RELATED PARALLEL COMPUTATIONS OVER ABSTRACT FIELDS

Several fundamental problems of computations with polynomials and stru ctured matrices are well known for their resistance to effective paral lel solution. This includes computing the gcd, the 1cm, and the result ant of two polynomials, as well as any selected entry of either the ex tended Euclidean scheme for these polynomials or the Pade approximatio n table associated to a fixed power series, the solution of the Berlek amp-Massey problem of recovering the n coefficients of a linear recurr ence sequence from its first 2n terms, the solution of a Toeplitz line ar system of equations, computing the ranks and the null-spaces of Toe plitz matrices, and several other computations with Toeplitz, Hankel, Vandermonde, and Cauchy (generalized Hilbert) matrices and with matric es having similar structures. Our algorithms enable us to reach new re cord estimates for randomized parallel arithmetic complexity of all th ese computations (over any field of constants), that is, O((log n)(k)) time and O((n(2) log log n)/(log n)(h-g)) arithmetic processors, wher e n is the input size, g varies from 1 to 2, and h varies from 2 to 4, depending on the computational problem and on the fixed field of cons tants. The estimates include the cost of correctness tests for the sol ution. The results have further applications to many related computati ons over abstract fields and rely on some new techniques (in particula r, on recursive Padi approximation and regularization of Fade approxim ation via randomization), which might be of some independent technical interest. In particular, an auxiliary algorithm computes (over any fi eld) the coefficients of a polynomial from the power sums of its zeros , which is an important problem of algebraic coding.