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/sup N/, p(0) not=0), by using, under the PRAM arithmetic models, O(h log N) time-steps and O((N/h)(1+2/sup -h/log/sup (h)/ N)) processors, for any h, h=1, 2, .. ., log/sup */ N, provided that O(logm) steps and m processors suffice to perform DFT on m points and that log/sup (0)/ N=N, log/sup (h)/ N=log/sub 2/log/sup (h-1)/N, h=1, .. ., log/sup */N, log/sup */N=max(h: log/sup (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/sup N/ of the m-th root, p(x)/sup 1/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. >

Authors

• Dario Bini
• Victor Y. Pan

Keywords

• Polynomials
• Concurrent computing
• Arithmetic
• Phase change random access memory
• Mathematics
• Mathematical model
• Educational institutions
• Processor scheduling
• State estimation
• Costs
• Polynomial Division
• Square Root
• Parallelization
• Components Of Vector
• Newton Method
• Polynomial Of Degree
• Discrete Fourier Transform
• Power Series
• Linear Algebra
• Complex Steps
• Parallel Algorithm
• Roots Of Polynomial
• Root Of Unity
• Stage Cost
• Number Of Processors
• Inverse Discrete Fourier Transform
• Recursive Step