Parallel polynomial computations by recursive processes
Dario A. Bini, Victor Ya. Pan · 1990
Let lg stand for log2, lg(0)n = n, lg(h)n = lg lg(h-1)n, h = 1, …, lg*n, lg*n = min{h,lg(h)n ≤ 1}. Given natural N, h, 1 ≤ h ≤ lg*N, and polynomial p(x), p(O) ≠ O, we compute r(x) = p(x)-1 mod xN for the cost OA(t, P), t = h lg N, P = (N/h)lg(h)N, under the PRAM arithmetic model, that is, we need O(t) steps and O(P) processors (with t and P as above), provided DFT(m) costs OA(lg m, m). For h = lg* N, the cost bounds turn into OA(lg N lg*N, N/lg*N). The results improve [G] and apply to various related computations [BP].