Efficient polynomial root-refiners: a survey and new record efficiency estimates

DOI10.1016/J.CAMWA.2011.11.015zbMATH Open1238.65044OpenAlexW2001830571MaRDI QIDQ418325FDOQ418325

Authors: J. M. McNamee, Victor Y. Pan 

Publication date: 28 May 2012

Published in: Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.camwa.2011.11.015

Recommendations

• Root-refining for a polynomial equation
• scientific article; zbMATH DE number 3928210
• On an efficient method for the simultaneous approximation of polynomial multiple roots
• 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 the \(R\)-order of some accelerated methods for the simultaneous finding of polynomial zeros

zbMATH Keywords

efficiencypolynomial factorizationcompanion matrix methodsiterative root-refinerssimultaneous iterations

Mathematics Subject Classification ID

Numerical computation of roots of polynomial equations (65H04)

Cites Work

• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Numerical computation of polynomial zeros by means of Aberth's method
• Title not available (Why is that?)
• Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
• A modified Newton method for polynomials
• Title not available (Why is that?)
• A new iterative method for the computation of the solutions of nonlinear equations
• Numerical methods for roots of polynomials. Part I
• A new family of higher order methods for solving equations
• Title not available (Why is that?)
• Solving Polynomials with Small Leading Coefficients
• Optimal Order of One-Point and Multipoint Iteration
• Title not available (Why is that?)
• Title not available (Why is that?)
• Numerical methods for roots of polynomials. II
• On a family of multipoint methods for non-linear equations
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Tangent methods for nonlinear equations
• A new family of eighth-order iterative methods for solving nonlinear equations
• Solving a Polynomial Equation: Some History and Recent Progress
• On computational efficiency of the iterative methods for the simultaneous approximation of polynomial zeros
• A nonstationary iterative second-order method for solving nonlinear equations
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• On a generalized companion matrix pencil for matrix polynomials expressed in the Lagrange basis
• Title not available (Why is that?)
• A Method for Solving Algebraic Equations Using an Automatic Computer
• \textit{qd}-type methods for quasiseparable matrices
• Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Implicit double shift \(QR\)-algorithm for companion matrices
• On zero finding methods of higher order from data at one point
• Root-finding by divided differences
• Methods without secant steps for finding a bracketed root
• A Fortran program for solving a nonlinear equation by Muller's method
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
• The DQR algorithm, basic theory, convergence, and conditional stability
• Inverse power and Durand-Kerner iterations for univariate polynomial root-finding
• A 2002 update of the supplementary bibliography on roots of polynomials
• A family of methods for solving nonlinear equations using quadratic interpolation
• Improved initialization of the accelerated and robust QR-like polynomial root-finding
• On the shifted QR iteration applied to companion matrices
• Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations
• The amended DSeSC power method for polynomial root-finding
• A biparametric family of optimally convergent sixteenth-order multipoint methods with their fourth-step weighting function as a sum of a rational and a generic two-variable function
• Generalizations of an algorithm of Sebastião e Silva
• Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
• A remark on simultaneous inclusions of the zeros of a polynomial by Gershgorin's theorem
• Recherches sur la méthode de Graeffe et les zéros des polynômes et des séries de Laurent
• Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
• Title not available (Why is that?)
• Algorithm 631
• Title not available (Why is that?)
• On Two Higher Order Enclosing Methods of J. W. Schmidt
• General polynomial roots and their multiplicities inO(N)memory andO(N²)Time^∗
• Root-Finding by Fitting Rational Functions
• Maximal order for multipoint methods with memory using hermitian information
• The Use of Rational Functions in the Iterative Solution of Equations on a Digital Computer
• Title not available (Why is that?)
• Title not available (Why is that?)
• A fast QR algorithm for companion matrices
• New progress in real and complex polynomial root-finding
• On the Convergence of Sebastião E. Silva’s Method for Finding a Zero of a Polynomial
• Optimality in a Class of Rootfinding Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new high order method of regula falsi type for computing a root of an equation
• Title not available (Why is that?)
• Generalization of Taylor's theorem and Newton's method via a new family of determinantal interpolation formulas and its applications
• Root-finding by expansion with independent constraints
• Linear construction of companion matrices
• A fast implicit QR eigenvalue algorithm for companion matrices
• A modification of Muller's method

Cited In (13)

• Nonstationary vs. stationary iterative processes
• Efficient iterations for algebraic numbers
• Iterative methods for simultaneous computing arbitrary number of multiple zeros of nonlinear equations
• Finding the Moore-Penrose inverse by a new matrix iteration
• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• Title not available (Why is that?)
• Root refinement for real polynomials using quadratic interval refinement
• Some matrix iterations for computing matrix sign function
• Finding all real roots of a polynomial by matrix algebra and the Adomian decomposition method
• An efficient matrix iteration for computing weighted Moore-Penrose inverse
• The polynomial pivots as initial values for a new root-finding iterative method
• Root-refining for a polynomial equation

Uses Software

• na20
• na10

This page was built for publication: Efficient polynomial root-refiners: a survey and new record efficiency estimates

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