Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
From MaRDI portal
The author develops two nearly optimal effective algorithms to approximate all roots of a univariate ploynomial. Two algorithms are combined in a single recursive process which leads to computation of the complete numerical factorization of a polynomial into the product of linear factors and further to the approximation of the roots. Both algorithms allow processor efficient acceleration to achieve the solution in polylogarithmic parallel time.
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
Cites work
- A bibliography on roots of polynomials
- A fast and stable algorithm for splitting polynomials
- A Newton-Raphson method for moving-average spectral factorization using the Euclid algorithm
- A Numerical Method for Locating the Zeros of an Analytic Function
- A quadtree algorithm for template matching on a pyramid computer
- A supplementary bibliography: on roots of polynomials
- An efficient algorithm for the complex roots problem
- An Inequality About Factors of Polynomials
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Certified approximate univariate GCDs
- Computation of approximate polynomial GCDs and an extension
- Computations with infinite Toeplitz matrices and polynomials
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
- Factorization of the Covariance Generating Function of a Pure Moving Average Process
- Fast multiplication of large numbers
- Fast solution of toeplitz systems of equations and computation of Padé approximants
- scientific article; zbMATH DE number 1682655 (Why is no real title available?)
- scientific article; zbMATH DE number 1003258 (Why is no real title available?)
- scientific article; zbMATH DE number 3839766 (Why is no real title available?)
- scientific article; zbMATH DE number 3856407 (Why is no real title available?)
- scientific article; zbMATH DE number 3179103 (Why is no real title available?)
- scientific article; zbMATH DE number 46317 (Why is no real title available?)
- scientific article; zbMATH DE number 3489473 (Why is no real title available?)
- scientific article; zbMATH DE number 3613366 (Why is no real title available?)
- scientific article; zbMATH DE number 1263253 (Why is no real title available?)
- scientific article; zbMATH DE number 653122 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- scientific article; zbMATH DE number 1096865 (Why is no real title available?)
- scientific article; zbMATH DE number 1744839 (Why is no real title available?)
- scientific article; zbMATH DE number 953021 (Why is no real title available?)
- scientific article; zbMATH DE number 3290249 (Why is no real title available?)
- scientific article; zbMATH DE number 3383473 (Why is no real title available?)
- scientific article; zbMATH DE number 3039704 (Why is no real title available?)
- Multivariate polynomials, duality, and structured matrices
- On the efficiency of algorithms of analysis
- On the worst-case arithmetic complexity of approximating zeros of 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]}\)
- Polynomial Root-Finding Algorithms and Branched Covers
- Quasi-gcd computations
- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- Solving a Polynomial Equation: Some History and Recent Progress
- Specified precision polynomial root isolation is in NC
- Stability of Methods for Solving Toeplitz Systems of Equations
- Tangent Graeffe iteration
- The Euclid algorithm and the fast computation of cross-covariance and autocovariance sequences
- The fundamental theorem of algebra and complexity theory
- The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
- The Simultaneous Newton Improvement of a Complete Set of Approximate Factors of a Polynomial
- Variations on computing reciprocals of power series
Cited in
(86)- Dynamic ham-sandwich cuts in the plane
- On the asymptotic and practical complexity of solving bivariate systems over the reals
- Polynomial root computation by means of the LR algorithm
- Normal factorisation of polynomials and computational issues.
- Inverse power and Durand-Kerner iterations for univariate polynomial root-finding
- A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
- Univariate real root isolation in an extension field and applications
- Improved algorithms for computing determinants and resultants
- A nearly optimal algorithm to decompose binary forms
- Multilinear polynomial systems: root isolation and bit complexity
- Infinitely many quasi-coincidence point solutions of multivariate polynomial problems
- Real root polynomials and real root preserving transformations
- Accelerated subdivision for clustering roots of polynomials given by evaluation oracles
- Faster numerical univariate polynomial root-finding by means of subdivision iterations
- Bounds for polynomials on algebraic numbers and application to curve topology
- Efficient sampling in spectrahedra and volume approximation
- Old and new nearly optimal polynomial root-finders
- How to count the number of zeros that a polynomial has on the unit circle?
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- On the complexity of computing with planar algebraic curves
- The polynomial pivots as initial values for a new root-finding iterative method
- 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
- Schur aggregation for linear systems and determinants
- The amended DSeSC power method for polynomial root-finding
- Finding Hamming weights without looking at truth tables
- Positive root isolation for poly-powers by exclusion and differentiation
- Symmetry detection of rational space curves from their curvature and torsion
- On the complexity of the Descartes method when using approximate arithmetic
- Root-squaring with DPR1 matrices
- On the complexity of real root isolation using continued fractions
- Near optimal subdivision algorithms for real root isolation
- On application of the ray-shooting method for LQR via static-output-feedback
- Bounded-degree factors of lacunary multivariate polynomials
- A symbolic-numerical algorithm for isolating real roots of certain radical expressions
- \texttt{PTOPO}: computing the geometry and the topology of parametric curves
- Numerical factorization of polynomials via a fast transversal filter
- Univariate polynomial root-finding by arming with constraints
- Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
- Solving bivariate systems using rational univariate representations
- First study for ramp secret sharing schemes through greatest common divisor of polynomials
- scientific article; zbMATH DE number 5356112 (Why is no real title available?)
- Improved bounds for the CF algorithm
- Efficient polynomial root-refiners: a survey and new record efficiency estimates
- A fitting algorithm for real coefficient polynomial rooting
- New Resultant Inequalities and Complex Polynomial Factorization
- Splitting full matrix algebras over algebraic number fields.
- scientific article; zbMATH DE number 1793930 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 1859220 (Why is no real title available?)
- Separating linear forms and rational univariate representations of bivariate systems
- A generic position based method for real root isolation of zero-dimensional polynomial systems
- A solution to certain polynomial equations with applications to nonlinear fitting
- Root refinement for real polynomials using quadratic interval refinement
- Computing real roots of real polynomials
- New Practical Advances in Polynomial Root Clustering
- The Weierstrass–Durand–Kerner root finder is not generally convergent
- 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
- Computing algebraic numbers of bounded height
- New progress in real and complex polynomial root-finding
- On the efficient global dynamics of Newton’s method for complex polynomials
- The Complexity of Diagonalization
- Validated Root Enclosures for Interval Polynomials with Multiplicities
- Fast evaluation and root finding for polynomials with floating-point coefficients
- A deterministic algorithm for isolating real roots of a real polynomial
- 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
- Complexity of a root clustering algorithm for holomorphic functions
- Algebraic winding numbers
- Fast evaluation and root finding for polynomials with floating-point coefficients
- Root-finding by expansion with independent constraints
- Novel range functions via Taylor expansions and recursive Lagrange interpolation with application to real root isolation
- Computing the non-properness set of real polynomial maps in the plane
- Global convergence of Hessenberg shifted QR. I: Exact arithmetic
- Global convergence of Hessenberg shifted QR. II: Finite arithmetic
- Factoring sparse polynomials fast
- Structured ramp secret sharing schemata over rings of real polynomials
- Plane curve germs and contact factorization
- Coefficient-free adaptations of polynomial root-finders
- Root radii and subdivision for polynomial root-finding
- Nearly optimal refinement of real roots of a univariate polynomial
- A randomized approximation algorithm for the minimal-norm static-output-feedback problem
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)
