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: Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, v.18 n.3, p.147-150, March 1984 [doi>10.1016/0020-0190(84)90018-8]
• 4: Jean Guillaume Dumas , Thierry Gautier , Clément Pernet, Finite field linear algebra subroutines, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.63-74, July 07-10, 2002, Lille, France [doi>10.1145/780506.780515]
• 5: Jean-Guillaume Dumas , Pascal Giorgi , Clément Pernet, FFPACK: finite field linear algebra package, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.119-126, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005304]
• 6: Jean-Guillaume Dumas , B. David Saunders , Gilles Villard, On efficient sparse integer matrix Smith normal form computations, Journal of Symbolic Computation, v.32 n.1, p.71-99, July 2001 [doi>10.1006/jsco.2001.0451]
• 7: Wayne Eberly, Reliable Krylov-based algorithms for matrix null space and rank, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.127-134, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005305]
• 8: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 9: Mark Giesbrecht , Arne Storjohann, Computing rational forms of integer matrices, Journal of Symbolic Computation, v.34 n.3, p.157-172, September 2002 [doi>10.1006/jsco.2002.0554]
• 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: Erich Kaltofen, On computing determinants of matrices without divisions, Papers from the international symposium on Symbolic and algebraic computation, p.342-349, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143350]
• 14: Erich Kaltofen , Gilles Villard, On the complexity of computing determinants, Computational Complexity, v.13 n.3-4, p.91-130, February 2005 [doi>10.1007/s00037-004-0185-3]
• 15: Walter Keller-Gehrig, Fast algorithms for the characteristic polynomial, Theoretical Computer Science, v.36 n.2-3, p.309-317, June 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 , J. L. Walsh, Field testing for cosmic ray soft errors in semiconductor memories, IBM Journal of Research and Development, v.40 n.1, p.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: Clément Pernet , Zhendong Wan, LU based algorithms for characteristic polynomial over a finite field, ACM SIGSAM Bulletin, v.37 n.3, September 2003 [doi>10.1145/990353.990367]
• 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

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms, Experimentation

Keywords:
Keller-Gehrig, Magma, characteristic polynomial, finite field, integer, minimal polynomial, probabilistic algorithm