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$?