# 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.
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