Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Polynomial minimum root separation


Author: Siegfried M. Rump
Journal: Math. Comp. 33 (1979), 327-336
MSC: Primary 12D10
DOI: https://doi.org/10.1090/S0025-5718-1979-0514828-8
MathSciNet review: 514828
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The minimum root separation of an arbitrary polynomial P is defined as the minimum of the distances between distinct (real or complex) roots of P. Some asymptotically good lower bounds for the root separation of P are given, where P may have multiple zeros. There are applications in the analysis of complexity of algorithms and in the theory of algebraic and transcendental numbers.


References [Enhancements On Off] (What's this?)

    A. CAUCHY, "Analyse algébrique," in Oeuvres Complètes, II série, tome III, p. 398, formula (48), Paris, 1847.
  • George E. Collins and Ellis Horowitz, The minimum root separation of a polynomial, Math. Comp. 28 (1974), 589–597. MR 345940, DOI https://doi.org/10.1090/S0025-5718-1974-0345940-X
  • G. E. COLLINS & R. G. K. LOOS, "Polynomial real root isolation by differentiation," Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, August 1976, pp. 15-25.
  • A. O. Gel′fond, Transcendental and algebraic numbers, Dover Publications, Inc., New York, 1960. Translated from the first Russian edition by Leo F. Boron. MR 0111736
  • R. Güting, Approximation of algebraic numbers by algebraic numbers, Michigan Math. J. 8 (1961), 149–159. MR 132722
  • R. Güting, Polynomials with multiple zeros, Mathematika 14 (1967), 181–196. MR 223544, DOI https://doi.org/10.1112/S002557930000379X
  • Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 0378456
  • E. Landau, Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques, Bull. Soc. Math. France 33 (1905), 251–261 (French). MR 1504527
  • R. G. K. LOOS, A Constructive Approach to Algebraic Numbers, Stanford University, 27 pages, April 1973. K. MAHLER, "Zur Approximation der Exponentialfunktion und des Logarithmus, I," J. Reine Angew. Math., v. 166, 1932, pp. 118-136.
  • K. Mahler, An application of Jensen’s formula to polynomials, Mathematika 7 (1960), 98–100. MR 124467, DOI https://doi.org/10.1112/S0025579300001637
  • K. Mahler, An inequality for the discriminant of a polynomial, Michigan Math. J. 11 (1964), 257–262. MR 166188
  • M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157. MR 354624, DOI https://doi.org/10.1090/S0025-5718-1974-0354624-3
  • M. MIGNOTTE, "Some problems about polynomials," Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, August 1976, pp. 227-228.
  • Morris Marden, The Geometry of the Zeros of a Polynomial in a Complex Variable, Mathematical Surveys, No. 3, American Mathematical Society, New York, N. Y., 1949. MR 0031114
  • Nikola Obreschkoff, Verteilung und Berechnung der Nullstellen reeller Polynome, VEB Deutscher Verlag der Wissenschaften, Berlin, 1963 (German). MR 0164003
  • S. M. RUMP, "Isolierung der reellen Nullstellen algebraischer Polynome," Bericht der Arbeitsgruppe Computer Algebra, Universität Kaiserslautern, v. 10, 1976, 121 pp.
  • Wolfgang M. Schmidt, Approximation to algebraic numbers, Secrétariat de l’Enseignement Mathématique, Université de Genève, Geneva, 1972. Série des Conférences de l’Union Mathématique Internationale, No. 2; Monographie No. 19 de l’Enseignement Mathématique. MR 0344203
  • Theodor Schneider, Einführung in die transzendenten Zahlen, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR 0086842
  • B. L. van der WAERDEN, Algebra, Springer-Verlag, New York, 1966.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12D10

Retrieve articles in all journals with MSC: 12D10


Additional Information

Keywords: Polynomial zeros, inequality, root separation, computing time analysis
Article copyright: © Copyright 1979 American Mathematical Society