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$?
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:
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)$.
