A Modular Algorithm for Computing Characteristic Polynomials over Z.

Simon Lo, Michael Monagan, Allan Wittkopf.

April 6th, at 3:30pm in K9509.


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.