O'Reilly logo

Numerical Methods for Roots of Polynomials - Part II by Victor Pan, J.M. McNamee

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 15

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required