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)=(2(1-\cos(\theta-\tilde{\theta})))^d$ are studied. The function $f$ is a real non-negative function with a zero of order $2d$ 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)=(2(1-\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.