Efficient Computation for Invertibility Sequence of Banded Toeplitz Matrices

Abstract

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\ast 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^{2}n/2+kn$ and a space complexity of $3k^2$ where $n$ is the size of the largest matrix. This enables efficient preprocessing when solving equation systems and inverses of banded Toeplitz matrices.