Efficient computation of the characteristic polynomial

ABSTRACT

We deal with the computation of the characteristic polynomial of dense matrices over word size finite fields and over the integers. We first present two algorithms for finite fields: one is based on Krylov iterates and Gaussian elimination. We compare it to an improvement of the second algorithm of Keller-Gehrig. Then we show that a generalization of Keller-Gehrig's third algorithm could improve both complexity and computational time. We use these results as a basis for the computation of the characteristic polynomial of integer matrices. We first use early termination and Chinese remaindering for dense matrices. Then a probabilistic approach, based on integer minimal polynomial and Hensel factorization, is particularly well suited to sparse and/or structured matrices.

References

1. J. Abdeljaoued and G. I. Malaschonok. Efficient algorithms for computing the characteristic polynomial in a domain. J. of Pure and Applied Algebra, 156:127--145, 2001.
2. W. Baur and V. Strassen. The complexity of partial derivatives. Theor. Computer Science, 22(3):317--330, 1983.
3. S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Process. Lett., 18(3):147--150, 1984.
4. J.-G. Dumas, T. Gautier, and C. Pernet. Finite field linear algebra subroutines. In T. Mora, editor, ISSAC'2002. ACM Press, New York, July 2002.
5. J.-G. Dumas, P. Giorgi, and C. Pernet. FFPACK: Finite field linear algebra package. In Gutierrez 2004:ISSAC.
6. J.-G. Dumas, B. D. Saunders, and G. Villard. On efficient sparse integer matrix Smith normal form computations. J. Symb. Comp., 32(1/2):71--99, July--Aug. 2001.
7. W. Eberly. Reliable krylov-based algorithms for matrix null space and rank. In Gutierrez 2004:ISSAC.
8. J. v. Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press. 1999.
9. M. Giesbrecht and A. Storjohann. Rational forms of integer matrices. J. Symb. Comp., 34(3):157--172, 2002.
10. J. Gutierrez, editor. ISSAC'2004. Santander, Spain. ACM Press, New York, July 2004.
11. A. Householder. The Theory of Matrices in Numerical Analysis. Blaisdell, Waltham, Mass., 1964.
12. O. H. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. J. of Algorithms, 3(1):45--56, Mar. 1982.
13. E. Kaltofen. On computing determinants of matrices without divisions. In P. S. Wang, editor, ISSAC'92. ACM Press, New York, July 1992.
14. E. Kaltofen and G. Villard. On the complexity of computing determinants. Comp. Complexity, 13:91--130, 2004.
15. W. Keller-Gehrig. Fast algorithms for the characteristic polynomial. Theoretical computer science, 36:309--317, 1985.
16. H. Lombardi and J. Abdeljaoued. Méthodes matricielles - Introduction à la complexité algébrique. Springer, 2004.
17. T. J. O'Gorman, J. M. Ross, A. H. Taber, J. F. Ziegler, H. P. Muhlfeld, C. J. Montrose, H. W. Curtis, and J. L. Walsh. Field testing for cosmic ray soft errors in semiconductor memories. IBM J. of R&D, 40(1):41--50, Jan. 1996.
18. C. Pernet. Calcul du polynôme caractéristique sur des corps finis. Master's thesis, U. J. Fourier, June 2003. www-lmc.imag.fr/lmc-mosaic/Clement.Pernet.
19. C. Pernet and Z. Wan. L U based algorithms for characteristic polynomial over a finite field. SIGSAM Bull., 37(3):83--84, 2003. Poster available at www-lmc.imag.fr/lmc-mosaic/Clement.Pernet.
20. A. Steel. Personnal communication. 2005
21. A. Storjohann. Algorithms for Matrix Canonical Forms. PhD thesis, Institut für Wissenschaftliches Rechnen, ETH-Zentrum, Zürich, Switzerland, Nov. 2000.
22. A. Storjohann. Computing the frobenius form of a sparse integer matrix. Manuscript, Apr. 2000.
23. G. Villard. Computing the Frobenius normal form of a sparse matrix. In V. G. Ganzha, E. W. Mayr, and E. V. Vorozhtsov, editors, CASC'00, Oct. 2000.

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

• Mathematics of computing

  • Mathematical software