A divide-and-conquer approach to the evaluation of the characteristic polynomial of a symmetric tridiagonal matrix

In this paper, we present a divide-and-conquer approach to the evaluation of the characteristic polynomial of a symmetric tridiagonal matrix for a real argument. Here, the problem is partitioned into smaller parts which are solved and these solutions are then combined to form the solution to the original problem. We give the update equations for the characteristic polynomial and certain auxiliary polynomials used in the computation. We show that the three-term recurrence is a specific case of our equations. Furthermore, this set of recursions can be implemented on a regular tree structure. If the concurrency exhibited by order is increased by one at every step.