Numerically reliable computation of characteristic polynomials

In this paper, we present an algorithm for computing the characteristic polynomial of the pencil (A Gamma sE). It is shown that after a preliminary reduction of the matrices A and E to, respectively, an upper Hessenberg and an upper triangular matrix, the problem of computing the characteristic polynomial is transformed to the solution of certain triangular systems of linear algebraic equations. We show that the computed characteristic polynomial corresponds exactly to perturbed matrices A + DeltaA and E + DeltaE and we derive bounds for DeltaA and DeltaE. We also suggest how to improve on this backward error via iterative refinement.