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

摘要

Several fundamental problems of computations with polynomials and structured matrices are well known for their resistance to effective parallel solution. This includes computing the gcd, the 1cm, and the resultant of two polynomials, as well as any selected entry of either the extended Euclidean scheme for these polynomials or the Pade approximation table associated to a fixed power series, the solution of the Berlekamp-Massey problem of recovering the n coefficients of a linear recurrence sequence from its first 2n terms, the solution of a Toeplitz linear system of equations, computing the ranks and the null-spaces of Toeplitz matrices, and several other computations with Toeplitz, Hankel, Vandermonde, and Cauchy (generalized Hilbert) matrices and with matrices having similar structures. Our algorithms enable us to reach new record estimates for randomized parallel arithmetic complexity of all these 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, where 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 constants. The estimates include the cost of correctness tests for the solution. The results have further applications to many related computations over abstract fields and rely on some new techniques (in particular, on recursive Padi approximation and regularization of Fade approximation via randomization), which might be of some independent technical interest. In particular, an auxiliary algorithm computes (over any field) the coefficients of a polynomial from the power sums of its zeros, which is an important problem of algebraic coding. [References: 92]