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

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] G. E. COLLINS & E. HOROWITZ, "The minimum root separation of a polynomial," Math. Comp., v. 28, 1974, pp. 589-597. MR 0345940 (49:10669)
  • [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. GELFOND, Transcendental and Algebraic Numbers, Dover, New York, 1959. MR 0111736 (22:2598)
  • [Gu61] R. GÜTING, "Approximation of algebraic numbers by algebraic numbers," Michigan Math. J., v. 8, 1961, pp. 149-159. MR 0132722 (24:A2559)
  • [Gu67] R. GÜTING, "Polynomials with multiple zeros," Mathematika, v. 14, 1967, pp. 181-196. MR 0223544 (36:6592)
  • [Kn69] D. E. KNUTH, The Art of Computer Programming, Vol. I (Fundamental Algorithms), Addison-Wesley, Reading, Mass., 1969. MR 0378456 (51:14624)
  • [La05] E. LANDAU, "Sur quelques théorèmes de M. Petrovic relatifs aux zéros des fonctions analytiques," Bull. Soc. Math. France, v. 33, 1905, pp. 251-261. 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, v. 7, 1960, pp. 98-100. MR 0124467 (23:A1779)
  • [Ma64] K. MAHLER, "An inequality for the discriminant of a polynomial," Michigan Math. J., v. 11, 1964, pp. 257-262. MR 0166188 (29:3465)
  • [Mi74] M. MIGNOTTE, "An inequality about factors of polynomials," Math. Comp., v. 28, 1974, pp. 1153-1157. MR 0354624 (50:7102)
  • [Mi76] M. MIGNOTTE, "Some problems about polynomials," Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, August 1976, pp. 227-228.
  • [Mn49] M. MARDEN, The Geometry of the Zeros of a Polynomial in a Complex Variable, Math. Surveys, no. 3, Amer. Math. Soc., Providence, R. I., 1949. MR 0031114 (11:101i)
  • [Ob63] N. OBRESCHKOFF, Verteilung und Berechnung der Nullstellen Reeller Polynome, VEB Deutscher Verlag, Berlin, 1963, MR 0164003 (29:1302)
  • [Ru76] S. M. RUMP, "Isolierung der reellen Nullstellen algebraischer Polynome," Bericht der Arbeitsgruppe Computer Algebra, Universität Kaiserslautern, v. 10, 1976, 121 pp.
  • [Sm72] W. M. SCHMIDT, Approximation to Algebraic Numbers, Monographie 19 de l'Enseignement Mathématique, Genève, 1972. MR 0344203 (49:8943)
  • [Sn57] T. SCHNEIDER, Einführung in die Transzendenten Zahlen, Springer-Verlag, Berlin, 1957. MR 0086842 (19:252f)
  • [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: https://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

American Mathematical Society