Algorithm 954
Author:
Open Access
- 12 October 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 41 (4) , 1-24
Abstract
We report on an accurate and efficient algorithm for obtaining all roots of general real cubic and quartic polynomials. Both the cubic and quartic solvers give highly accurate roots and place no restrictions on the magnitude of the polynomial coefficients. The key to the algorithm is a proper rescaling of both polynomials. This puts upper bounds on the magnitude of the roots and is very useful in stabilizing the root finding process. The cubic solver is based on dividing the cubic polynomial into six classes. By analyzing the root surface for each class, a fast convergent Newton-Raphson starting point for a real root is obtained at a cost no higher than three additions and four multiplications. The quartic solver uses the cubic solver in getting information about stationary points and, when the quartic has real roots, stable Newton-Raphson iterations give one of the extreme real roots. The remaining roots follow by composite deflation to a cubic. If the quartic has only complex roots, the present article shows that a stable Newton-Raphson iteration on a derived symmetric sixth degree polynomial can be formulated for the real parts of the complex roots. The imaginary parts follow by solving suitable quadratics.Keywords
Funding Information
- DOE NNSA ASC
This publication has 21 references indexed in Scilit:
- Solving cubics by polynomial fittingJournal of Computational and Applied Mathematics, 2011
- Algorithm 908ACM Transactions on Mathematical Software, 2010
- A FAST NEW PUBLIC CODE FOR COMPUTING PHOTON ORBITS IN A KERR SPACETIMEThe Astrophysical Journal, 2009
- An updated supplementary bibliography on roots of polynomialsJournal of Computational and Applied Mathematics, 1999
- Generalized quartic equation of state for pure nonpolar fluidsAIChE Journal, 1994
- A bibliography on roots of polynomialsJournal of Computational and Applied Mathematics, 1993
- Algorithm 493: Zeros of a Real Polynomial [C2]ACM Transactions on Mathematical Software, 1975
- Extension of Bairstow's Method for Multiple Quadratic FactorsIMA Journal of Applied Mathematics, 1972
- Practical Problems Arising in the Solution of Polynomial EquationsIMA Journal of Applied Mathematics, 1971
- Graphical Discussion of the Roots of a Quartic EquationThe American Mathematical Monthly, 1922