Finding eigenvalues of sparse integer matrix

I need to find eigenvalues of a sparse matrix with integer coefficients. I understand in general this is not done by explicitly computing the characteristic polynomial due to numerical instability, but in this case, that shouldn't be a problem? Is there an efficient way to find the polynomial? Is there any befefit from having the coefficients integer at all, or should I just stick to Lanczos algorithm or something similar?

-

2 Answers

Polynomial having integer coefficients is not much better in its roots. You'll still have to use some floating-point math to find roots (or you'll end up with enormous fractions), and this would lead to numerical instability again.

-
The problem with polynomials is that small errors in coefficients turn into huge errors in roots. With integer coefficients that will not happen, so the approach is certainly better than in the case of real matrix. That it is better than a general approach is most likely not true though. –  Karolis Juodelė Apr 5 '13 at 20:57

I came recently upon Bareiss algorithm for computing the determinant of a matrix with integer entries. As suggests Henri Cohen in his "A course on computational algebraic number theory" (page 54 on Google Books), one can reduce computing the characteristic polynomial (its coefficients, that is) to the computation of (matrix dimension)+1 determinants of related matrices with integer entries. If one has exact (although maybe large) integer coefficients of the characteristic polynomial, and good bounds on the eigenvalues obtained, for example, via Gershgorin lemma, one may probably obtain the roots of the characteristic polynomial with high precision using Newton's method, for example.

-
then of course whether this is practical depends on how large the sparse matrix is.. –  Giovanni Rossi Apr 16 '13 at 9:11