Publications [#236913] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Pan, V; Reif, J, SOME POLYNOMIAL AND TOEPLITZ MATRIX COMPUTATIONS., Annual Symposium on Foundations of Computer Science Proceedings (January, 1987), pp. 173-184 [doi]
   (last updated on 2026/01/14)

   Abstract:
   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.