Wilf's global bisection algorithm

Wilf's global bisection algorithm is a root-finding algorithm extending the idea of enclosing roots, as in the one-dimensional bisection method, to find the roots of a polynomial inside any rectangular region in the complex plane.

The rectangle in question is quadrisected into four congruent quarter rectangles. For each quarter, the image of the boundary is a curve in the complex plane. The argument principle is then applied to this path to find its winding number about the origin. Given that the polynomial is analytic within each of these quarters, a nonzero winding number N (always an integer) identifies N zeros of the polynomial inside the quarter in question, each zero counted as many times as its multiplicity.

Analogously with the bisection method, the algorithm is then applied recursively to any quarter whose boundary has nonzero winding number to further refine the estimates of the zeros. The recursion is repeated until the zero-containing rectangles are either small enough that their centres give sufficiently accurate zero estimates or until, owing to precision loss, it is not possible to continue.

See also

• Lehmer–Schur algorithm – similar method which uses circles instead of rectangles

References

• Herbert S. Wilf (July 1978), "A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane", Journal of the ACM, 25 (3): 415–420, doi:10.1145/322077.322084

• Glenn R. Luecke; James D. Francis (July 1990), "Comparative Testing of Five Numerical Methods for Finding Roots of Polynomials", Journal of Computational Mathematics, 8 (3): 202–211, JSTOR 43692481