[GAP Forum] Characteristic Polynomials ?

[Dima Pasechnik]

Dear GAP-Forum,
> I have a very sparse graph with about 7000 vertices for 
> which I wish to find the characteristic polynomial (over the integers).
Start by trying to collapse the adjacency matrix using the automorphism
group; the eigenvalues of such a collapsed matrix are in well-understood
correspondence with these of the original one.

Another way to proceed is to compute over GF(p) for p large enough.
Actually, that's where the problem lies - computing in arbitrary
precision arithmetic.
> 
> 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 
Numerical analysts don't care about the full spectrum, so don't hold
your breath hoping that you get the answer.
> 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. 
Try Matlab, if you can get your hands on it; it was possible to get
a fully functional trial version that works for a month or something
like this.
Matlab incorporates ARPACK, one of the better packages you mentioned.

Anyhow, all these packages actually compute few largest eigenvalues of
the matrix A, and certainly you can also get few smallest ones, by
doing few largest ones for -A.

All this is a part of "black-box linear algebra"; one works under
assumption that only the matrix-vector products Av are available, but not
the matrix A itself. A good introduction (and further references) 
to it is in "Modern computer algebra" by v.z.Gathen and Gerhard.

HTH,
Dima