Improved Parallel Polynomial Division and Its Extensions
Title | Improved Parallel Polynomial Division and Its Extensions |
Publication Type | Technical Report |
Year of Publication | 1992 |
Authors | Bini, D., & Pan V. |
Other Numbers | 756 |
Abstract | We 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) not equal to 0), by using, under the PRAM arithmetic models, O(h log N) time-steps and O((N/h)(1+2^{-h}log^{(h)}N)), processors, for any h, h=1, 2,... log^*N, provided that O(log m) steps and m processors suffice to perform DFT on m points and that log^{(0), N=N, log^{(h)}N = log_2 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 times N triangular Toeplitz matrix. This improves the known estimates of Reif-Tate and Georgiev. We also show how to extend our techniques to parallel implementation of other recursive processes, such as the evaluation modulo x^N of the m^th root, p(x)^{1/m, of p(x) (for any fixed natural m), for which we need 0(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 we combine with a technique of stream contraction. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-92-051.pdf |
Bibliographic Notes | ICSI Technical Report TR-92-051 |
Abbreviated Authors | D. Bini and V. Pan |
ICSI Publication Type | Technical Report |