SOME POLYNOMIAL AND TOEPLITZ MATRIX COMPUTATIONS.

The authors show that for n processors, O(n**2(log**2n plus log b)) arithmetic operations or O(n(log**2n plus log b)) parallel steps suffice in order to approximate with absolute error less than equivalent to 2**m**-**b all the complex zeros of an nth degree polynomial p(x) whose coefficients have moduli less than equivalent to 2**m. They also compute the inverse, determinant, and characteristic polynomial of an n multiplied by n Toeplitz matrix T using O(log**2n parallel arithmetic steps, n**2 processors.

Duke Scholars

Author John H. Reif Computer Science