Nearly Optimal Universal Polynomial Factorization and Root-Finding
J.M. McNamee and V.Y. Pan
Abstract
The zeros of a polynomial can be readily recovered from its linear factors. The linear factors can be approximated by first splitting a polynomial numerically into the product of its two nonconstant factors and then recursively splitting every computed nonlinear factor in similar fashion. For both the worst and average case inputs the resulting algorithms solve the polynomial factorization and root-finding problems within fixed sufficiently small error bounds by using nearly optimal arithmetic and Boolean time, that is using nearly optimal numbers of arithmetic and bitwise operations; in the case of a polynomial with integer coefficients ...
Get Numerical Methods for Roots of Polynomials - Part II now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
