Improving root separation bounds. (January 2018)

• Record Type: Journal Article
• Authors: Herman, Aaron; Hong, Hoon; Tsigaridas, Elias
• Is Part Of: Journal of symbolic computation. Volume 84(2018)
• Page Start: 25
• Page End: 56
• Publication Date: 2018-01
• Subjects: Root separation bounds -- Polynomial roots -- Polynomial systems; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.03.001
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: Let f be a polynomial (or polynomial system) with all simple roots. The root separation of f is the minimum of the pair-wise distances between the complex roots. A root separation bound is a lower bound on the root separation. Finding a root separation bound is a fundamental problem, arising in numerous disciplines. We present two new root separation bounds: one univariate bound, and one multivariate bound. The new bounds improve on the old bounds in two ways: (1) The new bounds are usually significantly bigger (hence better) than the previous bounds. (2) The new bounds scale correctly, unlike the previous bounds. Crucially, the new bounds are not harder to compute than the previous bounds.