Specified precision polynomial root isolation is in NC
From MaRDI portal
Publication:1329153
DOI10.1016/S0022-0000(05)80061-3zbMath0806.68054OpenAlexW4210565352MaRDI QIDQ1329153
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
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
