IMPROVED PARALLEL POLYNOMIAL DIVISION

The authors compute the first N coefficients of the reciprocal r(x), r (x)p(x) = 1 mod x(N) (given a natural N and a polynomial p(x)), (p(0) not-equal 0), by using O(h log N) arithmetic steps and O((N/h)(1 + 2-h log(h) N)) processors, for any h, h = 1, 2,...,log N, under the PRAM arithmetic models, provided that O(log m) steps and m processors suff ice to perform discrete Fourier transforms on m points and that log(0) N = N, log(h) N = log2 log(h-1) N, h = 1,...,log N, log* N = max{h : log(h) N > 0}. The same estimates apply to some other computations, s uch as the division with a remainder of two polynomials of degrees O(N ) and the inversion of an N x N triangular Toeplitz matrix. This impro ves the known estimates of Reif-Tate and Georgiev. The presented techn iques are extended to parallel implementation of other recursive proce sses, such as the evaluation modulo x(N) of the mth root p(x) 1/m of p (x) (for any fixed natural m), for which we need 0(log N log log N) ti mesteps and O(N/log log N) processors. The paper demonstrates some new techniques of supereffective slowdown of parallel algebraic computati ons combined with the technique of stream contraction.