In the software Regina what I do is apply [Descartes Rule of Signs][1] on the characteristic polynomial.  The algorithm for computing the determinant we use has complexity of the order of $n^4$, but it seems to work quite effectively for the signature computations we've been doing so far. 

  [1]: http://en.wikipedia.org/wiki/Descartes%2527_rule_of_signs