On the parallel arithmetic complexity of the root-finding problem

Abstract

It is shown by means of a constructive procedure, that the real and distinct zeros of a polynomial f(x) of degree n can be computed in 0(nlog₂ n) parallel steps using at most 0(n) processors.

Keywords:

• Parallel complexity
• root-finding
• Hankel matrices

C.R. Categories:

• 5.14

tThe research was supported by Air borce Office of Scientific Research under grant AFOSR 083-0334.

tThe research was supported by Air borce Office of Scientific Research under grant AFOSR 083-0334.

Notes

tThe research was supported by Air borce Office of Scientific Research under grant AFOSR 083-0334.