Two-level Toeplitz preconditioning: approximation results for matrices and functions

Large 2-level Toeplitz systems arise in a variety of applications (see, e.g., [R. H. Chan and M. Ng, SIAM Rev., 38 (1996), pp. 427-482]) for which efficient numerical methods for their solution are required. Some successful numerical techniques need the explicit knowledge of the generating function f of the considered system Tn(f)x = b, an assumption that usually is not fulfilled in real applications. In this paper we analyze and complete the procedure proposed in [D. Noutsas, S. Serra Capizzano, and P. Vassalos, Numer. Linear Algebra Appl., 12 (2005), pp. 231-239] for the 2-level case. In such a way, from the knowledge of the coefficients of Tn(f), we determine optimal preconditioning strategies for the solution of our systems. Finally, some numerical experiments are performed and discussed in connection with our theoretical analysis.