A Phase Error Analysis of Multigrid Methods for Hyperbolic Equations

In this research, we study the effects of the coarse grid correction process on multigrid convergence for hyperbolic problems in one and two dimensions. We approach this from the perspective of phase error, which allows us to exploit the hyperbolic nature of the underlying PDE. In particular, we consider three combinations of coarse grid operators and coarse grid solution approaches: (1) inexact coarse grid solve, direct discretization, (2) exact coarse grid solve, direct discretization, and (3) exact coarse grid solve, Galerkin coarse grid operator. For all these approaches, we show that the convergence behavior of multigrid can be precisely described by the phase error analysis of the coarse grid correction matrix, and we verify our results by numerical examples in 1D and 2D.

One dimension

Inexact coarse grid solve, direct discretization coarse grid matrix

The coarse grid problem is solved by a few steps of smoothing. The idea is to accelerate error propagation out of the domain by taking larger time steps on coarser grids.

Phase errors (dispersion) given by a 3-level multigrid V-cycle at iteration=0, 20, 40, and 60.

Exact coarse grid solve, direct discretization coarse grid matrix

The coarse grid problem is solved exactly as in the elliptic case.

The coarse grid error (purple) when compared to the fine grid error (blue) is shifted by 1/2 grid point to the left due to phase error. Hence the error after coarse grid correction (green) is not invisibly small.

Exact coarse grid solve, Galerkin coarse grid matrix

The coarse grid problem is solved exactly and the coarse grid matrix is obtain from the Galerkin process.

There is no phase shift in the coarse grid error. Also, there is no visible oscillation in the error after coarse grid correction.

Two dimensions

Inexact coarse grid solve, direct discretization coarse grid matrix

Phase errors (dispersion) given by a 3-level multigrid V-cycle at iteration=0, 10, 20, and 30.

Exact coarse grid solve, direct discretization coarse grid matrix

The coarse grid errors are shifted behind the direction of the flow.

Exact coarse grid solve, direct discretization coarse grid matrix

The coarse grid errors match accurately with the fine grid errors.

Numerical results

Inexact = inexact coarse grid solve, direct discretization coarse grid matrix
Non-Galerkin = exact coarse grid solve, direct discretization coarse grid matrix
Galerkin = exact coarse grid solve, Galerkin coarse grid matrix

Number of two-grid V-cycles.

h	Inexact	Non-Galerkin	Galerkin
1/32	31	13	8
1/64	44	9	5
1/128	73	6	3
1/256	141	5	3

The number of V-cycles taken by the inexact coarse grid correction increases as the mesh size decreases. Also, the convergence is rather slow due to phase error. Both non-Galerkin and Galerkin approaches, which use exact coarse grid solve, show much better convergence. However, due to phase error, the non-Galerkin approach is less efficient than the Galerkin approach.

Example 2: 2D wave equation

Number of two-grid V-cycles.

	Entering flow			Recirculating flow
h	Inexact	Non-Galerkin	Galerkin	Inexact	Non-Galerkin	Galerkin
1/32	28	13	7	63	14	6
1/64	41	13	5	72	14	6
1/128	70	11	5	84	14	7
1/256	134	9	5	>100	14	8

The convergence of the inexact approach is slow due to dispersion effect. The convergence of the non-Galerkin and Galerkin approaches is shown to be insensitive to the mesh size.