Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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.

share|improve this answer
    
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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.