An asymptotically superior algorithm for computing the characteristic polynomial of a tridiagonal matrix

摘要

The author describes an algorithm for computing the characteristic polynomial of a tridiagonal matrix. It is quite general and consists in the application of the divide-and-conquer technique to the evaluation of a three-term recurrence relation. The algorithm developed requires O(n log/sup 2) arithmetic operations as compared to the classical algorithm that requires O(n/sup 2/) arithmetic operations.