Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding

DOI10.1006/jsco.2002.0531zbMath1004.65061OpenAlexW2144619406MaRDI QIDQ697493

Publication date: 17 September 2002

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jsco.2002.0531

zbMATH Keywords

convergence acceleration factorization univariate polynomials root nearly optimal effective algorithms

Mathematics Subject Classification ID

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) Real polynomials: location of zeros (26C10)

Related Items

Root radii and subdivision for polynomial root-finding, Near optimal subdivision algorithms for real root isolation, On application of the ray-shooting method for LQR via static-output-feedback, Schur aggregation for linear systems and determinants, Efficient sampling in spectrahedra and volume approximation, Bounded-degree factors of lacunary multivariate polynomials, The Weierstrass–Durand–Kerner root finder is not generally convergent, Solving bivariate systems using rational univariate representations, The amended DSeSC power method for polynomial root-finding, A solution to certain polynomial equations with applications to nonlinear fitting, Finding Hamming weights without looking at truth tables, A symbolic-numerical algorithm for isolating real roots of certain radical expressions, Positive root isolation for poly-powers by exclusion and differentiation, Symmetry detection of rational space curves from their curvature and torsion, A deterministic algorithm for isolating real roots of a real polynomial, Improved bounds for the CF algorithm, A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration, \texttt{PTOPO}: computing the geometry and the topology of parametric curves, The Complexity of Diagonalization, Validated Root Enclosures for Interval Polynomials with Multiplicities, Fast evaluation and root finding for polynomials with floating-point coefficients, Newton's method in practice. II: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees, On Isolating Roots in a Multiple Field Extension, Matrix computations and polynomial root-finding with preprocessing, Nearly optimal refinement of real roots of a univariate polynomial, Efficient polynomial root-refiners: a survey and new record efficiency estimates, A randomized approximation algorithm for the minimal-norm static-output-feedback problem, A fitting algorithm for real coefficient polynomial rooting, Geometry of polynomials and root-finding via path-lifting, Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation, Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers, Splitting full matrix algebras over algebraic number fields., On the complexity of the Descartes method when using approximate arithmetic, How to count the number of zeros that a polynomial has on the unit circle?, Root-squaring with DPR1 matrices, Inverse power and Durand-Kerner iterations for univariate polynomial root-finding, Separating linear forms and rational univariate representations of bivariate systems, A generic position based method for real root isolation of zero-dimensional polynomial systems, Root-finding by expansion with independent constraints, Root refinement for real polynomials using quadratic interval refinement, First Study for Ramp Secret Sharing Schemes Through Greatest Common Divisor of Polynomials, Computing real roots of real polynomials, A nearly optimal algorithm to decompose binary forms, Multilinear polynomial systems: root isolation and bit complexity, On the complexity of real root isolation using continued fractions, From approximate factorization to root isolation with application to cylindrical algebraic decomposition, Univariate real root isolation in an extension field and applications, On the complexity of computing with planar algebraic curves, On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers, Numerical computation of the genus of an irreducible curve within an algebraic set, Improved algorithms for computing determinants and resultants, New progress in real and complex polynomial root-finding, Infinitely many quasi-coincidence point solutions of multivariate polynomial problems, Real root polynomials and real root preserving transformations, Dynamic ham-sandwich cuts in the plane, On the asymptotic and practical complexity of solving bivariate systems over the reals, Computing algebraic numbers of bounded height, The polynomial pivots as initial values for a new root-finding iterative method, New Practical Advances in Polynomial Root Clustering, Accelerated subdivision for clustering roots of polynomials given by evaluation oracles, On the efficient global dynamics of Newton’s method for complex polynomials, Coefficient-free adaptations of polynomial root-finders, Bounds for polynomials on algebraic numbers and application to curve topology, Accelerated approximation of the complex roots and factors of a univariate polynomial, Newton's method in practice: finding all roots of polynomials of degree one million efficiently

Uses Software

na20

Cites Work