A Modular Algorithm for Computing Characteristic Polynomials over Z.
Simon Lo, Michael Monagan, Allan Wittkopf.
Abstract: Let A be an n by n matrix of integers and let c(x) = x^n + ... + c1 x + c0 be the characteristic polynomial of A. We have implemented a modular algorithm for computing c(x). The computation of c(x) mod p is coded in C. It computes c(x) mod p via a Hessenberg matrix in O(n^3) arithmetic operations in Zp. We have implemented the integer arithmetic in Zp using (i) 64 bit integer arithmetic (long long int), (ii) 32 bit integer arithmetic (long int) and (iii) floating point arithmetic. The talk presents some timings of the different C implementations on different machines for a large relatively sparse matrix. The comparison includes Maple's code which is an implementation of the Berkowitz algorithm that does O(n^4) integer operations.