Computing the characteristic polynomial of real sparse matrix

Given a generic sparse matrix $A \in \mathbb{R}^{n\times n}$ with m << n (correction: $m \ll n^2$) non-zero elements (typically $m \in {\cal O}(n)$). $A$ is generic in the sense that it has no specific properties (e.g. positive definiteness), and no structure (e.g. bandedness) is assumed.

What are some of the good numerical methods to compute either the characteristic polynomial or the minimal polynomial of $A$?

-
Sounds like you want to compute all the eigenvalues. Why do you want the polynomial and how do you want it expressed? The monomial basis is extremely ill-conditioned, so the coefficients likely cannot be stably computed in finite precision arithmetic. – Jed Brown Mar 9 '12 at 15:56
@JedBrown more of a contemplation. In my answer to this question I gave an algebraic method to inverting a matrix, which is well-known in computer algebra (e.g matrices over commutative rings and fields). I want to know if I could use it for numerical matrices. Please note that, for this question purposes, I'm interested in numerical methods for finding the characteristic/minimal polynomial rather than inverse. – user182 Mar 9 '12 at 19:19

If $O(n^3)$ complexity is not a stopper then you might want to look at Danilevskii method. It is pretty well-known in Russian literature on numerical linear algebra, but there's not much information in English. You can start from this link.

The idea is rather straightforward: the matrix is gradually reduced to Frobenius normal form by "Gaussian elimination-like" similarity transformations. If you don't find the information I can make the algorithm more elaborate.

-

You could use a numerical method like QR Factorization or Power Method and its realtives (inverse power etc) to compute the eigenvalues of your generic matrix. After that, you can compute your characteristic polynomial by factorization as: (λ-λ1)(λ-λ2)...(λ-λn)=0 where λi are the computed eigenvalues. Here is a short presentation about power and QR methods:

QR-Power

-

By the way: Did you want to say that you have $m \ll O(n^2)$ entries? If indeed $m \ll O(n)$ then the majority of rows and columns will be completely empty and it is likely that the characteristic polynomial is in fact not of degree $n$ but of degree $O(m)$.

-
 Ops. No. I meant to say $m \ll n^2,$ i.e. $m \in {\cal O}(n)$. Sorry about that. – user182 Mar 10 '12 at 17:12