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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.