Specified precision polynomial root isolation is in NC

DOI10.1016/S0022-0000(05)80061-3zbMath0806.68054OpenAlexW4210565352MaRDI QIDQ1329153

C. Andrew Neff

Publication date: 9 February 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80061-3

zbMATH Keywords

polynomial root finding

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Related Items (11)

Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant ⋮ Optimal and nearly optimal algorithms for approximating polynomial zeros ⋮ On parallel complexity of analytic functions ⋮ Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations ⋮ Advice Coins for Classical and Quantum Computation ⋮ Root finding with threshold circuits ⋮ The Sturm method in the complex case ⋮ Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding ⋮ A lower bound for the shortest path problem ⋮ Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)] ⋮ Bit-complexity of solving systems of linear evolutionary partial differential equations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple algorithms for approximating all roots of a polynomial with real roots
• On computing the determinant in small parallel time using a small number of processors
• Fast parallel absolute irreducibility testing
• Complexity of parallel matrix computations
• Parallel evaluation of the determinant and of the inverse of a matrix
• Effective Noether irreducibility forms and applications
• An inequality for the discriminant of a polynomial
• Parallel Algorithms for Algebraic Problems
• On the cost of approximating all roots of a complex polynomial
• Representations and Parallel Computations for Rational Functions
• A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
• Fast Parallel Matrix Inversion Algorithms
• On the Problem of Runs
• Fast parallel matrix and GCD computations
• Polynomial Remainder Sequences and Determinants
• Subresultants and Reduced Polynomial Remainder Sequences

This page was built for publication: Specified precision polynomial root isolation is in NC