Efficient algorithms for computing the nearest polynomial with a real root and related problems
Markus A. Hitz, Erich Kaltofen, Y. N. Lakshman · 1999
this paper is very special: nearness is measured coefficient-wise, i.e., in infinity norm. And the root locus is parametric, namely, the real axis. All previous solutions seem to have required that for parametric root locations the distance expression is at least differentiable: they and we have proven results using the Euclidean distance. Infinity norm leads us [7] to linear programming problems, whose parametric versions we do not know how to solve efficiently. We can solve our specific problem efficiently, that is in polynomial-time in the degree and input length, because an explicit expression for the distance to the nearest polynomial with a real root can be derived from a result in [17], or alternatively by eigenvalue analysis of companion matrices in [15, Section 4.2]. The expression involves absolute values, but by a stroke of luck can be minimized over the entire real axis.