Algebraic complexity of computing polynomial zeros (Q1095599)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algebraic complexity of computing polynomial zeros |
scientific article |
Statements
Algebraic complexity of computing polynomial zeros (English)
0 references
1987
0 references
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.
0 references
zeros of polynomials
0 references
Graeffe-Runge method
0 references
Turan method
0 references
cost operations
0 references
upper estimates of relative errors
0 references
sequential and parallel computational complexity
0 references
0 references
0 references
0 references
0 references