---
tag: 7680AP09J4
kind: statement
role: theorem
name: Splitting circle method
msc: [65H04, 65Y20]
uses: [019MA1VTR2, 032HKYS329, 0PN2BXRS8G, 0WG2A3HE0S, 0ZNXZB4HNB, 06ZGPYTWK8, 09FTAET5Z4]
about: [019MA1VTR2]
sources:
  - url: https://en.wikipedia.org/wiki/Splitting_circle_method
same_as:
  wikidata: Q1269645
  wikipedia: Splitting circle method
---

## Statement

Let $p$ be a polynomial of degree $n \ge 1$ with [[complex|09FTAET5Z4]] coefficients.
Let $\Gamma$ be the circle $\abs{z - c} = \rho$, traversed once counterclockwise, with no [[root|019MA1VTR2]] of $p$ on it.
Let $z_1, \dots, z_k$ be the roots of $p$ inside $\Gamma$, listed with multiplicity, and let $f(z) = \prod_{j=1}^k (z - z_j)$.

1. For every integer $m \ge 0$, the [[power sum|0ZNXZB4HNB]] $s_m = z_1^m + \cdots + z_k^m$ equals the [[contour integral|06ZGPYTWK8]]
$$s_m = \frac{1}{2\pi i} \oint_\Gamma z^m \, \frac{p'(z)}{p(z)} \, dz.$$
In particular $s_0 = k$.
2. The coefficients of $f$ are determined by $s_1, \dots, s_k$ through [[Newton's identities|0WG2A3HE0S]]. Moreover $p = f g$, where the roots of the polynomial $g$ are the roots of $p$ outside $\Gamma$.

## Remarks

Clause 1 follows from the [[residue theorem|032HKYS329]]: $p'/p = \sum_j 1/(z - z_j)$ over all roots of $p$, and $z^m/(z - z_j)$ has residue $z_j^m$ at $z_j$ when $z_j$ lies inside $\Gamma$, and no pole inside otherwise.
For $m = 0$ this is the [[argument principle|0PN2BXRS8G]].
The *splitting circle method* of Arnold Schönhage turns this into an algorithm.
It chooses a circle that splits the roots into two nonempty groups and stays well away from all roots, using estimates of the root moduli such as Graeffe squaring steps.
It approximates the integrals by the trapezoidal rule on the circle, which is computed with the fast Fourier transform.
It then refines the approximate factorization $p \approx f g$ by a Newton iteration, and it recurses on $f$ and $g$ until all factors are linear.
The method was designed to bound the cost of computing all roots of a polynomial to a given precision, measured in bit operations.

## Explanations

### L1 human

Draw a circle in the complex plane that has some roots of a polynomial inside and the rest outside.
Integrals around the circle count the roots inside and give the sums of their powers.
From these sums one can rebuild the factor of the polynomial that holds exactly the roots inside, and then split again until every root stands alone.

### L2 human

The method is a divide-and-conquer approach to the fundamental theorem of algebra made effective.
Its main uses are in complexity theory and in high-precision software, rather than in everyday root finding.
It shows how complex analysis, through the residue theorem, gives concrete numerical algorithms.