Constrained minimax approximation and optimal preconditioned for Toeplitz matrices

Raymond H. CHAN*, Ping Tak Peter TANG

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

10 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)353-364
Number of pages12
JournalNumerical Algorithms
Issue number7
Publication statusPublished - Jul 1993
Externally publishedYes


  • conjugate gradients
  • Minimax approximation
  • preconditioner
  • Remez algorithm
  • Toeplitz matrix


Dive into the research topics of 'Constrained minimax approximation and optimal preconditioned for Toeplitz matrices'. Together they form a unique fingerprint.

Cite this