Algebraic complexity of computing polynomial zeros (Q1095599)

Let the operations \((+,-,*,\div,root\) evaluation) be unit cost operations and each processor performs at most one unit cost operation in each step. Then the cost of the exact evaluation of the zeros \(\lambda_ 1,...,\lambda_ n\) of an n-th degree general univariate polynomial \(P_ n(\lambda)\) with real or complex coefficients is infinite unless \(n<5\). The author obtains upper estimates of relative errors \(\epsilon\) for sequential and parallel computational complexity of the problem. The methods used are Graeffe-Runge's, Turan's and the author's own. The paper is self-contained as in four appendices there is all the necessary information on the methods used.