Constrained minimax approximation and optimal preconditioned for Toeplitz matrices

A good preconditioner is extremely important in order for the conjugate gradients method to converge quickly. In the case of Toeplitz matrices, a number of recent studies were made to relate approximation of functions to good preconditioners. In this paper, we present a new result relating the quality of the Toeplitz preconditioner C for the Toeplitz matrix T to the Chebyshev norm ∥(f- g)/f∥_∞, where f and g are the generating functions for T and C, respectively. In particular, the construction of band-Toeplitz preconditioners becomes a linear minimax approximation problem. The case when f has zeros (but is nonnegative) is especially interesting and the corresponding approximation problem becomes constrained. We show how the Remez algorithm can be modified to handle the constraints. Numerical experiments confirming the theoretical results are presented.