×

Optimal and nearly optimal algorithms for approximating polynomial zeros. (English) Zbl 0859.65045

The author presents a new algorithm for approximating all complex zeros of a polynomial. The new algorithm is shown to be superior to the previous best algorithms – in fact it is shown to be asymptotically optimal. Parallel aspects are also addressed and, even though no results on a parallel implementation are reported, the algorithm is expected to parallelize well.

MSC:

65H05 Numerical computation of solutions to single equations
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
12Y05 Computational aspects of field theory and polynomials (MSC2010)
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Schönhage, A., The fundamental theorem of algebra in terms of computational complexity (1982), Math. Dept., University of Tübingen: Math. Dept., University of Tübingen Tübingen, Germany, (manuscript)
[2] Pan, V. Y., Sequential and parallel complexity of approximate evaluation of polynomial zeros, Computers Math. Applic., 14, 8, 591-622 (1987) · Zbl 0634.65036
[3] Neff, C. A.; Reif, J. H., An \(O(n^{1+ϵ}\) log \(b)\) algorithm for the complex root problem, (Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science (1994), IEEE Computer Society Press), 540-547
[4] Neff, C. A., Specified precision polynomial root isolation is in NC, Journal of Computer and System Sciences, 48, 429-463 (1994) · Zbl 0806.68054
[5] Bini, D., Complexity of parallel polynomial computations, (Evans, J.; Nodari, C., Proc. Parallel Computing: Methods, Algorithms, Applications (1989), Adam Hilger: Adam Hilger Bristol), 115-126
[6] Bini, D.; Gemignani, L., On the complexity of polynomial zeros, SIAM J. on Sci. Stat. Computing, 8, 21, 781-799 (1992) · Zbl 0756.65071
[7] Kirrinnis, P., Polynomial factorization and partial fraction decomposition by simultaneous Newton’s iteration (1994), (extended abstract)
[8] Pan, V. Y., Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros, (Proc. \(27^{th}\) Annual ACM Symposium on Theory of Computing (1995), ACM Press: ACM Press New York), 741-750 · Zbl 0942.68796
[9] Weyl, H., Randbemerkungen zu Hauptproblemen der Mathematik, II, Fundamentalsatz der Algebra and Grundlagen der der Mathematik, Math. Z., 20, 131-151 (1924) · JFM 50.0064.03
[10] (Brouwer, L. E.J., Coll. Works (1975), North-Holland: North-Holland Amsterdam)
[11] Samet, H., The quadtree and related hierarchical data structures, Computing Surveys, 16, 2, 187-260 (1984)
[12] Senoussi, H., A quadtree algorithm for template matching on pyramid computer, Theor. Comp. Science, 136, 387-417 (1994) · Zbl 0874.68131
[13] Pan, V. Y., Weyl’s quadtree algorithm for the unsymmetric eigenvalue problem, Appl. Math. Lett., 8, 5, 87-88 (1995) · Zbl 0833.65029
[14] Gauss, C. F., (Werke, Band X (1973), Georg Olms Verlag: Georg Olms Verlag New York)
[15] Bell, E. T., The Development of Mathematics (1940), McGraw-Hill: McGraw-Hill New York · Zbl 0025.00101
[16] Boyer, C. A., A History of Mathematics (1968), Wiley: Wiley New York · Zbl 0182.30401
[17] (Dejon, B.; Henrici, P., Constructive Aspects of the Fundamental Theorem of Algebra (1969), Wiley: Wiley London) · Zbl 0175.00104
[18] Householder, A. S., The Numerical Treatment of a Single Nonlinear Equation (1970), McGraw-Hill: McGraw-Hill New York · Zbl 0242.65047
[19] Henrici, P., (Applied and Computational Complex Analysis, Vol. 1 (1974), Wiley: Wiley New York)
[20] Smale, S., The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc., 4, 1-36 (1981) · Zbl 0456.12012
[21] Pan, V. Y., Solving a polynomial equation: Some history and recent progress (1995), (preprint) · Zbl 0839.68033
[22] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1976), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029
[23] Karp, R.; Ramachandran, V., A survey of parallel algorithms for shared memory machines, (van Leeuwen, J., Handbook for Theoretical Computer Science (1990), North-Holland: North-Holland Amsterdam), 869-941 · Zbl 0900.68267
[24] Turan, P., On the approximate solution of algebraic functions (in Hungarian), Comm. Math. Phys. Class Hung. Acad., XVIII, 223-236 (1968)
[25] Henrici, P.; Gargantini, I., Uniformly convergent algorithms for the simultaneous approximation of all zeros of a polynomial, (Dejon, B.; Henrici, P., Constructive Aspects of the Fundamental Theorem of Algebra (1969), Wiley: Wiley London) · Zbl 0194.46902
[26] Renegar, J., On the worst-case arithmetic complexity of approximating zeros of polynomials, J. of Complexity, 3, 2, 90-113 (1987) · Zbl 0642.65031
[27] Coppersmith, D.; Neff, C. A., Roots of a polynomial and its derivatives, (Proc. \(5^{th}\) Ann. ACM-SIAM Symp. on Discrete Algorithms (1994), ACM Press: ACM Press New York), 271-279, and SIAM Publications, Philadelphia · Zbl 0867.65022
[28] Pan, V. Y., Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant, Computers Math. Applic., 30, 2, 71-94 (1995) · Zbl 0839.68033
[29] Pan, V. Y., New techniques for approximating complex polynomial zeros, (Proc. \(5^{th}\) Ann. ACM-SIAM Symp. on Discrete Algorithms (1994), ACM Press: ACM Press New York), 260-270, and SIAM Publications, Philadelphia · Zbl 0867.65021
[30] Ben-Or, M.; Feig, E.; Kozen, D.; Tiwari, P., A fast parallel algorithm for determining all roots of a polynomial with real roots, SIAM J. on Comput., 17, 1081-1092 (1989) · Zbl 0663.68047
[31] Ben-Or, M.; Tiwari, P., Simple algorithm for approximating all roots of a polynomial with real roots, J. of Complexity, 6, 417-442 (1990) · Zbl 0723.12011
[32] Bini, D.; Pan, V. Y., Parallel complexity of tridiagonal symmetric eigenvalue problem, (Proc. \(2^{nd}\) Ann. ACM-SIAM Symp. on Discrete Algorithms (1991), ACM Press: ACM Press New York), 384-393, and SIAM, Philadelphia · Zbl 0800.68501
[33] Pan, V. Y., New resultant inequalities and complex polynomial factorization, Journal on Computing, 23, 5, 934-950 (1994) · Zbl 0822.12005
[34] Marden, M., Geometry of Polynomials (1966), Amer. Math. Soc: Amer. Math. Soc Providence, RI · Zbl 0173.02703
[35] Soviet Physics-Dokl, 7, 7, 589-591 (1963) · Zbl 0132.24803
[36] Schönhage, A.; Strassen, V., Schnelle Multiplikation grosse Zahlen, Computing, 7, 281-292 (1971), (in German) · Zbl 0223.68007
[37] Savage, J. E., The Complexity of Computing (1976), Wiley and Sons: Wiley and Sons New York · Zbl 0363.68070
[38] Knuth, D. E., (The Art of Computer Programming: Seminumerical Algorithms, Vol. 2 (1981), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0477.65002
[39] Bini, D.; Pan, V. Y., Polynomial and Matrix Computations, Vol. 1: Fundamental Algorithms (1994), Birkhäuser, Boston · Zbl 0809.65012
[40] Karatsuba, A.; Ofman, Yu., Multiplication of multidigit numbers on automata, Soviet Physics Dokl., 7, 595-596 (1963)
[41] Durand, E., Solutions Numériques des Equations Algébriques, Tome I: Equations du Type \(F(x) = 0\): Racines d’un Polynome (1960), Masson: Masson Paris · Zbl 0099.10801
[42] Kerner, I. O., Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen, Numer. Math., 8, 290-294 (1966) · Zbl 0202.43605
[43] Aberth, O., Iteration methods for finding all zeros of a polynomial simultaneously, Math. Comput., 27, 122, 339-344 (1973) · Zbl 0282.65037
[44] Bini, D., Numerical computation of polynomial zeros by Aberth’s method (1994), Dept. of Math., University of Pisa, (manuscript)
[45] Wilf, H. S., A global bisection algorithm for computing the zeros of polynomials in the complex plane, J. ACM, 25, 415-420 (1978) · Zbl 0378.30003
[46] Pan, V. Y., On approximating complex polynomial zeros: Modified quadtree (Weyl’s) construction and improved Newton’s iteration (1994), (preprint)
[47] Pan, V. Y.; Linzer, E., A new approach to bisection acceleration for the symmetric eigenvalue problem (1995), (preprint)
[48] Smale, S., Algorithms for solving equations, (Proc. International Congress of Mathematicians. Proc. International Congress of Mathematicians, Berkeley, CA, 1986 (1987), American Math. Society: American Math. Society Providence, RI), 172-195
[49] Smale, S., On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc., 4, 1-36 (1986)
[50] Kim, M.-H.; Sutherland, S., Polynomial root-finding algorithms and branched covers, SIAM J. on Computing, 23, 2, 415-436 (1994) · Zbl 0803.65066
[51] Shub, M.; Smale, S., Complexity of Bezout’s Theorem I: Geometric aspects, J. of the Amer. Math. Soc., 6, 459-501 (1993) · Zbl 0821.65035
[52] Shub, M.; Smale, S., Complexity of Bezout’s Theorem II: Volumes and probabilities, (Eyssette, F.; Galligo, A., Computational Algebraic Geometry, Progress in Mathematics, Vol. 109 (1993)), 267-285, Birkhäuser · Zbl 0851.65031
[53] Shub, M.; Smale, S., Complexity of Bezout’s Theorem III: Condition number and packing, J. of Complexity, 9, 4-14 (1993) · Zbl 0846.65018
[54] Shub, M.; Smale, S., Complexity of Bezout’s Theorem IV: Probability of success, extensions, (Research Report RC 18921 (1993), IBM T.J. Watson Research Center: IBM T.J. Watson Research Center Yorktown Heights, NY) · Zbl 0843.65035
[55] Shub, M.; Smale, S., Complexity of Bezout’s Theorem V: Polynomial time, (Report No. 236 (1993), Centre de Recerca Matemàtica, Institut d’Estudis Catalanas: Centre de Recerca Matemàtica, Institut d’Estudis Catalanas Barcelona, Spain) · Zbl 0846.65022
[56] Van der Sluis, A., Upper bounds for roots of polynomials, Numer. Math., 15, 250-262 (1970) · Zbl 0204.48205
[57] Turan, P., Power sum method and approximative solution of algebraic equations, Math. Comp., 29, 311-318 (1975) · Zbl 0293.65027
[58] Polýa, G.; Szegö, G., (Aufgaben und Lehrsätze aus der Analysis, Vol. 1 (1945), Dover Publications: Dover Publications New York) · Zbl 0060.12307
[59] Schätzle, R., Zur Störung der Nullstellen von komplexen Polynomen, Dimplomarbeit (1990), Math. Dept., Univ. of Bonn: Math. Dept., Univ. of Bonn Bonn, Germany, (in German)
[60] Schönhage, A., Quasi-GCD computations, J. of Complexity, 1, 118-137 (1985) · Zbl 0586.68031
[61] Fischer, M. J.; Paterson, M. S., String matching and other products, (SIAM-AMS Proc., 7 (1974)), 113-125
[62] Bulletin of the EATCS, 14, 95 (1981)
[63] Pan, V. Y., How to Multiply Matrices Faster, (Lecture Notes in Computer Science (1984), Springer: Springer Berlin) · Zbl 0548.65022
[64] Bini, D.; Pan, V. Y., Polynomial division and its computational complexity, J. of Complexity, 2, 179-203 (1986) · Zbl 0629.68040
[65] Delves, L. M.; Lyness, J. N., A numerical method for locating zeros of an analytic function, Math. Comp., 21, 543-560 (1967) · Zbl 0153.17904
[66] Schröder, J., Über das Newtonsche Verfahren, Arch. Rat. Mech. Anal., 1, 154-180 (1957) · Zbl 0079.13605
[67] (Proc. \(3^{rd}\) IEEE Conf. on Parallel and Distributed Proc. (1991), IEEE Computer Society Press), 212-218
[68] Reif, J. H.; Tate, S. R., Optimal size division circuits, SIAM J. on Computing, 19, 5, 912-925 (1990) · Zbl 0711.68064
[69] Gragg, W. B., The Padé table and its relation to certain algorithms of numerical analysis, SIAM Review, 14, 1, 1-62 (1972) · Zbl 0238.30008
[70] Pan, V. Y., Parametrization of Newton’s iteration for computations with structured matrices and applications, Computers Math. Applic., 24, 3, 61-75 (1992) · Zbl 0772.65013
[71] Pan, V. Y., Fast and efficient parallel algorithms for the exact inversion of integer matrices, (Proc. \(5^{th}\) Ann. Conference on Foundation of Software Technology and Theoretical Computer Science. Proc. \(5^{th}\) Ann. Conference on Foundation of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 206 (1985), Springer: Springer Berlin), 504-521
[72] Pan, V. Y., Complexity of parallel matrix computations, Theoretical Computer Science, 54, 65-85 (1987) · Zbl 0641.68058
[73] Pan, V. Y., Parallel solution of Toeplitz-like linear systems, J. of Complexity, 8, 1-21 (1992)
[74] Pan, V. Y., Concurrent iterative algorithm for Toeplitz-like linear systems, IEEE Trans. on Parallel and Distributed Systems, 4, 5, 592-600 (1993)
[75] Kirrinnis, P., Fast computation of numerical partial fraction decompositions and contour integrals of rational functions, (Wang, P. S., Proc. ACM Annual Int. Symp. on Symb. and Alg. Comput. (ISSAC92) (1992), ACM Pres: ACM Pres New York), 16-26 · Zbl 0980.65506
[76] Ahlfors, L., Complex Analysis (1979), McGraw-Hill: McGraw-Hill New York
[77] Pan, V. Y., Faster splitting a polynomial into factors over a fixed disc (1994), (preprint)
[78] Golub, G. H.; Van Loan, C. F., Matrix Computations (1989), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0733.65016
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.