Abstract :
The authors compute the first N coefficients of the reciprocal r(x) of a given polynomial p(x), (r(x)p(x)=1 mod xN, 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(0) N=N, log(h) N=log2log(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 xN of the m-th root, p(x)1m/, 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
Keywords :
computational complexity; parallel algorithms; polynomials; PRAM arithmetic models; complexity estimates; evaluation modulo; parallel algebraic computations; parallel polynomial division; polynomial; reciprocal; recursive processes; stream contraction; supereffective slowdown; triangular Toeplitz matrix; Arithmetic; Concurrent computing; Costs; Educational institutions; Mathematical model; Mathematics; Phase change random access memory; Polynomials; Processor scheduling; State estimation;