Efficient computation of the characteristic polynomial

DOI10.1145/1073884.1073905zbMATH Open1360.65123arXivcs/0501074OpenAlexW1965506160MaRDI QIDQ5262755FDOQ5262755

Jean-Guillaume Dumas, Zhendong Wan, Clément Pernet

Publication date: 16 July 2015

Published in: Proceedings of the 2005 international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/cs/0501074

Recommendations

• Calculation of the characteristic polynomial of a matrix
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• Faster algorithms for the characteristic polynomial
• Computing characteristic polynomials of matrices of structured polynomials
• A modular algorithm for computing the characteristic polynomial of an integer matrix in Maple

zbMATH Keywords

minimal polynomialintegercharacteristic polynomialfinite fieldMagmaprobabilistic algorithmKeller-Gehrig

Mathematics Subject Classification ID

Matrices over special rings (quaternions, finite fields, etc.) (15B33) Matrices of integers (15B36)

Cited In (15)

• Title not available (Why is that?)
• Efficient parallel computation of the characteristic polynomial of a sparse, separable matrix
• Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs
• List decoding of number field codes
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• Title not available (Why is that?)
• On the permanental polynomials of matrices
• Finding Hamming weights without looking at truth tables
• Determinisability of unary weighted automata over the rational numbers
• Fast recursive computation of Krawtchouk polynomials
• Efficient algorithms for computing the characteristic polynomial in a domain
• The complexity of the characteristic and the minimal polynomial.
• Spectral norm of a symmetric tensor and its computation
• Computational complexity of \(k\)-block conjugacy
• Fast algorithms for the characteristic polynomial

This page was built for publication: Efficient computation of the characteristic polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262755)