Computing Characteristic Polynomials of an Integer Matrix in Maple

Simon Lo, Simon Fraser University

June 15th, 2005 at 3:30pm in K9509.

Abstract: 
Let A be an n by n matrix of integers. We have already presented a Maple
implementation of a modular method for computing the characteristic
polynomial of A using the Hessenberg matrix approach, and we found that
the implementation using double precision floats was always faster than
the implementation using integers.
We present two improvements to improve the running times. The first
improvement is to use a output sensitive probabilistic version of the
modular algorithm that would eliminate the use of a bound for the
largest coefficient. The second improvement is to first try to find a
permutation of the rows and columns of A to convert A into block upper
triangular matrix where it would be easier to compute the characteristic
polynomial. The permutation can be found by finding the strongly
connected components (SCC) of a directed graph G, where G is the graph
whose adjancency matrix is A.
We have also implemented an algorithm by Tarjan to compute the SCC of a
directed graph in Maple in linear time. Our approach of finding
permutations into block upper triangular matrix could also be used to
compute other related problems, such as computing the determinant.