Multigrid methods for anisotropic BTTB systems

Rainer Fischer, Thomas Huckle

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


Multigrid methods are highly efficient solution techniques for large sparse multilevel Toeplitz systems which are positive definite and ill-conditioned. In this paper, we develop multigrid methods which are especially designed for anisotropic two-level Toeplitz (BTTB) matrices. First, a method is described for systems with anisotropy along coordinate axes as a suitable combination of semicoarsening and full coarsening steps. Although the basic idea is known from the solution of partial differential equations, we present it here in a more formal way using generating functions and their level curves. This enables us not only to prove the optimal convergence of the two-grid method, but also to carry over the results to systems with anisotropy in other directions. We introduce new coordinates in order to describe these more complicated systems in terms of generating functions. This enables us to solve them with the same efficiency. For the two-level method, we present a convergence proof in this more general case.

Original languageEnglish
Pages (from-to)314-334
Number of pages21
JournalLinear Algebra and Its Applications
Issue number2-3
StatePublished - 1 Sep 2006


  • Iterative methods
  • Multigrid methods
  • Multilevel Toeplitz
  • Preconditioners


Dive into the research topics of 'Multigrid methods for anisotropic BTTB systems'. Together they form a unique fingerprint.

Cite this