Inverse product Toeplitz preconditioners for non-Hermitian Toeplitz systems (Q973856): Difference between revisions

Preconditioners are proposed for systems with Toeplitz matrices \(T(f)\) whose symbol \(f\) is either rational or of the form \(f(z)=p_L(z)p_U(z)h(z)\) where \(p_L(z)=\prod(1-\overline{z}_kz)\) and \(p_U(z)=\prod(1-z_l/z)\) with \(|z_j|=1\) and \(h(z)\neq0\) on \(|z|=1\). The Toeplitz matrices \(T(p_L)\), and \(T(p_U)\) are lower and upper triangular respectively. A preconditioner is then \(P=T(1/h)[T(p_U)]^{-1}[T(p_L)]^{-1}\). It is shown that \(PT(f)=I+S+L\) with \(\|S\|\) small and \(L\) has low rank (i.e.\ independent of the size of \(T(f)\)) which means that its eigenvalues and singular values are clustered around 1. If \(f\) is rational without zeros on \(|z|=1\), it is split into a stable and an unstable part \(f=\frac{l_2}{l_1}+\frac{u_2}{u_1}\) with the zeros of \(l_1\) and \(u_1\) outside and inside the unit disk respectively so that \(T(l_i)\) and \(T(u_i)\) are lower and upper triangular respectively. Writing \(T(f)=[T(l_1)]^{-1}T(l_2u_1+l_1u_2)[T(u_1)]^{-1}\), the first and the last matrices being triangular, one basically needs to solve and precondition a system with the middle matrix which is band Toeplitz. A preconditioner for that system is based on \textit{T. Ku} and \textit{C.-C. J. Kuo} [SIAM J. Sci. Stat. Comput. 13, No.~6, 1470--1487 (1992; Zbl 0765.65039)]. Some numerical examples illustrate the results.