Efficient computation of tr{TR-1} for Toeplitz matrices

An efficient algorithm for the computation of tr{TR-1}, where T and R are Toeplitz matrices and R is also symmetric positive definite, is presented. The method exploits the fact that the trace of TR-1 depends only on the sum of the diagonals of R-1, and not on the whole matrix R-1. To obtain this sum, a fast efficient technique, built upon the Trench algorithm for computing the inverse of a Toeplitz matrix, is developed. The complexity of the algorithm depends on the generation function of matrix R and is O(N In N) for generic functions and O(p ln p) for AR(p) functions.