Nearly Optimal Algorithms for Univariate Polynomial Factorization and Rootfinding.~II: Computing a~Basic Annulus for Splitting

V. Ya. Pan

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Analytic and geometric issues of complex analysis, Tome 235 (2001), pp. 211-223.

Résumé

We describe some effective algorithms for the computation of a basic well isolated annulus over which we split a given univariate $n$th degree polynomial numerically into two factors. This is extended to recursive computation of the complete numerical factorization of a polynomial into the product of its linear factors and further to the approximation of its roots. The extension incorporates the earlier techniques of Schönhage and Kirrinnis and our old and new splitting techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the complexity of both complete factorization and rootfinding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of $n$ for complete factorization and also for the approximation of well-conditioned (well isolated) roots.

Bibliographie

[1] Bini D., Pan V. Y., Polynomial and matrix computations. V. 2: Fundamental and practical algorithms, Birkhäuser, Boston etc., 2002 (to appear)

[2] Bini D., Pan V. Y., Polynomial and matrix computations. V. 1: Fundamental algorithms, Birkhäuser, Boston etc., 1994 | MR | Zbl

[3] Coppersmith D., Neff C. A., “Roots of a polynomial and its derivatives”, Proc. 5th Ann. ACM–SIAM Symp. on Discrete Algorithms, ACM Press, SIAM Publ., New York, Philadelphia, 1994, 271–279 | MR | Zbl

[4] Gelfond A. O., Ischislenie konechnykh raznostei, GITTL, M., L., 1952

[5] Kirrinnis P., “Fast computation of numerical partial fraction decompositions and contour integrals of rational functions”, Proc. Intern. Symp. on Symbolic and Algebraic Computation (ISSAC 92), ed. P. S. Wang, ACM Press, New York, 1992, 16–26 | MR | Zbl

[6] Kirrinnis P., “Polynomial factorization and partial fraction decomposition by simultaneous Newton's iteration”, J. Complexity, 14:3 (1998), 378–444 | DOI | MR | Zbl

[7] Kapur D., Lakshman Y. N., “Elimination methods: An introduction”, Symbolic and numerical computation for artificial intelligence, eds. B. Donald, D. Kapur, J. Mundy, Acad. Press, New York, 1992, 45–89 | MR

[8] Mourrain B., Pan V. Y., “Asymptotic acceleration of solving polynomial systems”, Proc. 27th Ann. ACM Symp. on Theory of Computing, ACM Press, New York, 1998, 488–496 | MR | Zbl

[9] Mourrain B., Pan V. Y., “Multivariate polynomials, duality and structured matrices”, J. Complexity, 16:1 (2000), 110–180 | DOI | MR | Zbl

[10] Neff C. A., “Specified precision polynomial root isolation is NC”, J. Comput. and Syst. Sci., 48 (1994), 429–463 | DOI | MR | Zbl

[11] Neff C. A., Reif J. H., “An $O(n^{l+\epsilon})$ algorithm for the complex root problem”, Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science, IEEE Comput. Soc. Press, 1994, 540–547

[12] Neff C. A., Reif J. H., “An efficient algorithm for the complex roots problem”, J. Complexity, 12 (1996), 81–115 | DOI | MR | Zbl

[13] Pan V. Y., “Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros”, Proc. 27th Ann. ACM Symp. on Theory of Computing, ACM Press, New York, 1995, 741–750 | Zbl

[14] Pan V. Y., “Optimal and nearly optimal algorithms for approximating polynomial zeros”, Comput. and Math. (with Applications), 31:12 (1996), 97–138 | DOI | MR | Zbl

[15] Pan V. Y., “Solving a polynomial equation: Some history and recent progress”, SIAM Rev., 39:2 (1997), 187–220 | DOI | MR | Zbl

[16] Pan V. Y., “Approximate polynomial gcds, Padé approximation, polynomial zeros, and bipartite graphs”, Proc. 9th Ann. ACM–SIAM Symp. on Discrete Algorithms, ACM Press, SIAM Publ., New York, Philadelphia, 1998, 68–77 | MR | Zbl

[17] Pan V. Y., “Approximating complex polynomial zeros: modified quadtree (Weyl's) construction and improved Newton's iteration”, J. Complexity, 16:1 (2000), 213–264 | DOI | MR | Zbl

[18] Pan V. Y., Nearly optimal algorithms for numerical univariate polynomial factorization and rootfinding. I: Splitting a polynomial into factors over an annulus, Preprint, New York, 2000 | MR

[19] Pan V. Y., “Numerical computation of a polynomial gcd and extensions”, Inform. and Comput (to appear)

[20] Pan V. Y., Chen Z. Q., “The complexity of the matrix eigenproblem”, Proc. 31st Ann. ACM Symp. on Theory of Computing, ACM Press, New York, 1999, 507–516 | MR

[21] Renegar J., “On the worst-case arithmetic complexity of approximating zeros of polynomials”, J. Complexity, 3:2 (1987), 90–113 | DOI | MR | Zbl

[22] Schönhage A., “Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients”, Lect. Notes Comput. Sci., 144, 1982, 3–15 | MR | Zbl

[23] Schönhage A., The fundamental theorem of algebra in terms of computational complexity, Preprint. Math. Dept. Univ. Tübingen, 1982

[24] Schönhage A., “Quasi-gcd computations”, J. Complexity, 1 (1985), 118–137 | DOI | MR | Zbl