Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real
Dario A. Bini, Victor Ya. Pan · SIAM Journal on Computing · 1998
Surprisingly simple corollaries from the Courant--Fischer minimax characterization theorem enable us to devise a very effective algorithm for the evaluation of a set S interleaving the set E of the eigenvalues of an n X n real symmetric tridiagonal (rst) matrix T n (as well as a point that splits E into two subsets of comparable cardinalities). Furthermore, we extend this algorithm so as to approximate all the n eigenvalues of T n at nearly optimal sequential and parallel cost, that is, at the cost of staying within polylogarithmic factors from the straightforward lower bounds. The resulting improvement of the known processor bound in NC algorithms for the rst-eigenproblem is roughly by factor n. Our approach extends the previous works [M. Ben-Or and P. Tiwari, J. Complexity, 6(1990), pp. 417--442] and [M. Ben-Or et al., SIAM J. Comput., 17(1988), pp. 1081--1092] for the approximation of the zeros of a polynomial having only real zeros, and our algorithm leads to an alternative and simplified derivation of the known record parallel and sequential complexity estimates for the latter problem.