Math 2.0

Numerical analysis Nonlinear equations Theorem

Splitting circle method

Builds on Root of a polynomialResidue theoremArgument principleNewton's identitiesPower sum symmetric polynomialContour integralComplex numbers

Statement

Let pp be a polynomial of degree n≥1n \ge 1 with complex coefficients. Let Γ\Gamma be the circle ∣z−c∣=ρ\abs{z - c} = \rho, traversed once counterclockwise, with no root of pp on it. Let z1,…,zkz_1, \dots, z_k be the roots of pp inside Γ\Gamma, listed with multiplicity, and let f(z)=∏j=1k(z−zj)f(z) = \prod_{j=1}^k (z - z_j).

  1. For every integer m≥0m \ge 0, the power sum sm=z1m+⋯+zkms_m = z_1^m + \cdots + z_k^m equals the contour integral sm=12πi∮Γzm p′(z)p(z) dz.s_m = \frac{1}{2\pi i} \oint_\Gamma z^m \, \frac{p'(z)}{p(z)} \, dz. In particular s0=ks_0 = k.
  2. The coefficients of ff are determined by s1,…,sks_1, \dots, s_k through Newton's identities. Moreover p=fgp = f g, where the roots of the polynomial gg are the roots of pp outside Γ\Gamma.

Remarks

Clause 1 follows from the residue theorem: p′/p=∑j1/(z−zj)p'/p = \sum_j 1/(z - z_j) over all roots of pp, and zm/(z−zj)z^m/(z - z_j) has residue zjmz_j^m at zjz_j when zjz_j lies inside Γ\Gamma, and no pole inside otherwise. For m=0m = 0 this is the argument principle. 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≈fgp \approx f g by a Newton iteration, and it recurses on ff and gg 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.

Going deeper

For a student

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.

Reading path

To understand this page from the ground up, read these 47 pages in order. The foundations come first.

  1. Complex numbers object
  2. Complex plane concept
  3. Contour integral concept
  4. Group concept
  5. Power sum symmetric polynomial concept
  6. Real numbers object
  7. Root of a polynomial concept
  8. Set bounded above definition
  9. Complex exponential definition
  10. Contour integral definition
  11. Power series in the complex plane definition
  12. Real and imaginary parts definition
  13. Ring definition
  14. Supremum definition
  15. Circle integral definition
  16. Winding number definition
  17. Disc of convergence definition
  18. Laurent series definition
  19. Commutative ring definition
  20. Polynomial ring definition
  21. Completeness axiom statement
  22. Polynomials in several variables definition
  23. Existence of square roots of nonnegative reals statement
  24. Symmetric polynomial definition
  25. Square root definition
  26. Elementary symmetric polynomials definition
  27. Power sum symmetric polynomials definition
  28. Modulus of a complex number definition
  29. Newton's identities statement
  30. Complex differentiability definition
  31. Annulus definition
  32. Holomorphic function definition
  33. Cauchy's integral formula statement
  34. Isolated singularity definition
  35. Zero of a holomorphic function definition
  36. Existence of Laurent expansions on an annulus statement
  37. Power series are holomorphic in the disc of convergence statement
  38. Pole definition
  39. Holomorphic functions are analytic statement
  40. Residue definition
  41. Meromorphic function definition
  42. Residue theorem statement
  43. Holomorphic functions are infinitely differentiable statement
  44. Order of a zero definition
  45. Order of a pole definition
  46. Argument principle statement
  47. Splitting circle method statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Splitting_circle_method
About this page
Tag7680AP09J4
URIm2://7680AP09J4
Kindstatement, theorem
WritingW0 stub
MSC65H04, 65Y20
StatusThis copy of the site has no build data. Run m2 status 7680AP09J4.
AboutRoot of a polynomial
UsesRoot of a polynomial, Residue theorem, Argument principle, Newton's identities, Power sum symmetric polynomial, Contour integral, Complex numbers
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.