Sequential and parallel complexity of approximate evaluation of polynomial zeros

DOI10.1016/0898-1221(87)90186-6zbMath0634.65036OpenAlexW2111468049MaRDI QIDQ1097004

Pan, Victor Y.

Publication date: 1987

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(87)90186-6

zbMATH Keywords

upper boundssequential and parallel algorithmsarithmetic and Boolean complexitycomplex polynomial zerospractical implementation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05) Software, source code, etc. for problems pertaining to functions of a complex variable (30-04)

Related Items

Optimum placement of guards, Algebraic complexity of computing polynomial zeros, Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant, Parallel evaluation of the determinant and of the inverse of a matrix, Optimal and nearly optimal algorithms for approximating polynomial zeros, A general approach to isolating roots of a bitstream polynomial, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., On the evaluation of the eigenvalues of a banded Toeplitz block matrix, Numerical computation of polynomial zeros by means of Aberth's method, List decoding of number field codes, Improving the solution of the symmetric eigenvalue problem and an extension, Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding, Solving matrix polynomial equations arising in queueing problems, Symbolic differentiation of factorized polynomials with repeated roots and the identification of their loci, Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)], Efficient Algorithms for the Evaluation of the Eigenvalues of (Block) Banded Toeplitz Matrices, Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros

Cites Work

• Fast algorithms for the characteristic polynomial
• Quasi-gcd computations
• Polynomial division and its computational complexity
• Algebraic complexity of computing polynomial zeros
• Complexity of parallel matrix computations
• Parallel computational geometry
• A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• A Machine Method for Solving Polynomial Equations
• On the efficiency of algorithms of analysis
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Computational complexity. On the geometry of polynomials and a theory of cost. I
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
• The fundamental theorem of algebra and complexity theory
• Power Sum Method and the Approximative Solution of Algebraic Equations
• Evaluating Polynomials at Fixed Sets of Points
• Fast parallel matrix and GCD computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item