Efficient Computation of the Characteristic Polynomial
<|reference_start|>Efficient Computation of the Characteristic Polynomial: This article deals with the computation of the characteristic polynomial of dense matrices over small finite fields and over the integers. We first present two algorithms for the 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.<|reference_end|>
@article{dumas2005efficient,
    title={Efficient Computation of the Characteristic Polynomial},
    author={Jean-Guillaume Dumas (LMC - IMAG), Cl'ement Pernet (LMC - IMAG),
  Zhendong Wan (CIS)},
    journal={arXiv preprint arXiv:cs/0501074},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0501074},
    primaryClass={cs.SC}
}