899:
538:
1196:
265:
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.
894:{\displaystyle {\begin{aligned}&a_{n-1}+2\,a_{n-2}\,u+\cdots +(n-1)\,a_{1}\,u^{n-2}+n\,a_{0}\,u^{n-1}\\&\quad =-(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 ).\end{aligned}}}
2048:
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.
954:
2197:
2725:
1366:). 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.
1369:
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
425:
1843:
526:
2469:
226:. 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
3359:
3234:
543:
1924:
173:
3146:
1607:
3002:
2930:
1283:
2581:
1200:
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
2348:
2059:
929:
2026:
1977:
2795:
2590:
1465:
3507:
175:
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
3406:
3049:
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 (
3047:
2861:
3691:
3452:
2233:
284:
2496:
2260:
1685:
1676:
1637:
1520:
1191:{\displaystyle {\frac {1}{2\pi \,i}}\oint _{C}{\frac {p'(z)}{p(z)}}z^{m}\,dz=\sum _{z\in G:\,p(z)=0}{\frac {p'(z)z^{m}}{p'(z)}}=\sum _{z\in G:\,p(z)=0}z^{m}.}
430:
3910:
222:) 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
3258:
3684:
1529:
1203:
3889:
3815:
2353:
3151:
3677:
3879:
278:
1848:
3537:
2747:
Making use of the
Graeffe iteration and any known estimate for the absolute value of the largest root one can find estimates
82:
281:
of a tuple of complex numbers and its sums of powers. Therefore, it is possible to compute the coefficients of a polynomial
3056:
2866:
56:
2935:
2508:
1927:
3843:
3848:
3365:
79:, to construct factors of polynomials. With those methods it is possible to construct a factor of a given polynomial
2269:
1342:
The commonly used regions are circles in the complex plane. Each circle gives raise to a split of the polynomial
3833:
3777:
3792:
3736:
3708:
3700:
2751:
of this absolute value of any precision. Now one computes estimates for the largest and smallest distances
906:
47:(Technical report, Mathematisches Institut der UniversitĂ€t TĂŒbingen). A revised algorithm was presented by
3782:
1982:
1933:
1371:
274:
2754:
3874:
1433:
3457:
1398:) that results will only be an approximate factor. To ensure that its zeros are close to the zeros of
3853:
3828:
3592:
3371:
2583:
is now to be lifted back to the original polynomial. To this end an alternation of Newton steps and
1647:
large enough. However, one can improve this approximation faster using a Newton method. Division of
52:
3838:
3767:
3759:
2732:
2584:
2053:
533:
40:
2350:
into even and odd parts, the succeeding polynomial is obtained by purely arithmetic operations as
2932:
for at least one center. For such a center there has to be a root-free annulus of relative width
2824:
36:
25:
3884:
3805:
3749:
3744:
3415:
3007:
223:
2192:{\displaystyle p_{0}=p,\qquad p_{j+1}(x)=(-1)^{\deg p}p_{j}({\sqrt {x}})\,p_{j}(-{\sqrt {x}}),}
3800:
3662:
3652:
Univariate
Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding
3531:
3244:
2202:
1612:
Since the zeros of a polynomial are continuous in its coefficients, one can make the zeros of
3716:
3625:
3600:
3569:
214:) in the complex plane as regions. The boundary circle of a disk splits the set of roots of
72:
3523:
The fundamental theorem of algebra in terms of computational complexity. Preliminary Report
2720:{\displaystyle {\frac {p_{j-1}(x)}{g_{j}(x^{2})}}\approx {\frac {f_{j-1}(x)}{g_{j-1}(-x)}}}
2474:
2238:
1654:
1615:
1498:
3521:
2502:
large enough one finally finds a splitting annulus of relative width 4 around the origin.
948:
76:
3613:
3596:
3583:
Pan, V. Y. (1997). "Solving a polynomial equation: Some history and recent progresses".
3650:
33:
3630:
3904:
3823:
3772:
3574:
3557:
3721:
2736:
2028:. This is repeated until the increments are zero relative to the chosen precision.
3640:
420:{\displaystyle p(x)=x^{n}+p_{n-1}x^{n-1}+\cdots +p_{0}=(x-z_{1})\cdots (x-z_{n})}
3148:
Graeffe iterations, the corresponding annulus has a relative width greater than
17:
3726:
3604:
1838:{\displaystyle p-f_{0}g_{0}=(f-f_{0})g_{0}+(g-g_{0})f_{0}+(f-f_{0})(g-g_{0}),}
48:
29:
1609:
where the norm of a polynomial is the sum of the moduli of its coefficients.
528:
by solving the triangular system that is obtained by comparing the powers of
2471:. The ratios of the absolute moduli of the roots increase by the same power
3546:
3669:
3558:"Optimal and nearly optimal algorithms for approximating polynomial zeros"
71:
The fundamental idea of the splitting circle method is to use methods of
2036:
The crucial step in this method is to find an annulus of relative width
521:{\displaystyle t_{m}=z_{1}^{m}+\cdots +z_{n}^{m}\,,\quad m=0,1,\dots ,n}
60:
45:
The fundamental theorem of algebra in terms of computational complexity
3243:
To locate the best root-free annulus one uses a consequence of the
2863:
between the two. By this construction it can be guaranteed that
183:) result in nontrivial factors that have exactly those roots of
3673:
1491:
large enough, the approximation of the contour integrals using
2464:{\displaystyle p_{j+1}(x)=(-1)^{\deg p}(e(x)^{2}-x\,o(x)^{2})}
3354:{\displaystyle \,0=\sum _{j\neq k}|p_{j}|u^{j}-|p_{k}|u^{k},}
3229:{\textstyle 2^{13{.}8}\cdot n^{6{.}9}>(64\cdot n^{3})^{2}}
1307:. By polynomial division one also obtains the second factor
427:(or of a factor of it) from the sums of powers of its zeros
194:
In the numerical realization of this method one uses disks
2727:
holds. The polynomials on the left side are known in step
1845:
so discarding the last second order term one has to solve
2262:-th dyadic powers of the roots of the initial polynomial
1919:{\displaystyle p-f_{0}g_{0}=f_{0}\Delta g+g_{0}\Delta f}
3614:"A fast and stable algorithm for splitting polynomials"
2731:, the polynomials on the right side can be obtained as
168:{\displaystyle p(x)=x^{n}+p_{n-1}x^{n-1}+\cdots +p_{0}}
3548:
Combinatoire, Algorithmique et
Geometrie des Polynomes
3154:
3059:
3010:
2938:
3460:
3418:
3374:
3261:
3141:{\textstyle 4+\log _{2}(n)+\log _{2}(2+\log _{2}(n))}
2869:
2827:
2757:
2593:
2511:
2477:
2356:
2272:
2241:
2205:
2062:
1985:
1936:
1851:
1688:
1657:
1618:
1602:{\displaystyle \|f-f_{0}\|\leq 2^{2k-N}\,nk\,100/98,}
1532:
1501:
1436:
1406:
and only to those, one must demand that all zeros of
1206:
957:
909:
541:
433:
287:
85:
3642:
2997:{\textstyle e^{0{.}3/n}\approx 1+{\frac {0{.}3}{n}}}
2925:{\displaystyle R_{j}/r_{j}>e^{0{.}3}\approx 1.35}
3867:
3814:
3791:
3758:
3735:
3707:
1278:{\displaystyle f(x):=\prod _{z\in G:\,p(z)=0}(x-z)}
3501:
3446:
3400:
3353:
3228:
3140:
3041:
2996:
2924:
2855:
2789:
2719:
2576:{\displaystyle p_{j}(x)\approx f_{j}(x)\,g_{j}(x)}
2575:
2490:
2463:
2342:
2254:
2227:
2191:
2056:is applied. It computes a sequence of polynomials
2020:
1971:
1918:
1837:
1670:
1631:
1601:
1514:
1459:
1277:
1190:
923:
893:
520:
419:
167:
3237:
3612:Malajovich, Gregorio; Zubelli, Jorge P. (1997).
3236:, allowing a much simplified initial splitting (
943:) are pairwise distinct and not on the boundary
3526:, Math. Inst. Univ. TĂŒbingen. 49 pages. (ps.gz)
2040:in the complex plane that contains no zeros of
191:) as their own roots, preserving multiplicity.
3685:
3618:Computers & Mathematics with Applications
2343:{\displaystyle p_{j}(x)=e(x^{2})+x\,o(x^{2})}
8:
2739:expansion of the fraction on the left side.
2044:and contains approximately as many zeros of
1552:
1533:
3663:Real and Complex Fields: Element Operations
2821:and selects the one with the largest ratio
931:is a domain with piecewise smooth boundary
51:in 1998. An implementation was provided by
3692:
3678:
3670:
3629:
3573:
3490:
3477:
3459:
3435:
3417:
3392:
3379:
3373:
3342:
3333:
3327:
3318:
3309:
3300:
3294:
3285:
3273:
3262:
3260:
3220:
3210:
3184:
3180:
3163:
3159:
3153:
3117:
3095:
3070:
3058:
3050:
3021:
3009:
2980:
2974:
2955:
2947:
2943:
2937:
2906:
2902:
2889:
2880:
2874:
2868:
2847:
2838:
2832:
2826:
2775:
2762:
2756:
2690:
2663:
2656:
2641:
2628:
2601:
2594:
2592:
2558:
2553:
2538:
2516:
2510:
2482:
2476:
2452:
2438:
2426:
2398:
2361:
2355:
2331:
2320:
2305:
2277:
2271:
2246:
2240:
2210:
2204:
2176:
2164:
2159:
2149:
2140:
2124:
2087:
2067:
2061:
2003:
1990:
1984:
1954:
1941:
1935:
1930:to obtain the incremented approximations
1904:
1885:
1872:
1862:
1850:
1823:
1801:
1779:
1766:
1744:
1731:
1709:
1699:
1687:
1662:
1656:
1623:
1617:
1588:
1584:
1577:
1562:
1546:
1531:
1506:
1500:
1444:
1443:
1435:
1427:
1239:
1226:
1205:
1179:
1154:
1141:
1106:
1082:
1061:
1048:
1034:
1028:
987:
981:
970:
958:
956:
917:
916:
908:
863:
858:
852:
833:
828:
822:
811:
805:
792:
773:
768:
762:
743:
738:
732:
715:
703:
664:
659:
653:
648:
630:
625:
619:
614:
586:
574:
569:
551:
542:
540:
486:
480:
475:
456:
451:
438:
432:
408:
383:
361:
336:
320:
307:
286:
159:
134:
118:
105:
84:
3408:. In the latter case, there are exactly
3255: â 1 the polynomial equation
2805:) to any of the five center points 0, 2
1651:with remainder yields an approximation
3529:
1374:for the evaluation of the polynomials
270:Details of the analytical construction
2735:of the corresponding degrees for the
924:{\displaystyle G\subset \mathbb {C} }
277:are a bijective relation between the
28:for the numerical factorization of a
7:
2498:and thus tend to infinity. Choosing
2021:{\displaystyle g_{1}=g_{0}+\Delta g}
1972:{\displaystyle f_{1}=f_{0}+\Delta f}
3911:Polynomial factorization algorithms
2790:{\displaystyle R_{j}>r_{j}>0}
1639:as close as wanted to the zeros of
1495:points results in an approximation
1483:zeros outside the circle of radius
2587:is used. It is easy to check that
2012:
1963:
1910:
1891:
1475:zeros inside the circle of radius
14:
2505:The approximate factorization of
1460:{\displaystyle p\in \mathbb {C} }
32:and, ultimately, for finding its
3890:Sidi's generalized secant method
3502:{\displaystyle A(0,u_{k},v_{k})}
1295:) corresponding to the zeros of
279:elementary symmetric polynomials
3880:Inverse quadratic interpolation
3509:is a root-free (open) annulus.
3412:roots inside the (closed) disk
2082:
1410:are far away from the boundary
683:
490:
3496:
3464:
3441:
3422:
3401:{\displaystyle u_{k}<v_{k}}
3334:
3319:
3301:
3286:
3217:
3197:
3135:
3132:
3126:
3104:
3085:
3079:
3036:
3030:
2711:
2702:
2681:
2675:
2647:
2634:
2619:
2613:
2570:
2564:
2550:
2544:
2528:
2522:
2458:
2449:
2442:
2423:
2416:
2410:
2395:
2385:
2379:
2373:
2337:
2324:
2311:
2298:
2289:
2283:
2222:
2216:
2183:
2170:
2156:
2146:
2121:
2111:
2105:
2099:
2052:To remedy this situation, the
1829:
1810:
1807:
1788:
1772:
1753:
1737:
1718:
1454:
1448:
1272:
1260:
1249:
1243:
1216:
1210:
1164:
1158:
1128:
1122:
1099:
1093:
1071:
1065:
1018:
1012:
1004:
998:
951:of residual calculus one gets
881:
785:
779:
690:
611:
599:
414:
395:
389:
370:
297:
291:
254:) with a large relative width
95:
89:
1:
3631:10.1016/S0898-1221(96)00233-7
3551:. Paris: Ecole Polytechnique.
3238:Malajovich & Zubelli 1997
532:in the following identity of
3575:10.1016/0898-1221(96)00080-6
1928:extended Euclidean algorithm
3368:zero or two positive roots
3042:{\textstyle 3+\log _{2}(n)}
2856:{\displaystyle R_{j}/r_{j}}
1422:Basic numerical observation
3927:
3709:Bracketing (no derivative)
3536:: CS1 maint: postscript (
3520:Schönhage, Arnold (1982),
3447:{\displaystyle D(0,u_{k})}
1467:be a polynomial of degree
63:computer algebra systems.
3605:10.1137/S0036144595288554
1926:using any variant of the
3545:Gourdon, Xavier (1996).
3366:Descartes' rule of signs
2228:{\displaystyle p_{j}(x)}
1678:of the remaining factor
3859:Splitting circle method
3844:JenkinsâTraub algorithm
3701:Root-finding algorithms
39:. It was introduced by
22:splitting circle method
3849:LehmerâSchur algorithm
3503:
3448:
3402:
3355:
3230:
3142:
3043:
2998:
2926:
2857:
2791:
2721:
2577:
2492:
2465:
2344:
2256:
2229:
2193:
2022:
1973:
1920:
1839:
1672:
1633:
1603:
1516:
1461:
1372:fast Fourier transform
1279:
1192:
925:
895:
522:
421:
169:
3875:Fixed-point iteration
3661:Magma documentation.
3504:
3449:
3403:
3356:
3231:
3143:
3044:
2999:
2927:
2858:
2792:
2743:Finding a good circle
2722:
2578:
2493:
2491:{\displaystyle 2^{j}}
2466:
2345:
2257:
2255:{\displaystyle 2^{j}}
2230:
2194:
2023:
1974:
1921:
1840:
1673:
1671:{\displaystyle g_{0}}
1634:
1632:{\displaystyle f_{0}}
1604:
1517:
1515:{\displaystyle f_{0}}
1462:
1280:
1193:
926:
896:
523:
422:
170:
75:, more precisely the
3834:DurandâKerner method
3778:NewtonâKrylov method
3649:Pan, Victor (2002),
3639:Pan, Victor (1998),
3458:
3416:
3372:
3259:
3152:
3057:
3008:
2936:
2867:
2825:
2755:
2591:
2509:
2475:
2354:
2270:
2239:
2203:
2060:
1983:
1934:
1849:
1686:
1655:
1616:
1530:
1499:
1434:
1204:
955:
935:and if the zeros of
907:
539:
431:
285:
83:
3783:Steffensen's method
3597:1997SIAMR..39..187P
3556:Pan, V. Y. (1996).
2585:Padé approximations
2199:where the roots of
534:formal power series
485:
461:
275:Newton's identities
67:General description
26:numerical algorithm
3816:Polynomial methods
3562:Comput. Math. Appl
3499:
3444:
3398:
3351:
3284:
3226:
3138:
3039:
2994:
2922:
2853:
2787:
2717:
2573:
2488:
2461:
2340:
2252:
2225:
2189:
2018:
1969:
1916:
1835:
1668:
1629:
1599:
1512:
1479:and the remaining
1457:
1390:). The polynomial
1275:
1259:
1188:
1174:
1081:
921:
891:
889:
518:
471:
447:
417:
165:
43:in his 1982 paper
3898:
3897:
3854:Laguerre's method
3829:Bairstow's method
3269:
2992:
2733:Padé approximants
2715:
2651:
2181:
2154:
2054:Graeffe iteration
2032:Graeffe iteration
1222:
1137:
1132:
1044:
1022:
975:
3918:
3839:Graeffe's method
3768:Broyden's method
3717:Bisection method
3694:
3687:
3680:
3671:
3658:
3657:
3645:
3635:
3633:
3608:
3579:
3577:
3552:
3541:
3535:
3527:
3508:
3506:
3505:
3500:
3495:
3494:
3482:
3481:
3453:
3451:
3450:
3445:
3440:
3439:
3407:
3405:
3404:
3399:
3397:
3396:
3384:
3383:
3364:> 0, has, by
3360:
3358:
3357:
3352:
3347:
3346:
3337:
3332:
3331:
3322:
3314:
3313:
3304:
3299:
3298:
3289:
3283:
3235:
3233:
3232:
3227:
3225:
3224:
3215:
3214:
3193:
3192:
3188:
3172:
3171:
3167:
3147:
3145:
3144:
3139:
3122:
3121:
3100:
3099:
3075:
3074:
3048:
3046:
3045:
3040:
3026:
3025:
3003:
3001:
3000:
2995:
2993:
2988:
2984:
2975:
2964:
2963:
2959:
2951:
2931:
2929:
2928:
2923:
2915:
2914:
2910:
2894:
2893:
2884:
2879:
2878:
2862:
2860:
2859:
2854:
2852:
2851:
2842:
2837:
2836:
2796:
2794:
2793:
2788:
2780:
2779:
2767:
2766:
2726:
2724:
2723:
2718:
2716:
2714:
2701:
2700:
2684:
2674:
2673:
2657:
2652:
2650:
2646:
2645:
2633:
2632:
2622:
2612:
2611:
2595:
2582:
2580:
2579:
2574:
2563:
2562:
2543:
2542:
2521:
2520:
2497:
2495:
2494:
2489:
2487:
2486:
2470:
2468:
2467:
2462:
2457:
2456:
2431:
2430:
2409:
2408:
2372:
2371:
2349:
2347:
2346:
2341:
2336:
2335:
2310:
2309:
2282:
2281:
2261:
2259:
2258:
2253:
2251:
2250:
2234:
2232:
2231:
2226:
2215:
2214:
2198:
2196:
2195:
2190:
2182:
2177:
2169:
2168:
2155:
2150:
2145:
2144:
2135:
2134:
2098:
2097:
2072:
2071:
2027:
2025:
2024:
2019:
2008:
2007:
1995:
1994:
1978:
1976:
1975:
1970:
1959:
1958:
1946:
1945:
1925:
1923:
1922:
1917:
1909:
1908:
1890:
1889:
1877:
1876:
1867:
1866:
1844:
1842:
1841:
1836:
1828:
1827:
1806:
1805:
1784:
1783:
1771:
1770:
1749:
1748:
1736:
1735:
1714:
1713:
1704:
1703:
1677:
1675:
1674:
1669:
1667:
1666:
1638:
1636:
1635:
1630:
1628:
1627:
1608:
1606:
1605:
1600:
1592:
1576:
1575:
1551:
1550:
1521:
1519:
1518:
1513:
1511:
1510:
1466:
1464:
1463:
1458:
1447:
1284:
1282:
1281:
1276:
1258:
1197:
1195:
1194:
1189:
1184:
1183:
1173:
1133:
1131:
1121:
1112:
1111:
1110:
1092:
1083:
1080:
1033:
1032:
1023:
1021:
1007:
997:
988:
986:
985:
976:
974:
959:
947:, then from the
930:
928:
927:
922:
920:
900:
898:
897:
892:
890:
874:
873:
857:
856:
838:
837:
827:
826:
810:
809:
797:
796:
778:
777:
767:
766:
754:
753:
737:
736:
714:
713:
679:
675:
674:
658:
657:
641:
640:
624:
623:
585:
584:
562:
561:
545:
527:
525:
524:
519:
484:
479:
460:
455:
443:
442:
426:
424:
423:
418:
413:
412:
388:
387:
366:
365:
347:
346:
331:
330:
312:
311:
174:
172:
171:
166:
164:
163:
145:
144:
129:
128:
110:
109:
73:complex analysis
55:in 1996 for the
41:Arnold Schönhage
3926:
3925:
3921:
3920:
3919:
3917:
3916:
3915:
3901:
3900:
3899:
3894:
3885:Muller's method
3863:
3810:
3806:Ridders' method
3787:
3754:
3750:Halley's method
3745:Newton's method
3731:
3703:
3698:
3668:
3655:
3648:
3638:
3611:
3582:
3555:
3544:
3528:
3519:
3515:
3486:
3473:
3456:
3455:
3431:
3414:
3413:
3388:
3375:
3370:
3369:
3338:
3323:
3305:
3290:
3257:
3256:
3216:
3206:
3176:
3155:
3150:
3149:
3113:
3091:
3066:
3055:
3054:
3017:
3006:
3005:
2976:
2939:
2934:
2933:
2898:
2885:
2870:
2865:
2864:
2843:
2828:
2823:
2822:
2797:of any root of
2771:
2758:
2753:
2752:
2745:
2686:
2685:
2659:
2658:
2637:
2624:
2623:
2597:
2596:
2589:
2588:
2554:
2534:
2512:
2507:
2506:
2478:
2473:
2472:
2448:
2422:
2394:
2357:
2352:
2351:
2327:
2301:
2273:
2268:
2267:
2266:. By splitting
2242:
2237:
2236:
2206:
2201:
2200:
2160:
2136:
2120:
2083:
2063:
2058:
2057:
2034:
1999:
1986:
1981:
1980:
1950:
1937:
1932:
1931:
1900:
1881:
1868:
1858:
1847:
1846:
1819:
1797:
1775:
1762:
1740:
1727:
1705:
1695:
1684:
1683:
1658:
1653:
1652:
1619:
1614:
1613:
1558:
1542:
1528:
1527:
1502:
1497:
1496:
1432:
1431:
1424:
1202:
1201:
1175:
1114:
1113:
1102:
1085:
1084:
1024:
1008:
990:
989:
977:
963:
953:
952:
949:residue theorem
905:
904:
888:
887:
859:
848:
829:
818:
801:
788:
769:
758:
739:
728:
699:
677:
676:
660:
649:
626:
615:
570:
547:
537:
536:
434:
429:
428:
404:
379:
357:
332:
316:
303:
283:
282:
272:
250:, outer radius
246:, inner radius
224:Newton's method
155:
130:
114:
101:
81:
80:
77:residue theorem
69:
12:
11:
5:
3924:
3922:
3914:
3913:
3903:
3902:
3896:
3895:
3893:
3892:
3887:
3882:
3877:
3871:
3869:
3865:
3864:
3862:
3861:
3856:
3851:
3846:
3841:
3836:
3831:
3826:
3820:
3818:
3812:
3811:
3809:
3808:
3803:
3801:Brent's method
3797:
3795:
3793:Hybrid methods
3789:
3788:
3786:
3785:
3780:
3775:
3770:
3764:
3762:
3756:
3755:
3753:
3752:
3747:
3741:
3739:
3733:
3732:
3730:
3729:
3724:
3719:
3713:
3711:
3705:
3704:
3699:
3697:
3696:
3689:
3682:
3674:
3667:
3666:
3659:
3646:
3636:
3609:
3591:(2): 187â220.
3580:
3568:(12): 97â138.
3553:
3542:
3516:
3514:
3511:
3498:
3493:
3489:
3485:
3480:
3476:
3472:
3469:
3466:
3463:
3443:
3438:
3434:
3430:
3427:
3424:
3421:
3395:
3391:
3387:
3382:
3378:
3350:
3345:
3341:
3336:
3330:
3326:
3321:
3317:
3312:
3308:
3303:
3297:
3293:
3288:
3282:
3279:
3276:
3272:
3268:
3265:
3245:Rouché theorem
3223:
3219:
3213:
3209:
3205:
3202:
3199:
3196:
3191:
3187:
3183:
3179:
3175:
3170:
3166:
3162:
3158:
3137:
3134:
3131:
3128:
3125:
3120:
3116:
3112:
3109:
3106:
3103:
3098:
3094:
3090:
3087:
3084:
3081:
3078:
3073:
3069:
3065:
3062:
3051:Schönhage 1982
3038:
3035:
3032:
3029:
3024:
3020:
3016:
3013:
2991:
2987:
2983:
2979:
2973:
2970:
2967:
2962:
2958:
2954:
2950:
2946:
2942:
2921:
2918:
2913:
2909:
2905:
2901:
2897:
2892:
2888:
2883:
2877:
2873:
2850:
2846:
2841:
2835:
2831:
2786:
2783:
2778:
2774:
2770:
2765:
2761:
2744:
2741:
2713:
2710:
2707:
2704:
2699:
2696:
2693:
2689:
2683:
2680:
2677:
2672:
2669:
2666:
2662:
2655:
2649:
2644:
2640:
2636:
2631:
2627:
2621:
2618:
2615:
2610:
2607:
2604:
2600:
2572:
2569:
2566:
2561:
2557:
2552:
2549:
2546:
2541:
2537:
2533:
2530:
2527:
2524:
2519:
2515:
2485:
2481:
2460:
2455:
2451:
2447:
2444:
2441:
2437:
2434:
2429:
2425:
2421:
2418:
2415:
2412:
2407:
2404:
2401:
2397:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2370:
2367:
2364:
2360:
2339:
2334:
2330:
2326:
2323:
2319:
2316:
2313:
2308:
2304:
2300:
2297:
2294:
2291:
2288:
2285:
2280:
2276:
2249:
2245:
2224:
2221:
2218:
2213:
2209:
2188:
2185:
2180:
2175:
2172:
2167:
2163:
2158:
2153:
2148:
2143:
2139:
2133:
2130:
2127:
2123:
2119:
2116:
2113:
2110:
2107:
2104:
2101:
2096:
2093:
2090:
2086:
2081:
2078:
2075:
2070:
2066:
2033:
2030:
2017:
2014:
2011:
2006:
2002:
1998:
1993:
1989:
1968:
1965:
1962:
1957:
1953:
1949:
1944:
1940:
1915:
1912:
1907:
1903:
1899:
1896:
1893:
1888:
1884:
1880:
1875:
1871:
1865:
1861:
1857:
1854:
1834:
1831:
1826:
1822:
1818:
1815:
1812:
1809:
1804:
1800:
1796:
1793:
1790:
1787:
1782:
1778:
1774:
1769:
1765:
1761:
1758:
1755:
1752:
1747:
1743:
1739:
1734:
1730:
1726:
1723:
1720:
1717:
1712:
1708:
1702:
1698:
1694:
1691:
1665:
1661:
1626:
1622:
1598:
1595:
1591:
1587:
1583:
1580:
1574:
1571:
1568:
1565:
1561:
1557:
1554:
1549:
1545:
1541:
1538:
1535:
1522:of the factor
1509:
1505:
1456:
1453:
1450:
1446:
1442:
1439:
1428:Schönhage 1982
1423:
1420:
1414:of the region
1274:
1271:
1268:
1265:
1262:
1257:
1254:
1251:
1248:
1245:
1242:
1238:
1235:
1232:
1229:
1225:
1221:
1218:
1215:
1212:
1209:
1187:
1182:
1178:
1172:
1169:
1166:
1163:
1160:
1157:
1153:
1150:
1147:
1144:
1140:
1136:
1130:
1127:
1124:
1120:
1117:
1109:
1105:
1101:
1098:
1095:
1091:
1088:
1079:
1076:
1073:
1070:
1067:
1064:
1060:
1057:
1054:
1051:
1047:
1043:
1040:
1037:
1031:
1027:
1020:
1017:
1014:
1011:
1006:
1003:
1000:
996:
993:
984:
980:
973:
969:
966:
962:
919:
915:
912:
886:
883:
880:
877:
872:
869:
866:
862:
855:
851:
847:
844:
841:
836:
832:
825:
821:
817:
814:
808:
804:
800:
795:
791:
787:
784:
781:
776:
772:
765:
761:
757:
752:
749:
746:
742:
735:
731:
727:
724:
721:
718:
712:
709:
706:
702:
698:
695:
692:
689:
686:
682:
680:
678:
673:
670:
667:
663:
656:
652:
647:
644:
639:
636:
633:
629:
622:
618:
613:
610:
607:
604:
601:
598:
595:
592:
589:
583:
580:
577:
573:
568:
565:
560:
557:
554:
550:
546:
544:
517:
514:
511:
508:
505:
502:
499:
496:
493:
489:
483:
478:
474:
470:
467:
464:
459:
454:
450:
446:
441:
437:
416:
411:
407:
403:
400:
397:
394:
391:
386:
382:
378:
375:
372:
369:
364:
360:
356:
353:
350:
345:
342:
339:
335:
329:
326:
323:
319:
315:
310:
306:
302:
299:
296:
293:
290:
271:
268:
162:
158:
154:
151:
148:
143:
140:
137:
133:
127:
124:
121:
117:
113:
108:
104:
100:
97:
94:
91:
88:
68:
65:
53:Xavier Gourdon
13:
10:
9:
6:
4:
3:
2:
3923:
3912:
3909:
3908:
3906:
3891:
3888:
3886:
3883:
3881:
3878:
3876:
3873:
3872:
3870:
3868:Other methods
3866:
3860:
3857:
3855:
3852:
3850:
3847:
3845:
3842:
3840:
3837:
3835:
3832:
3830:
3827:
3825:
3824:Aberth method
3822:
3821:
3819:
3817:
3813:
3807:
3804:
3802:
3799:
3798:
3796:
3794:
3790:
3784:
3781:
3779:
3776:
3774:
3773:Secant method
3771:
3769:
3766:
3765:
3763:
3761:
3757:
3751:
3748:
3746:
3743:
3742:
3740:
3738:
3734:
3728:
3725:
3723:
3720:
3718:
3715:
3714:
3712:
3710:
3706:
3702:
3695:
3690:
3688:
3683:
3681:
3676:
3675:
3672:
3664:
3660:
3654:
3653:
3647:
3644:
3643:
3637:
3632:
3627:
3623:
3619:
3615:
3610:
3606:
3602:
3598:
3594:
3590:
3586:
3581:
3576:
3571:
3567:
3563:
3559:
3554:
3550:
3549:
3543:
3539:
3533:
3525:
3524:
3518:
3517:
3512:
3510:
3491:
3487:
3483:
3478:
3474:
3470:
3467:
3461:
3436:
3432:
3428:
3425:
3419:
3411:
3393:
3389:
3385:
3380:
3376:
3367:
3363:
3348:
3343:
3339:
3328:
3324:
3315:
3310:
3306:
3295:
3291:
3280:
3277:
3274:
3270:
3266:
3263:
3254:
3250:
3246:
3241:
3239:
3221:
3211:
3207:
3203:
3200:
3194:
3189:
3185:
3181:
3177:
3173:
3168:
3164:
3160:
3156:
3129:
3123:
3118:
3114:
3110:
3107:
3101:
3096:
3092:
3088:
3082:
3076:
3071:
3067:
3063:
3060:
3052:
3033:
3027:
3022:
3018:
3014:
3011:
2989:
2985:
2981:
2977:
2971:
2968:
2965:
2960:
2956:
2952:
2948:
2944:
2940:
2919:
2916:
2911:
2907:
2903:
2899:
2895:
2890:
2886:
2881:
2875:
2871:
2848:
2844:
2839:
2833:
2829:
2820:
2816:
2812:
2808:
2804:
2800:
2784:
2781:
2776:
2772:
2768:
2763:
2759:
2750:
2742:
2740:
2738:
2734:
2730:
2708:
2705:
2697:
2694:
2691:
2687:
2678:
2670:
2667:
2664:
2660:
2653:
2642:
2638:
2629:
2625:
2616:
2608:
2605:
2602:
2598:
2586:
2567:
2559:
2555:
2547:
2539:
2535:
2531:
2525:
2517:
2513:
2503:
2501:
2483:
2479:
2453:
2445:
2439:
2435:
2432:
2427:
2419:
2413:
2405:
2402:
2399:
2391:
2388:
2382:
2376:
2368:
2365:
2362:
2358:
2332:
2328:
2321:
2317:
2314:
2306:
2302:
2295:
2292:
2286:
2278:
2274:
2265:
2247:
2243:
2219:
2211:
2207:
2186:
2178:
2173:
2165:
2161:
2151:
2141:
2137:
2131:
2128:
2125:
2117:
2114:
2108:
2102:
2094:
2091:
2088:
2084:
2079:
2076:
2073:
2068:
2064:
2055:
2050:
2047:
2043:
2039:
2031:
2029:
2015:
2009:
2004:
2000:
1996:
1991:
1987:
1966:
1960:
1955:
1951:
1947:
1942:
1938:
1929:
1913:
1905:
1901:
1897:
1894:
1886:
1882:
1878:
1873:
1869:
1863:
1859:
1855:
1852:
1832:
1824:
1820:
1816:
1813:
1802:
1798:
1794:
1791:
1785:
1780:
1776:
1767:
1763:
1759:
1756:
1750:
1745:
1741:
1732:
1728:
1724:
1721:
1715:
1710:
1706:
1700:
1696:
1692:
1689:
1681:
1663:
1659:
1650:
1646:
1642:
1624:
1620:
1610:
1596:
1593:
1589:
1585:
1581:
1578:
1572:
1569:
1566:
1563:
1559:
1555:
1547:
1543:
1539:
1536:
1525:
1507:
1503:
1494:
1490:
1486:
1482:
1478:
1474:
1470:
1451:
1440:
1437:
1429:
1421:
1419:
1417:
1413:
1409:
1405:
1401:
1397:
1393:
1389:
1385:
1381:
1377:
1373:
1367:
1365:
1361:
1357:
1353:
1350:) in factors
1349:
1345:
1340:
1338:
1334:
1330:
1326:
1322:
1318:
1314:
1310:
1306:
1302:
1298:
1294:
1290:
1285:
1269:
1266:
1263:
1255:
1252:
1246:
1240:
1236:
1233:
1230:
1227:
1223:
1219:
1213:
1207:
1198:
1185:
1180:
1176:
1170:
1167:
1161:
1155:
1151:
1148:
1145:
1142:
1138:
1134:
1125:
1118:
1115:
1107:
1103:
1096:
1089:
1086:
1077:
1074:
1068:
1062:
1058:
1055:
1052:
1049:
1045:
1041:
1038:
1035:
1029:
1025:
1015:
1009:
1001:
994:
991:
982:
978:
971:
967:
964:
960:
950:
946:
942:
938:
934:
913:
910:
901:
884:
878:
875:
870:
867:
864:
860:
853:
849:
845:
842:
839:
834:
830:
823:
819:
815:
812:
806:
802:
798:
793:
789:
782:
774:
770:
763:
759:
755:
750:
747:
744:
740:
733:
729:
725:
722:
719:
716:
710:
707:
704:
700:
696:
693:
687:
684:
681:
671:
668:
665:
661:
654:
650:
645:
642:
637:
634:
631:
627:
620:
616:
608:
605:
602:
596:
593:
590:
587:
581:
578:
575:
571:
566:
563:
558:
555:
552:
548:
535:
531:
515:
512:
509:
506:
503:
500:
497:
494:
491:
487:
481:
476:
472:
468:
465:
462:
457:
452:
448:
444:
439:
435:
409:
405:
401:
398:
392:
384:
380:
376:
373:
367:
362:
358:
354:
351:
348:
343:
340:
337:
333:
327:
324:
321:
317:
313:
308:
304:
300:
294:
288:
280:
276:
269:
267:
263:
261:
257:
253:
249:
245:
241:
237:
233:
229:
225:
221:
217:
213:
209:
205:
201:
197:
192:
190:
186:
182:
178:
160:
156:
152:
149:
146:
141:
138:
135:
131:
125:
122:
119:
115:
111:
106:
102:
98:
92:
86:
78:
74:
66:
64:
62:
58:
54:
50:
46:
42:
38:
35:
31:
27:
23:
19:
3858:
3760:Quasi-Newton
3722:Regula falsi
3651:
3641:
3621:
3617:
3588:
3584:
3565:
3561:
3547:
3522:
3409:
3361:
3252:
3248:
3242:
2818:
2814:
2810:
2806:
2802:
2798:
2748:
2746:
2737:power series
2728:
2504:
2499:
2263:
2051:
2045:
2041:
2037:
2035:
1679:
1648:
1644:
1643:by choosing
1640:
1611:
1523:
1492:
1488:
1484:
1480:
1476:
1472:
1468:
1425:
1415:
1411:
1407:
1403:
1399:
1395:
1391:
1387:
1383:
1379:
1375:
1368:
1363:
1359:
1355:
1351:
1347:
1343:
1341:
1336:
1332:
1328:
1324:
1320:
1316:
1312:
1308:
1304:
1300:
1296:
1292:
1288:
1286:
1199:
944:
940:
936:
932:
902:
529:
273:
264:
259:
255:
251:
247:
243:
239:
235:
231:
227:
219:
215:
211:
207:
203:
199:
195:
193:
188:
184:
180:
176:
70:
44:
21:
15:
3737:Householder
3624:(2): 1â23.
3585:SIAM Review
1526:with error
18:mathematics
3727:ITP method
3513:References
3251:= 1, ...,
1471:which has
242:) (center
206:) (center
49:Victor Pan
30:polynomial
3316:−
3278:≠
3271:∑
3204:⋅
3174:⋅
3124:
3102:
3077:
3053:). After
3028:
2966:≈
2917:≈
2706:−
2695:−
2668:−
2654:≈
2606:−
2532:≈
2433:−
2403:
2389:−
2174:−
2129:
2115:−
2013:Δ
1964:Δ
1911:Δ
1892:Δ
1856:−
1817:−
1795:−
1760:−
1725:−
1693:−
1570:−
1556:≤
1553:‖
1540:−
1534:‖
1441:∈
1303:) inside
1267:−
1231:∈
1224:∏
1146:∈
1139:∑
1053:∈
1046:∑
979:∮
968:π
914:⊂
879:⋯
868:−
843:⋯
783:⋅
748:−
723:⋯
708:−
688:−
669:−
635:−
606:−
594:⋯
579:−
556:−
510:…
466:⋯
402:−
393:⋯
377:−
352:⋯
341:−
325:−
210:, radius
150:⋯
139:−
123:−
3905:Category
3532:citation
3004:. After
2235:are the
1119:′
1090:′
995:′
3593:Bibcode
1487:. With
1402:inside
61:PARI/GP
34:complex
3620:. 33.
3247:: For
1682:. Now
1489:N=O(k)
1430:) Let
1382:) and
1358:) and
20:, the
3656:(PDF)
1315:) in
57:Magma
37:roots
24:is a
3538:link
3454:and
3386:<
3195:>
2920:1.35
2896:>
2817:, â2
2809:, â2
2782:>
2769:>
1979:and
1323:) =
59:and
3626:doi
3601:doi
3570:doi
3115:log
3093:log
3068:log
3019:log
2813:, 2
2400:deg
2126:deg
1586:100
1481:n-k
1477:1/2
1339:).
1287:of
903:If
16:In
3907::
3616:.
3599:.
3589:39
3587:.
3566:31
3564:.
3560:.
3534:}}
3530:{{
3240:)
3201:64
3161:13
2819:Ri
2815:Ri
1594:98
1418:.
1386:'(
1220::=
262:.
3693:e
3686:t
3679:v
3665:.
3634:.
3628::
3622:3
3607:.
3603::
3595::
3578:.
3572::
3540:)
3497:)
3492:k
3488:v
3484:,
3479:k
3475:u
3471:,
3468:0
3465:(
3462:A
3442:)
3437:k
3433:u
3429:,
3426:0
3423:(
3420:D
3410:k
3394:k
3390:v
3381:k
3377:u
3362:u
3349:,
3344:k
3340:u
3335:|
3329:k
3325:p
3320:|
3311:j
3307:u
3302:|
3296:j
3292:p
3287:|
3281:k
3275:j
3267:=
3264:0
3253:n
3249:k
3222:2
3218:)
3212:3
3208:n
3198:(
3190:9
3186:.
3182:6
3178:n
3169:8
3165:.
3157:2
3136:)
3133:)
3130:n
3127:(
3119:2
3111:+
3108:2
3105:(
3097:2
3089:+
3086:)
3083:n
3080:(
3072:2
3064:+
3061:4
3037:)
3034:n
3031:(
3023:2
3015:+
3012:3
2990:n
2986:3
2982:.
2978:0
2972:+
2969:1
2961:n
2957:/
2953:3
2949:.
2945:0
2941:e
2912:3
2908:.
2904:0
2900:e
2891:j
2887:r
2882:/
2876:j
2872:R
2849:j
2845:r
2840:/
2834:j
2830:R
2811:R
2807:R
2803:x
2801:(
2799:p
2785:0
2777:j
2773:r
2764:j
2760:R
2749:R
2729:j
2712:)
2709:x
2703:(
2698:1
2692:j
2688:g
2682:)
2679:x
2676:(
2671:1
2665:j
2661:f
2648:)
2643:2
2639:x
2635:(
2630:j
2626:g
2620:)
2617:x
2614:(
2609:1
2603:j
2599:p
2571:)
2568:x
2565:(
2560:j
2556:g
2551:)
2548:x
2545:(
2540:j
2536:f
2529:)
2526:x
2523:(
2518:j
2514:p
2500:j
2484:j
2480:2
2459:)
2454:2
2450:)
2446:x
2443:(
2440:o
2436:x
2428:2
2424:)
2420:x
2417:(
2414:e
2411:(
2406:p
2396:)
2392:1
2386:(
2383:=
2380:)
2377:x
2374:(
2369:1
2366:+
2363:j
2359:p
2338:)
2333:2
2329:x
2325:(
2322:o
2318:x
2315:+
2312:)
2307:2
2303:x
2299:(
2296:e
2293:=
2290:)
2287:x
2284:(
2279:j
2275:p
2264:p
2248:j
2244:2
2223:)
2220:x
2217:(
2212:j
2208:p
2187:,
2184:)
2179:x
2171:(
2166:j
2162:p
2157:)
2152:x
2147:(
2142:j
2138:p
2132:p
2122:)
2118:1
2112:(
2109:=
2106:)
2103:x
2100:(
2095:1
2092:+
2089:j
2085:p
2080:,
2077:p
2074:=
2069:0
2065:p
2046:p
2042:p
2038:4
2016:g
2010:+
2005:0
2001:g
1997:=
1992:1
1988:g
1967:f
1961:+
1956:0
1952:f
1948:=
1943:1
1939:f
1914:f
1906:0
1902:g
1898:+
1895:g
1887:0
1883:f
1879:=
1874:0
1870:g
1864:0
1860:f
1853:p
1833:,
1830:)
1825:0
1821:g
1814:g
1811:(
1808:)
1803:0
1799:f
1792:f
1789:(
1786:+
1781:0
1777:f
1773:)
1768:0
1764:g
1757:g
1754:(
1751:+
1746:0
1742:g
1738:)
1733:0
1729:f
1722:f
1719:(
1716:=
1711:0
1707:g
1701:0
1697:f
1690:p
1680:g
1664:0
1660:g
1649:p
1645:N
1641:f
1625:0
1621:f
1597:,
1590:/
1582:k
1579:n
1573:N
1567:k
1564:2
1560:2
1548:0
1544:f
1537:f
1524:f
1508:0
1504:f
1493:N
1485:2
1473:k
1469:n
1455:]
1452:X
1449:[
1445:C
1438:p
1426:(
1416:G
1412:C
1408:p
1404:G
1400:p
1396:x
1394:(
1392:f
1388:x
1384:p
1380:x
1378:(
1376:p
1364:x
1362:(
1360:g
1356:x
1354:(
1352:f
1348:x
1346:(
1344:p
1337:x
1335:(
1333:g
1331:)
1329:x
1327:(
1325:f
1321:x
1319:(
1317:p
1313:x
1311:(
1309:g
1305:G
1301:x
1299:(
1297:p
1293:x
1291:(
1289:p
1273:)
1270:z
1264:x
1261:(
1256:0
1253:=
1250:)
1247:z
1244:(
1241:p
1237::
1234:G
1228:z
1217:)
1214:x
1211:(
1208:f
1186:.
1181:m
1177:z
1171:0
1168:=
1165:)
1162:z
1159:(
1156:p
1152::
1149:G
1143:z
1135:=
1129:)
1126:z
1123:(
1116:p
1108:m
1104:z
1100:)
1097:z
1094:(
1087:p
1078:0
1075:=
1072:)
1069:z
1066:(
1063:p
1059::
1056:G
1050:z
1042:=
1039:z
1036:d
1030:m
1026:z
1019:)
1016:z
1013:(
1010:p
1005:)
1002:z
999:(
992:p
983:C
972:i
965:2
961:1
945:C
941:x
939:(
937:p
933:C
918:C
911:G
885:.
882:)
876:+
871:1
865:n
861:u
854:n
850:t
846:+
840:+
835:2
831:u
824:3
820:t
816:+
813:u
807:2
803:t
799:+
794:1
790:t
786:(
780:)
775:n
771:u
764:0
760:a
756:+
751:1
745:n
741:u
734:1
730:a
726:+
720:+
717:u
711:1
705:n
701:a
697:+
694:1
691:(
685:=
672:1
666:n
662:u
655:0
651:a
646:n
643:+
638:2
632:n
628:u
621:1
617:a
612:)
609:1
603:n
600:(
597:+
591:+
588:u
582:2
576:n
572:a
567:2
564:+
559:1
553:n
549:a
530:u
516:n
513:,
507:,
504:1
501:,
498:0
495:=
492:m
488:,
482:m
477:n
473:z
469:+
463:+
458:m
453:1
449:z
445:=
440:m
436:t
415:)
410:n
406:z
399:x
396:(
390:)
385:1
381:z
374:x
371:(
368:=
363:0
359:p
355:+
349:+
344:1
338:n
334:x
328:1
322:n
318:p
314:+
309:n
305:x
301:=
298:)
295:x
292:(
289:p
260:r
258:/
256:R
252:R
248:r
244:c
240:R
238:,
236:r
234:,
232:c
230:(
228:A
220:x
218:(
216:p
212:r
208:c
204:r
202:,
200:c
198:(
196:D
189:x
187:(
185:p
181:x
179:(
177:p
161:0
157:p
153:+
147:+
142:1
136:n
132:x
126:1
120:n
116:p
112:+
107:n
103:x
99:=
96:)
93:x
90:(
87:p
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.