We use a bisection method [B. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, NJ, 1980, p. 51] to compute the eigenvalues of a symmetric -matrix M. The number of negative eigenvalues of is computed via the LDL factorization of . For dense matrices, the LDL factorization is too expensive to yield an efficient eigenvalue algorithm in general, but not so for -matrices. In the special structure of -matrices there is an LDL factorization with linear-polylogarithmic complexity. The bisection method requires only matrix-size independent many iterations to find an eigenvalue up to the desired accuracy, so that an eigenvalue can be found in linear-polylogarithmic time. For all n eigenvalues, flops are needed to compute all eigenvalues with an accuracy . It is also possible to compute only eigenvalues in a specific interval or the jth smallest one. Numerical experiments demonstrate the efficiency of the algorithm, in particular for the case when some interior eigenvalues are required. (A corrected PDF is attached to this article.)