A preconditioning proposal for ill-conditioned Hermitian two-level Toeplitz systems

Large 2-level Toeplitz systems arise in many applications and thus an efficient strategy for their solution is often needed. The already known methods require the explicit knowledge of the generating function ƒ of the considered system Tnm(ƒ)x=b, an assumption that usually is not fulfilled in real applications. In this paper, we extend to the 2-level case a technique proposed in the literature in such a way that, from the knowledge of the coefficients of Tnm(ƒ), we determine optimal preconditioning strategies for the solution of our systems. More precisely, we propose and analyse an algorithm for the economical computation of minimal features of ƒ that allow us to select optimal preconditioners. Finally, we perform various numerical experiments which fully confirm the effectiveness of the proposed idea.