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
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?)

  • [Ca47] A. CAUCHY, "Analyse algébrique," in Oeuvres Complètes, II série, tome III, p. 398, formula (48), Paris, 1847.
  • [CH74] George E. Collins and Ellis Horowitz, The minimum root separation of a polynomial, Math. Comp. 28 (1974), 589–597. MR 0345940, 10.1090/S0025-5718-1974-0345940-X
  • [CL76] 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.
  • [Ge59] A. O. Gel′fond, Transcendental and algebraic numbers, Translated from the first Russian edition by Leo F. Boron, Dover Publications, Inc., New York, 1960. MR 0111736
  • [Gu61] R. Güting, Approximation of algebraic numbers by algebraic numbers, Michigan Math. J. 8 (1961), 149–159. MR 0132722
  • [Gu67] R. Güting, Polynomials with multiple zeros, Mathematika 14 (1967), 181–196. MR 0223544
  • [Kn69] 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
  • [La05] 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
  • [Lo73] R. G. K. LOOS, A Constructive Approach to Algebraic Numbers, Stanford University, 27 pages, April 1973.
  • [Ma32] K. MAHLER, "Zur Approximation der Exponentialfunktion und des Logarithmus, I," J. Reine Angew. Math., v. 166, 1932, pp. 118-136.
  • [Ma60] K. Mahler, An application of Jensen’s formula to polynomials, Mathematika 7 (1960), 98–100. MR 0124467
  • [Ma64] K. Mahler, An inequality for the discriminant of a polynomial, Michigan Math. J. 11 (1964), 257–262. MR 0166188
  • [Mi74] M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157. MR 0354624, 10.1090/S0025-5718-1974-0354624-3
  • [Mi76] M. MIGNOTTE, "Some problems about polynomials," Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, August 1976, pp. 227-228.
  • [Mn49] 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
  • [Ob63] Nikola Obreschkoff, Verteilung und Berechnung der Nullstellen reeller Polynome, VEB Deutscher Verlag der Wissenschaften, Berlin, 1963 (German). MR 0164003
  • [Ru76] S. M. RUMP, "Isolierung der reellen Nullstellen algebraischer Polynome," Bericht der Arbeitsgruppe Computer Algebra, Universität Kaiserslautern, v. 10, 1976, 121 pp.
  • [Sm72] 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
  • [Sn57] Theodor Schneider, Einführung in die transzendenten Zahlen, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR 0086842
  • [vW66] 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

DOI: http://dx.doi.org/10.1090/S0025-5718-1979-0514828-8
Keywords: Polynomial zeros, inequality, root separation, computing time analysis
Article copyright: © Copyright 1979 American Mathematical Society