I have a $n \times n$ matrix, for which i need to calculate the characteristic polynomial. The matrix is over $GF(2)$, and $n \approx 10^4$. However the matrix is very sparse, with around $ n $ non zero entries.
Is there a computer algebra system with sparse matrix structures capable of handling the calculation of the characteristic polynomial? What would be the most promising system to try?
Best Answer
I have been experimenting with Fermat to see how this goes. For a 5000x5000 test case I made up, it computed the minimal polynomial (Wiedemann algorithm) in about 30 seconds, then using that, the characteristic poly in about 22 minutes. It used about 45 meg of RAM. This is on a three year old IMac.
I am the author of Fermat. You can find my email online, and the Fermat web site.
To the Maple person, James:
I tried your code in Maple and the kernel crashed, memory allocation failed. (My IMac has 4 gig RAM.)
Does your example really have only 1 entry per row? The test case I quote above with Fermat has about two per row. With one per row, I get the answer in 0.92 seconds.