Discrete Fourier analysis of multigrid algorithms

Jacobus J.W. van der Vegt, Sander Rhebergen

    Research output: Book/ReportReportProfessional

    138 Downloads (Pure)


    The main topic of this report is a detailed discussion of the discrete Fourier multilevel analysis of multigrid algorithms. First, a brief overview of multigrid methods is given for discretizations of both linear and nonlinear partial differential equations. Special attention is given to the hp-Multigrid as Smoother algorithm, which is a new algorithm suitable for higher order accurate discontinuous Galerkin discretizations of advection dominated flows. In order to analyze the performance of the multigrid algorithms the error transformation operator for several linear multigrid algorithms are derived. The operator norm and spectral radius of the multigrid error transformation are then computed using discrete Fourier analysis. First, the main operations in the discrete Fourier analysis are defined, including the aliasing of modes. Next, the Fourier symbol of the multigrid operators is computed and used to obtain the Fourier symbol of the multigrid error transformation operator. In the multilevel analysis, two and three level h-multigrid, both for uniformly and semi-coarsened meshes, are considered, and also the analysis of the hp-Multigrid as Smoother algorithm for three polynomial levels and three uniformly and semi-coarsened meshes. The report concludes with a discussion of the multigrid operator norm and spectral radius. In the appendix some useful auxiliary results are summarized.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente, Department of Applied Mathematics
    Number of pages76
    Publication statusPublished - Oct 2011

    Publication series

    NameMemorandum / Department of Applied Mathematics
    PublisherUniversity of Twente, Department of Applied Mathematics
    ISSN (Print)1874-4850
    ISSN (Electronic)1874-4850


    • EWI-20656
    • Runge-Kutta methods
    • Higher order accurate discretizations
    • Discontinuous Galerkin methods
    • Multigrid algorithms
    • Fourier analysis
    • Multi-level analysis
    • IR-78250
    • METIS-279713
    • MSC-76M10
    • MSC-65M60
    • MSC-65M55
    • Space-time methods

    Cite this