Improved parallel polynomial division and its extensions

The authors compute the first N coefficients of the reciprocal r(x) of a given polynomial p(x), (r(x)p(x)=1 mod x^N, p(0)≠0), by using, under the PRAM arithmetic models, O(h log N) time-steps and O((N/h)(1+2^-hlog^(h) N)) processors, for any h, h=1,2, . . .,log^* N, provided that O(logm) steps and m processors suffice to perform DFT on m points and that log⁽⁰⁾ N=N, log^(h) N=log₂log^(h-1)N, h=1, . . .,log^*N, log^*N=max{h:log^(h)N>0}. The same complexity estimates apply to some other computations, such as the division with a remainder of two polynomials of degrees O(N) and the inversion of an N×N triangular Toeplitz matrix. They also show how to extend the techniques to parallel implementation of other recursive processes, such as the evaluation modulo x^N of the m-th root, p(x)¹m/, of p(x) (for any fixed natural m), for which we need O(log N log log N) time-steps and O(N/log log N) processors. The paper demonstrates some new techniques of supereffective slowdown of parallel algebraic computations, which they combine with a technique of stream contraction