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

DOI10.1006/JSCO.2002.0531zbMATH Open1004.65061OpenAlexW2144619406MaRDI QIDQ697493FDOQ697493

Authors: Victor Y. Pan 

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

Recommendations

• Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
• scientific article; zbMATH DE number 1859220
• Real arithmetic versions of simultaneous iteration methods for polynomial root finding
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• scientific article; zbMATH DE number 1793930

zbMATH Keywords

convergence accelerationfactorizationrootunivariate polynomialsnearly 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) Real polynomials: location of zeros (26C10) Numerical computation of solutions to single equations (65H05)

Cites Work

• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Title not available (Why is that?)
• Fast multiplication of large numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quasi-gcd computations
• A bibliography on roots of polynomials
• Certified approximate univariate GCDs
• Computation of approximate polynomial GCDs and an extension
• Multivariate polynomials, duality, and structured matrices
• Title not available (Why is that?)
• Stability of Methods for Solving Toeplitz Systems of Equations
• The fundamental theorem of algebra and complexity theory
• A Numerical Method for Locating the Zeros of an Analytic Function
• Factorization of the Covariance Generating Function of a Pure Moving Average Process
• A supplementary bibliography: on roots of polynomials
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Title not available (Why is that?)
• The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
• Solving a Polynomial Equation: Some History and Recent Progress
• Tangent Graeffe iteration
• Title not available (Why is that?)
• Title not available (Why is that?)
• Specified precision polynomial root isolation is in NC
• Computations with infinite Toeplitz matrices and polynomials
• On the efficiency of algorithms of analysis
• A fast and stable algorithm for splitting polynomials
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• Title not available (Why is that?)
• A Newton-Raphson method for moving-average spectral factorization using the Euclid algorithm
• The Euclid algorithm and the fast computation of cross-covariance and autocovariance sequences
• Polynomial Root-Finding Algorithms and Branched Covers
• Title not available (Why is that?)
• Sequential and parallel complexity of approximate evaluation of polynomial zeros
• A quadtree algorithm for template matching on a pyramid computer
• An efficient algorithm for the complex roots problem
• An Inequality About Factors of Polynomials
• Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
• Variations on computing reciprocals of power series
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Simultaneous Newton Improvement of a Complete Set of Approximate Factors of a Polynomial

Cited In (79)

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

Uses Software

• na20

This page was built for publication: Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q697493)