In mathematics, the splitting circle method is a numerical algorithm for the numerical factorization of a polynomial and, ultimately, for finding its complex roots.
It was introduced by Arnold Schönhage in his 1982 paper The fundamental theorem of algebra in terms of computational complexity (Technical report, Mathematisches Institut der Universität Tübingen).
An implementation was provided by Xavier Gourdon in 1996 for the Magma and PARI/GP computer algebra systems.
The fundamental idea of the splitting circle method is to use methods of complex analysis, more precisely the residue theorem, to construct factors of polynomials.
for any region of the complex plane with a piecewise smooth boundary.
In the numerical realization of this method one uses disks D(c,r) (center c, radius r) in the complex plane as regions.
The boundary circle of a disk splits the set of roots of p(x) in two parts, hence the name of the method.
To a given disk one computes approximate factors following the analytical theory and refines them using Newton's method.
To avoid numerical instability one has to demand that all roots are well separated from the boundary circle of the disk.
So to obtain a good splitting circle it should be embedded in a root free annulus A(c,r,R) (center c, inner radius r, outer radius R) with a large relative width R/r.
The factors are either linear polynomials representing well isolated zeros or higher order polynomials representing clusters of zeros.
Newton's identities are a bijective relation between the elementary symmetric polynomials of a tuple of complex numbers and its sums of powers.
The identity of the left to the right side of this equation also holds for zeros with multiplicities.
By using the Newton identities one is able to compute from those sums of powers the factor
of p(x) corresponding to the zeros of p(x) inside G. By polynomial division one also obtains the second factor g(x) in p(x) = f(x)g(x).
This recursion stops after a finite number of proper splits with all factors being nontrivial powers of linear polynomials.
The challenge now consists in the conversion of this analytical procedure into a numerical algorithm with good running time.
The integration is approximated by a finite sum of a numerical integration method, making use of the fast Fourier transform for the evaluation of the polynomials p(x) and p'(x).
using any variant of the extended Euclidean algorithm to obtain the incremented approximations
This is repeated until the increments are zero relative to the chosen precision.
The crucial step in this method is to find an annulus of relative width 4 in the complex plane that contains no zeros of p and contains approximately as many zeros of p inside as outside of it.
-th dyadic powers of the roots of the initial polynomial p. By splitting
into even and odd parts, the succeeding polynomial is obtained by purely arithmetic operations as
The ratios of the absolute moduli of the roots increase by the same power
Choosing j large enough one finally finds a splitting annulus of relative width 4 around the origin.
To this end an alternation of Newton steps and Padé approximations is used.
of any root of p(x) to any of the five center points 0, 2R, −2R, 2Ri, −2Ri and selects the one with the largest ratio
Graeffe iterations, the corresponding annulus has a relative width greater than
, allowing a much simplified initial splitting (Malajovich & Zubelli 1997) To locate the best root-free annulus one uses a consequence of the Rouché theorem: For k = 1, ..., n − 1 the polynomial equation
u > 0, has, by Descartes' rule of signs zero or two positive roots