Sequential and parallel complexity of approximate evaluation of polynomial zeros
From MaRDI portal
(Redirected from Publication:1097004)
arithmetic and Boolean complexitycomplex polynomial zerospractical implementationsequential and parallel algorithmsupper bounds
Software, source code, etc. for problems pertaining to functions of a complex variable (30-04) 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) Analysis of algorithms and problem complexity (68Q25)
By modification and extension of ideas which are, among others, originally due to Turan, Lehmer and Weyl, the author develops sequential and parallel algorithms for the approximation of complex polynomial zeros and establishes new upper bounds on the respective arithmetic and Boolean complexity of these methods. Questions of practical implementation are discussed as well as applications to the solution of related problems.
Recommendations
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- On the Complexity of Polynomial Zeros
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- Algebraic complexity of computing polynomial zeros
- On the worst-case arithmetic complexity of approximating zeros of polynomials
Cites work
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- A Machine Method for Solving Polynomial Equations
- A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
- Algebraic complexity of computing polynomial zeros
- Complexity of parallel matrix computations
- Computational complexity. On the geometry of polynomials and a theory of cost. I
- Evaluating Polynomials at Fixed Sets of Points
- Fast algorithms for the characteristic polynomial
- Fast parallel matrix and GCD computations
- scientific article; zbMATH DE number 3841223 (Why is no real title available?)
- scientific article; zbMATH DE number 3856407 (Why is no real title available?)
- scientific article; zbMATH DE number 3865403 (Why is no real title available?)
- scientific article; zbMATH DE number 3734057 (Why is no real title available?)
- scientific article; zbMATH DE number 3750284 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3471577 (Why is no real title available?)
- scientific article; zbMATH DE number 3489473 (Why is no real title available?)
- scientific article; zbMATH DE number 3566175 (Why is no real title available?)
- scientific article; zbMATH DE number 3624682 (Why is no real title available?)
- scientific article; zbMATH DE number 3628385 (Why is no real title available?)
- scientific article; zbMATH DE number 3992807 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3279131 (Why is no real title available?)
- scientific article; zbMATH DE number 3321949 (Why is no real title available?)
- scientific article; zbMATH DE number 3383473 (Why is no real title available?)
- scientific article; zbMATH DE number 3055967 (Why is no real title available?)
- On the efficiency of algorithms of analysis
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Parallel computational geometry
- Polynomial division and its computational complexity
- Power Sum Method and the Approximative Solution of Algebraic Equations
- Quasi-gcd computations
- The fundamental theorem of algebra and complexity theory
Cited in
(27)- Algebraic complexity of computing polynomial zeros
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Parallel evaluation of the determinant and of the inverse of a matrix
- On the evaluation of the eigenvalues of a banded Toeplitz block matrix
- Improving the solution of the symmetric eigenvalue problem and an extension
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Optimum placement of guards
- Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- List decoding of number field codes
- Symbolic differentiation of factorized polynomials with repeated roots and the identification of their loci
- On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials
- Efficient Algorithms for the Evaluation of the Eigenvalues of (Block) Banded Toeplitz Matrices
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- scientific article; zbMATH DE number 57956 (Why is no real title available?)
- scientific article; zbMATH DE number 69493 (Why is no real title available?)
- On the Complexity of Polynomial Zeros
- The actual complexity of parallel evaluation of low degree polynomials
- Calculating polynomial zeros on a local memory parallel computer
- Solving matrix polynomial equations arising in queueing problems
- A general approach to isolating roots of a bitstream polynomial
- A new fast root-finder for black box polynomials
- Numerical computation of polynomial zeros by means of Aberth's method
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
This page was built for publication: Sequential and parallel complexity of approximate evaluation of polynomial zeros
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097004)
