Efficient Computation of the Characteristic Polynomial

Details Efficient Computation of the Characteristic Polynomial Efficient Computation of the Characteristic Polynomial

2005-01-25

arxiv.org/abs/cs/0501074v2

Computer Science

Symbolic Computation

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Efficient Computation of the Characteristic Polynomial does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Computation of the Characteristic Polynomial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Computation of the Characteristic Polynomial will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-513158