In this paper, we propose a structured bisection method with adaptive randomized
sampling for finding selected or all of the eigenvalues of certain real symmetric matrices A. For A with
a low-rank property, we construct a hierarchically semiseparable (HSS) approximation and show how
to quickly evaluate and update its inertia in the bisection method. Unlike some existing randomized
HSS constructions, the methods here do not require the knowledge of the off-diagonal (numerical)
ranks in advance. Moreover, for A with a weak rank property or slowly decaying off-diagonal singular
values, we show an idea for aggressive low-rank inertia evaluation, which means that a compact HSS
approximation can preserve the inertia for certain shifts. This is analytically justified for a special
case, and numerically shown for more general ones. A generalized LDL factorization of the HSS
approximation is then designed for the fast evaluation of the inertia. A significant advantage over
standard LDL factorizations is that the HSS LDL factorization (and thus the inertia) of A − sI
can be quickly updated with multiple shifts s in bisection. The factorization with each new shift
can reuse about 60% of the work. As an important application, the structured eigensolver can
be applied to symmetric Toeplitz matrices, and the cost to find one eigenvalue is nearly linear in
the order of the matrix. The numerical examples demonstrate the efficiency and the accuracy of
our methods, especially the benefit of low-rank inertia evaluations. The ideas and methods can
be potentially adapted to other HSS computations where shifts are involved and to more problems
without a significant low-rank property.