[GAP Forum] Characteristic Polynomials ?

[Gordon Royle]

Does anyone have any recommendations for software for finding  
characteristic polynomials of large sparse matrices?

More precisely, I have a very sparse graph with about 7000 vertices for 
which I wish to find the characteristic polynomial (over the integers).

Both  GAP and Maple appear to have characteristic polynomial routines 
that reach their limit at a few hundred vertices; Magma has an amazing 
routine that manages to get up to 2000-3000 vertices, but it does not 
use sparseness and runs out of memory at that point... NTL also runs 
out of puff at around 1000 vertices.

There are quite a few numerical solvers out there (for calculating the 
eigenvalues of a sparse symmetric matrix), but the numerical linear 
algebraists seem quite cavalier about the MULTIPLICITY of an eigenvalue 
and the packages that I have managed to install (some of them are quite 
complex to install) seem to have complicated user-defined parameters to 
control how multiple eigenvalues are dealt with. I have no 'a priori' 
guesstimate of the maximum multiplicity of an eigenvalue and I don't 
really have a firm understanding of the sensitivity of such a problem 
to numerical inaccuracy, so I am a bit unwilling to use these routines.

Thanks.. (and apologies for not being a 100% GAP question)

Gordon