Efficient Computation of the Characteristic PolynomialReportar como inadecuado

Efficient Computation of the Characteristic Polynomial - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LMC - IMAG - Laboratoire de Modélisation et Calcul 2 CIS - Department of Computer and Information Sciences Newark

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.

Keywords : characteristic polynomial over finite fields characteristic polynomial of integer matrices

Autor: Jean-Guillaume Dumas - Clément Pernet - Zhendong Wan -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados