Efficient Computation for Invertibility Sequence of Banded Toeplitz Matrices

When solving systems of banded Toeplitz equations or calculating their inverses, it is necessary to determine the invertibility of the matrices beforehand. In this paper, we equate the invertibility of an n-order banded Toeplitz matrix with bandwidth $2k+1$ to that of a small $k*k$ matrix. By utilizing a specially designed algorithm, we compute the invertibility sequence of a class of banded Toeplitz matrices with a time complexity of 5k²n/2+kn and a space complexity of 3k² where n is the size of the largest matrix. This enables efficient preprocessing when solving equation systems and inverses of banded Toeplitz matrices.