Algebraic complexity of computing polynomial zeros

DOI10.1016/0898-1221(87)90137-4zbMath0632.65052OpenAlexW2065482768MaRDI QIDQ1095599

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)90137-4

zbMATH Keywords

zeros of polynomialscost operationsGraeffe-Runge methodsequential and parallel computational complexityTuran methodupper estimates of relative errors

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) Parallel numerical computation (65Y05)

Related Items

Polynomial division and its computational complexity, Sequential and parallel complexity of approximate evaluation of polynomial zeros, Complexity of parallel matrix computations, Effective asymptotics of linear recurrences with rational coefficients, Distances from differences of roots of polynomials to the nearest integers, A technology for reverse-engineering a combinatorial problem from a rational generating function, Solving matrix polynomial equations arising in queueing problems, On Multiple Eigenvalues of a Matrix Dependent on a Parameter, Computational aspects of the general Rodrigues problem

Cites Work

• On computing the determinant in small parallel time using a small number of processors
• How to multiply matrices faster
• Fast algorithms for the characteristic polynomial
• On application of some recent techniques of the design of algebraic algorithms to the sequential and parallel evaluation of the roots of a polynomial and to some other numerical problems
• Polynomial division and its computational complexity
• Sequential and parallel complexity of approximate evaluation of polynomial zeros
• Complexity of parallel matrix computations
• The bit-operation complexity of matrix multiplication and of all pair shortest path problem
• The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• Inverses of Vandermonde Matrices
• A Machine Method for Solving Polynomial Equations
• Parallel Solution of Certain Toeplitz Linear Systems
• On the efficiency of algorithms of analysis
• 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
• An Efficient Formula for Linear Recurrences
• 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