×

Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\). (English) Zbl 0934.12005

This paper presents fast numerical algorithms for factoring univariate polynomials with complex coefficients and for computing partial decomposition (PFDs) of rational functions in one complex variable. Rigorous proofs for the correctness of the algorithms and for favourable asymptotic time bounds with respect to bit complexity are given. Numerically stable and computationally feasible versions of PFD are specified first for the special case of rational functions with all singularities in the unit disk (the bounded case) and then for rational functions with arbitrarily distributed singularities.
Two major algorithms for computing PFDs are presented. The first one is an extension of the splitting method by A. Schönhage (1982). The second algorithm is a Newton iteration for simultaneously improving the accuracy of all factors in an approximate PFD of a rational function. Algorithmically useful starting value conditions for the Newton algorithm are provided.
Three subalgorithms are of independent interest. They compute the product of a sequence of polynomials, the sum of a sequence of rational functions, and the modular representation of a polynomial. All algorithms are described in a great detail, and numerous technical auxiliaries are provided which are also useful for the design and analysis of other algorithms in computational complex analysis.
Combining the splitting circle method with simultaneous Newton iteration yields favourable time bounds, measured in bit iterations, for PFD, polynomial factoring, and root calculation. In particular, the time bounds for computing high accuracy PFDs, high accuracy factorizations, and high accuracy approximations for zeros of squarefree polynomials are linear in the output size, and hence optimal, up to logarithmic factors.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
65H05 Numerical computation of solutions to single equations
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aberth, O., Iteration methods for finding all zeros of a polynomial simultaneously, Math. Comp., 27, 339-344 (1973) · Zbl 0282.65037
[2] Aigner, M., Combinatorial Search (1988), Wiley-Teubner: Wiley-Teubner Chichester, Stuttgart · Zbl 0663.68076
[3] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.), 21, 1-46 (1989) · Zbl 0681.03020
[4] Borodin, A.; Munro, I., The Computational Complexity of Algebraic and Numeric Problems (1975), Elsevier: Elsevier New York · Zbl 0404.68049
[5] Brent, R. P., Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach., 23, 242-251 (1976) · Zbl 0324.65018
[6] Brent, R. P.; Kung, H. T., Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach., 25, 581-595 (1978) · Zbl 0388.68052
[7] Carstensen, C., On Grau’s method for simultaneous factorization of polynomials, SIAM J. Numer. Anal., 29, 601-613 (1992) · Zbl 0756.65072
[8] Delves, L. M.; Lyness, J. N., A numerical method for locating the zeros of an analytic function, Math. Comp., 21, 543-560 (1967) · Zbl 0153.17904
[9] Friedman, J., On the convergence of Newton’s method, J. Complexity, 5, 12-33 (1989) · Zbl 0675.65038
[10] Frommer, A., A unified approach to methods for the simultaneous computation of all zeros of generalized polynomials, Numer. Math., 54, 105-116 (1988) · Zbl 0636.65045
[11] Gourdon, X., Rapport de Recherche (1993)
[12] Gourdon, X., Combinatoire, algorithmique et géométrie des polynômes (1996), École Polytechnique
[13] Grau, A. A., The simultaneous improvement of a complete set of approximate factors of a polynomial, SIAM J. Numer. Anal., 8, 425-438 (1971) · Zbl 0221.65081
[14] Green, M.; Korsak, A.; Pease, M., Simultaneous iteration towards all roots of a complex polynomial, SIAM Rev., 18, 501-502 (1976)
[15] Henrici, P., Applied and Computational Complex Analysis (1974), Wiley: Wiley New York
[16] Jenkins, M. A.; Traub, J. F., A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration, Numer. Math., 14, 252-263 (1970) · Zbl 0176.13701
[17] Kaltofen, E., Technical Report (1992)
[18] Kerner, I. O., Ein Gesamtschrittverfahren zur Berechnung von Nullstellen von Polynomen, Numer. Math., 8, 290-294 (1966) · Zbl 0202.43605
[19] Kirrinnis, P., An optimal bound for path weights in Huffman trees, Inform. Proc. Lett., 51, 107-110 (1994) · Zbl 0942.68547
[20] Knuth, D. E., The Art of Computer Programming. Vol. 1. Fundamental Algorithms (1973), Addison-Wesley: Addison-Wesley Reading · Zbl 0191.17903
[21] Knuth, D. E., The Art of Computer Programming. Vol. 2. Seminumerical Algorithms (1981), Addison-Wesley: Addison-Wesley Reading · Zbl 0191.17903
[22] Ko, K., Complexity Theory of Real Functions (1991), Birkhäuser: Birkhäuser Boston
[23] Lehmer, D. H., A machine method for solving polynomial equations, J. Assoc. Comput. Mach., 8, 151-162 (1961) · Zbl 0106.10203
[24] Mignotte, M., An inequality about factors of polynomials, Math. Comp., 28, 1153-1157 (1974) · Zbl 0299.12101
[25] Mignotte, M., Mathematics for Computer Algebra (1992), Springer-Verlag: Springer-Verlag New York
[26] Neff, C. A., Specified precision polynomial root isolation is in NC, J. Comput. Syst. Sci., 48, 429-463 (1994) · Zbl 0806.68054
[27] Neff, C. A.; Reif, J. H., An efficient algorithm for the complex roots problem, J. Complexity, 12, 81-115 (1996) · Zbl 0888.12005
[28] Pan, V. Ya., Sequential and parallel complexity of approximate evaluation of polynomial zeros, Comput. Math. Appl., 14, 591-622 (1987) · Zbl 0634.65036
[29] Pan, V. Ya., New techniques for approximating complex polynomial zeros, Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms (1994), p. 260-270 · Zbl 0867.65021
[30] Pan, V. Ya., Optimal and nearly optimal algorithms for approximating complex polynomial zeros, Comput. Math. Appl., 31, 97-138 (1996) · Zbl 0859.65045
[31] Pasquini, L.; Trigiante, D., A globally convergent method for simultaneously finding polynomial roots, Math. Comp., 44, 135-149 (1985) · Zbl 0565.65026
[32] Preparata, F. P.; Shamos, M. I., Computational Geometry (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0759.68037
[33] Ostrowski, A., Solution of Equations and Systems of Equations (1966), Academic Press: Academic Press New York · Zbl 0222.65070
[34] Renegar, J., On the cost of approximating all roots of a complex polynomial, Math. Programming, 32, 319-336 (1985) · Zbl 0577.65040
[35] Renegar, J., On the worst-case complexity of approximating zeros of polynomials, J. Complexity, 3, 90-113 (1987) · Zbl 0642.65031
[36] Samelson, K., Faktorisierung von Polynomen durch funktionale Iteration, Bayer. Akad. Wiss. Math.-Natur. Kl. Abh., 95 (1958) · Zbl 0094.10901
[37] Schätzle, R., Zur Störung der Nullstellen von komplexen Polynomen (1990), Univ. BonnMath. Inst
[38] Schönhage, A., Storage modification machines, SIAM J. Comput., 9, 490-508 (1980) · Zbl 0454.68034
[39] Schönhage, A., Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients, Computer Algebra EUROCAM ’82 (Marseille (1982)). Computer Algebra EUROCAM ’82 (Marseille (1982)), Lecture Notes in Computer Science, 144 (1982), Springer-Verlag: Springer-Verlag New York, p. 3-15
[40] Schönhage, A., Technical Report (1982)
[41] Schönhage, A., Quasi-GCD computations, J. Complexity, 1, 118-137 (1985) · Zbl 0586.68031
[42] Schönhage, A., Equation solving in terms of computational complexity, Proc. Internat. Congress of Mathematicians, Berkeley, CA (1986), p. 131-153
[43] Schönhage, A., Numerik analytischer Funktionen und Komplexität, Jber. d. Dt. Math.-Verein. (1990), p. 1-20 · Zbl 0797.68090
[44] Schönhage, A. 1996, Ordinary root finding, Univ. Bonn; Schönhage, A. 1996, Ordinary root finding, Univ. Bonn
[45] Schönhage, A. 1997; Schönhage, A. 1997
[46] Schönhage, A.; Strassen, V., Schnelle Multiplikation großer Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007
[47] Schönhage, A.; Grotefeld, A. F.W.; Vetter, E., Fast Algorithms: A Multitape Turing Machine Implementation (1994), B.I. Wissenschaftsverlag: B.I. Wissenschaftsverlag Mannheim · Zbl 0853.68108
[48] Schröder, J., Factorization of polynomials by generalized Newton procedures, Constructive Aspects of the Fundamental Theorem of Algebra (1969), Wiley: Wiley London · Zbl 0182.21601
[49] Shub, M.; Smale, S., Computational complexity: On the geometry of polynomials and a theory of cost, Part I, Ann. Sci. École Norm. Sup. (4), 18, 107-142 (1985) · Zbl 0603.65027
[50] Shub, M.; Smale, S., Computational complexity: On the geometry of polynomials and a theory of cost, II, SIAM J. Comput., 15, 145-161 (1986) · Zbl 0625.65036
[51] Shub, M.; Smale, S., Complexity of Bezout’s theorem. I. Geometric aspects, J. Amer. Math. Soc., 6, 459-501 (1993) · Zbl 0821.65035
[52] Smale, S., The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.), 4, 1-36 (1981) · Zbl 0456.12012
[53] Smale, S., Algorithms for solving equations, Proc. Internat. Congress of Mathematicians, Berkeley, CA (1986), p. 172-195
[54] Strassen, V., The computational complexity of continued fractions, SIAM J. Comput., 12, 1-27 (1983) · Zbl 0543.68026
[55] van der Waerden, B. L., Algebra I (1971), Springer-Verlag: Springer-Verlag Berlin · Zbl 0221.12001
[56] Weierstrass, K., Neuer Beweis des Satzes, dass jede ganze rationale Function einer Veränderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veränderlichen, Gesammelte Mathematische Werke (1891), Mayer & Müller: Mayer & Müller Berlin · JFM 23.0083.02
[57] Weyl, H., Randbemerkungen zu Hauptproblemen der Mathematik. II. Fundamentalsatz der Algebra und Grundlagen der Mathematik, Math. Z., 20, 142-150 (1924) · JFM 50.0064.03
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.