Fast and efficient algorithms for sequential and parallel evaluation of polynomial zeros and of matrix polynomials

We evaluate all the real and complex zeros λ1,...,λn of an n-th degree univariate polynomial with the relative precision 1/2nc for a given positive constant c. If for all g,h, log |λg/λh-1| ≥ 1/2O(n) unless λg = λh, then we need O(n3log2n) arithmetic operations or O(n2log n) steps, n log n processors. O(n2log n) operations or O(n log n) parallel steps, n processors suffice if either all the zeros are real or for all g,h either |λg| = |λh| or 2O(n) ≥ (|λg/λh| - 1)| ≥ 1/2O(n). If all the zeros are either multiple or form complex conjugate pairs or if their moduli pairwise differ by the factors at least 1+1/nO(1), then O(n log2n) operations or O(log2n) steps, n processors suffice. Replacing 1+1/nO(1) above by 1+1/nO(loghn) for a positive h only requires to increase the time-complexity bounds by the factor loghn. Some of the presented algorithms extend Graeffe´s method, other algorithms use the power sum techniques and the companion matrix computation; the latter ones are related to Bernoulli´s and Leverrier´s methods and to the power method and are extended in this paper to the evaluation of a matrix polynomial u(X) of degree N, (X is an n×n matrix), using O(N log N+n2.496) arithmetic operations. Such evaluation can be performed using O(log N+log2n) parallel steps, Nn+n3.496 processors or alternatively O(log2(nN)) steps, N/log N+n3.496 processors over arbitrary field of constants. Over rational constants, for almost all matrices X the number of processors can be reduced to Nn+n2.933 or to N/log N+n2.933, respectively; the bounds can be further reduced to O(log N+log2n)steps, N+n2.933 processors if u(X) is to be computed with a fixed arbitrarily high precision rather than exactly. For integer and well-conditioned matrices, the exponent 2.933 above can be decreased to 2.496. The results substantially improve the previously known upper estimates for the com- plexity of sequential and parallel evaluation of polynomial zeros and of matrix polynomials.