A direct solver for solving systems of linear equations with banded ill-conditioned Toeplitz matrices

In this paper, the banded Toeplitz matrices generated by f(\theta)=(۲(۱-\cos(\theta-\tilde{\theta})))^d are studied. The function f is a real non-negative function with a zero of order ۲d at \tilde{\theta} and the generated matrices are ill-conditioned Hermitian positive definite. We show that these banded Toeplitz matrices are similar to the banded real symmetric positive definite Toeplitz matrices that are generated by f(\theta)=(۲(۱-\cos(\theta)))^d.  A fast direct solver is proposed to compute the inverse of these real matrices. Numerical experiments show that our proposed method is faster and more stable than the stable Levinson algorithm.

Keywords:

Toeplitz matrices , fast Toeplitz solver , Levinson algorithm