Efficient computation of the characteristic polynomial

DOI10.1145/1073884.1073905MaRDI QIDQ5262755zbMATHOpenAlexFDO

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

Publication date 16 July 2015

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

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

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)

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.

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

Cited in

(24)

• On the permanental polynomials of matrices
• An accurate and efficient algorithm for the computation of the characteristic polynomial of a general square matrix
• Efficient algorithms for computing the characteristic polynomial in a domain
• Efficient parallel computation of the characteristic polynomial of a sparse, separable matrix
• Computing characteristic polynomials of matrices of structured polynomials
• scientific article; zbMATH DE number 3958571 (Why is no real title available?)
• Determinisability of unary weighted automata over the rational numbers
• The complexity of the characteristic and the minimal polynomial.
• Finding Hamming weights without looking at truth tables
• Computational complexity of \(k\)-block conjugacy
• Characteristic polynomials of \(p\)-adic matrices
• Fast algorithms for the characteristic polynomial
• Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs
• A modular algorithm for computing the characteristic polynomial of an integer matrix in Maple
• scientific article; zbMATH DE number 4151735 (Why is no real title available?)
• Fast recursive computation of Krawtchouk polynomials
• Spectral norm of a symmetric tensor and its computation
• Bounds on the coefficients of the characteristic and minimal polynomials
• On finding multiplicities of characteristic polynomial factors of black-box matrices
• Calculation of the characteristic polynomial of a matrix
• Faster algorithms for the characteristic polynomial
• List decoding of number field codes
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic

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)