On finding multiplicities of characteristic polynomial factors of black-box matrices

Jean-Guillaume Dumas (1) , Clément Pernet (2) , B. David Saunders (3)

1 CASYS - Calculs Algébriques et Systèmes Dynamiques
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
3 CIS - Department of Computer and Information Sciences [Newark]

We present algorithms and heuristics to compute the characteristic polynomial of a matrix given its minimal polynomial. The matrix is represented as a black-box, i.e., by a function to compute its matrix-vector product. The methods apply to matrices either over the integers or over a large enough finite field. Experiments show that these methods perform efficiently in practice. Combined in an adaptive strategy, these algorithms reach significant speedups in practice for some integer matrices arising in an application from graph theory.

Mots clés: Minimal polynomial; Characteristic polynomial; Multiplicity

Domaines: Calcul formel [cs.SC]

Jean-Guillaume Dumas, Clément Pernet, B. David Saunders. On finding multiplicities of characteristic polynomial factors of black-box matrices. ISSAC 2009 - International Symposium on Symbolic and Algebraic Computation, Jul 2009, Séoul, South Korea. pp.135-142, ⟨10.1145/1576702.1576723⟩. ⟨hal-00357262v2⟩