Splitting circle method

Splitting circle method

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). A revised algorithm was presented by Victor Pan in 1998. An implementation was provided by Xavier Gourdon in 1996 for the Magma and PARI/GP computer algebra systems.

General description

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. With those methods it is possible to construct a factor of a given polynomial p(x)=x^n+p_{n-1}x^{n-1}+cdots+p_0 for any region of the complex plane with a piecewise smooth boundary. Most of those factors will be trivial, that is constant polynomials. Only regions that contain roots of "p(x)" result in nontrivial factors that have exactly those roots of "p(x)" as their own roots, preserving multiplicity.

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

Repeating this process for the factors found, one finally arrives at an approximative factorization of the polynomial at a required precision. The factors are either linear polynomials representing well isolated zeros or higher order polynomials representing clusters of zeros.

Details of the analytical construction

The Newton's identities are a bijective relation between the elementary symmetric polynomials of a tuple of complex numbers and its sums of powers. Therefore, it is possible to compute the coefficients of a polynomial


(or of a factor of it) from the sums of powers of its zeros

:t_m=z_1^m+cdots+z_n^m, m=0,1,dots,n

by solving the triangular system that is obtained by comparing the powers of "u" in the following identity of formal power series

: a_{n-1}+2,a_{n-2},u+cdots+(n-1),a_1,u^{n-2}+n,a_0,u^{n-1}

: = -(1+a_{n-1},u+cdots+a_1,u^{n-1}+a_0,u^n)cdot(t_1+t_2,u+t_3,u^2+dots+t_n,u^{n-1}+cdots).

If Gsubsetmathbb C is a domain with piecewise smooth boundary "C" and if the zeros of "p"("x") are pairwise distinct and not on the boundary "C", then from the residue theorem of residual calculus one gets

