Toeplitz approximate inverse preconditioner for banded Toeplitz matrices (Q1334243)

The authors consider the system of linear algebraic equations with a banded Toeplitz \(n \times n\) matrix \(T\) with bandwidth \(\beta\). Because of problematical stability of fast direct methods, the attention is concentrated on conjugate gradients, especially on finding efficient preconditioners. The authors introduce a preconditioner whose inverse is a Toeplitz matrix \(M\) itself such that \(MT = I + R\) (or \(M(T^*T) = I + R\)) and an estimate for \(\text{rank}(R)\) is given for various types of the matrix \(T\) (Hermitian and positive definite, non-Hermitian and block Toeplitz matrices). For forming \(M\), the matrix \(T\) is firstly embedded into an \((n + \beta) \times (n + \beta)\) circulant matrix \(C\). The estimate depends on \(\beta\) and \(\nu\), where \(\nu\) is the number of nonpositive eigenvalues of \(C\). For a Hermitian and positive definite matrix \(T\) it is \(\text{rank} (R) \leq \beta + \nu\). Numerical experiments complete the paper.