:frac1{2pi,i}oint_C frac{p'(z)}{p(z)}z^m,dz=sum_{zin G:,p(z)=0}frac{p'(z)z^m}{p'(z)}=sum_{zin G:,p(z)=0}z^m.

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

:f(x):=prod_{zin G:,p(z)=0}(x-z)

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

The commonly used regions are circles in the complex plane. Each circle gives raise to a split of the polynomial "p"("x") in factors "f"("x") and "g"("x"). Repeating this procedure on the factors using different circles yields finer and finer factorizations. 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"). The polynomial "f"("x") that results will only be an approximate factor. To ensure that its zeros are close to the zeros of "p" inside "G" and only to those, one must demand that all zeros of "p" are far away from the boundary "C" of the region "G".

Basic numerical observation

(Schönhage 1982) Let pinmathbb C [X] be a polynomial of degree "n" has "k" zeros inside the circle of radius "1/2" and the remaining "n-k" zeros outside the circle of radius "2". With "N=O(k)" large enough, the approximation of the contour integrals using "N" points results in an approximation f_0 of the factor "f" with error:|f-f_0|le 2^{2k-N},nk,100/98,where the norm of a polynomial is the sum of the moduli of its coefficients.

Since the zeros of a polynomial are continuous in its coefficients, one can make the zeros of f_0 as close as wanted to the zeros of "f" by choosing "N" large enough. However, one can improve this approximation faster using a Newton method. Division of "p" with remainder yields an approximation g_0 of the remaining factor "g". Now:p-f_0g_0=(f-f_0)g_0+(g-g_0)f_0+(f-f_0)(g-g_0),so discarding the last second order term one has to solve p-f_0g_0=f_0Delta g+g_0Delta f using any variant of the extended euclidian algorithm to obtain the incremented approximations f_1=f_0+Delta f and g_1=g_0+Delta g. This is repeated until the increments are zero relative to the chosen precision.

Graeffe iteration

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. Any annulus of this characteristic can be transformed, by translation and scaling of the polynomial, into the annulus between the radii 1/2 and 2 around the origin. But, not every polynomial admits such a splitting annulus.

To remedy this situation, the Graeffe iteration is applied. It computes a sequence of polynomials

:p_0=p,qquad p_{j+1}(x)=(-1)^{deg p}p(sqrt x),p(-sqrt x),

where the roots of p_j(x) are the 2^j-th dyadic powers of the roots of the initial polynomial "p". By splitting p_j(x)=e(x)+x,o(x) into even and odd parts, the succeeding polynomial is obtained by purely arithmetic operations as p_{j+1}(x)=(-1)^{deg p}(e(x)^2-x,o(x)^2). The ratios of the absolute moduli of the roots increase by the same power 2^j and thus tend to infinity. Choosing "j" large enough one finally finds a splitting annulus of relative width 4 around the origin.

The approximate factorization of p_j(x)approx f_j(x),g_j(x) is now to be lifted back to the original polynomial. To this end an alternation of Newton steps and Pade approximations is used. It is easy to check that:frac{p_{j-1}(x)}{g_j(x^2)}approx frac{f_{j-1}(x)}{g_{j-1}(-x)}holds. The polynomials on the left side are known in step "j", the polynomials on the right side can bo obtained as Padé approximants of the corresponding degrees for the power series expansion of the fraction on the left side.

Finding a good circle

Making use of the Graeffe iteration and any known estimate for the absolute value of the largest root one can find estimates "R" of this absolute value of any precision. Now one computes estimates for the largest and smallest distances R_j>r_j>0 of any root of "p"("x") to any of the five center points 0, 2"R", −2"R", 2"Ri", −2"Ri" and selects the one with the largest ratio R_j/r_j between the two. By this construction it can be guaranteed that R_j/r_j>e^{0{.}3}approx 1.35 for at least one center. For such a center there has to be a root-free annulus of relative width extstyle e^{0{.}3/n}approx 1+frac{0{.}3}{n}. After extstyle 3+log_2(n) Graeffe iterations, the corresponding annulus of the iterated polynomial has a relative width greater than 11 > 4, as required for the initial splitting described above (see Schönhage (1982)). After extstyle 4+log_2(n)+log_2(2+log_2(n)) Graeffe iterations, the corresponding annulus has a relative width greater than extstyle 2^{13{.}8}cdot n^{6{.}9}>(64cdot n^3)^2, allowing a much simplified initial splitting (see 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

:,0=sum_{j e k}|p_j|u^j-|p_k|u^k,

"u" > 0, has, by Descartes' rule of signs zero or two positive roots u_k. In the latter case, there are exactly "k" roots inside the (closed) disk D(0,u_k) and A(0,u_k,v_k) is a root-free (open) annulus.


* Schönhage, Arnold (1982): [http://www.informatik.uni-bonn.de/~schoe/fdthmrep.ps.gz "The fundamental theorem of algebra in terms of computational complexity."] Preliminary Report, Math. Inst. Univ. Tübingen (1982), 49 pages. (ps.gz)
* Pan, Victor (1998). [http://algo.inria.fr/seminars/sem97-98/pan.html "Algorithm for Approximating Complex Polynomial Zeros"]
* Pan, Victor (2002). [http://comet.lehman.cuny.edu/vpan/pdf/JSCOptimal.pdf "Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding"]
* Magma documentation. [http://magma.maths.usyd.edu.au/magma/htmlhelp/text598.htm#5334 Real and Complex Fields: Element Operations] .

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Circle grid analysis — (CGA), also known as circle grid strain analysis, is a method of measuring the strain levels of sheet metal after a part is formed by stamping or drawing. The name itself is a fairly accurate description of the process. Literally, a grid of… …   Wikipedia

  • List of circle topics — This list of circle topics includes things related to the geometric shape, either abstractly, as in idealizations studied by geometers, or concretely in physical space. It does not include metaphors like inner circle or circular reasoning in… …   Wikipedia

  • The Method of Mechanical Theorems — is a work by Archimedes which contains the first attested explicit use of infinitesimals.[1] The work was originally thought to be lost, but was rediscovered in the celebrated Archimedes Palimpsest. The palimpsest includes Archimedes account of… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Root-finding algorithm — A root finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. Such an x is called a root of the function f. This article is concerned with finding scalar, real or complex roots,… …   Wikipedia

  • Trennkreisverfahren — Das Trennkreisverfahren (engl. splitting circle method) ist eine Methode zum numerischen Faktorisieren von Polynomen in einer Variablen mit komplexen Koeffizienten. Dieses Verfahren wurde 1982 von Arnold Schönhage in dem Artikel The fundamental… …   Deutsch Wikipedia

  • Analytic number theory — In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve number theoretical problems. [Page 7 of Apostol 1976] It is often said to have begun with Dirichlet s introduction of… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Scientific phenomena named after people — This is a list of scientific phenomena and concepts named after people (eponymous phenomena). For other lists of eponyms, see eponym. NOTOC A* Abderhalden ninhydrin reaction Emil Abderhalden * Abney effect, Abney s law of additivity William de… …   Wikipedia

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.