A Boundary-Layer Preconditioner for Singularly Perturbed Convection Diffusion

Scott MacLachlan, Niall Madden, Thái Anh NhanSIAM J. Matrix Anal. Appl 2021

TL;DR

This paper introduces a novel "boundary-layer" preconditioner designed to efficiently solve systems of linear equations arising from the numerical discretization of singularly perturbed convection-diffusion problems. By specifically tailoring the preconditioner to the unique structure of these problems, particularly in regions with thin layers, the authors achieve significant speedups over standard solvers, making complex simulations more tractable.

What Problem Does This Paper Address?

Many real-world phenomena, from fluid dynamics to heat transfer, are modeled by singularly perturbed differential equations. These equations often exhibit "boundary layers" or "interior layers" where the solution changes very rapidly over a small region. Numerically solving these problems is challenging because standard discretization methods require an impractically large number of grid points to accurately capture these layers. While layer-adapted meshes help resolve the solution, the resulting linear systems become ill-conditioned, making them difficult and slow to solve with traditional iterative or direct methods. This paper addresses the critical bottleneck of efficiently solving these ill-conditioned linear systems that arise from discretizing convection-diffusion problems on layer-adapted meshes.

Methods

The core of this paper is the development of a "boundary-layer" preconditioner. The authors first discretize the convection-diffusion equation using an upwind finite-difference scheme on a "Shishkin mesh," which is a type of layer-adapted mesh that is very fine in the layer regions and coarser elsewhere.

The key innovation lies in how they construct the preconditioner. Instead of treating the entire discretized system uniformly, they partition the system matrix into blocks corresponding to different regions of the mesh: a corner region, two edge regions, and an interior region. The preconditioner is then designed to exploit the different behaviors of the solution in these regions.

  • One-Dimensional Case: For the 1D problem, they propose an idealized block preconditioner that leverages the structure of the upwind discretization. They provide a rigorous theoretical analysis, proving an $\epsilon$-robust bound on the condition number of the preconditioned system, meaning the condition number doesn't degrade significantly as the perturbation parameter $\epsilon$ becomes very small.
  • Two-Dimensional Case: In 2D, the problem becomes more complex due to anisotropic diffusion and convection. They extend the block partitioning idea, treating the interior and edge regions with specialized approximations (often involving line solves or approximations of upper-triangular parts). For the critical corner region, where both diffusion and convection are significant, they employ a multigrid method, specifically a semi-coarsening multigrid for one type of layer and a full-coarsening multigrid for another.

Datasets

The paper does not introduce new datasets. Instead, it uses manufactured solutions to test the performance of their proposed preconditioner on representative one- and two-dimensional convection-diffusion problems. These manufactured solutions allow for precise error estimation by comparing the computed solution to the known exact solution.

Key Insights and Ideas

  • Layer-Specific Preconditioning is Crucial: The most significant insight is that a "one-size-fits-all" approach to preconditioning is insufficient for singularly perturbed convection-diffusion problems. Tailoring the preconditioner to the specific behavior of the solution in different mesh regions (interior, edge, corner) is essential for efficiency.
  • Block Structure Exploitation: Partitioning the discretized system into blocks corresponding to mesh regions and designing specialized solvers for each block is a powerful strategy. This allows for efficient handling of both the dominant convection terms in the interior and the complex interplay of diffusion and convection in the layer regions.
  • Multigrid for Corner Regions: The corner regions in 2D problems, where multiple layers intersect, pose a particular challenge. The paper demonstrates that multigrid methods, adapted for anisotropic operators and specific mesh structures, are effective in efficiently solving the sub-problems associated with these regions.
  • Theoretical Guarantees: The rigorous theoretical analysis for the 1D case, providing an $\epsilon$-robust condition number bound, is a key contribution, offering strong theoretical backing for the practical performance observed.

Key Results

  • Significant Speedups: The proposed boundary-layer preconditioner, when used with GMRES (Generalized Minimum Residual method), achieves substantial speedups over standard sparse direct solvers (like UMFPACK). For example, in 2D, they report speedups of up to 40x for representative problems on large meshes (1024x1024).
  • Robustness: The iteration counts for the preconditioned GMRES solver remain remarkably low and stable, even for very small perturbation parameters ($\epsilon$) and large mesh sizes (N). This demonstrates the parameter-robustness of their approach.
  • Accuracy: The numerical results show that the preconditioned solver achieves high accuracy, often matching the results of direct solvers to at least 3 digits, and frequently more.
  • Efficiency: For problems with $\epsilon < 10^{-5}$ on a 1024x1024 mesh, the total solution time (including preconditioner setup) is less than 1 second.

Limitations and Future Work

  • Focus on Boundary Layers: The current work primarily focuses on problems with boundary layers. The authors acknowledge that extending the techniques to interior layers or non-regular domains would require further generalization of the region definitions and corresponding solution strategies.
  • Three-Dimensional Problems: The extension of these preconditioners to three-dimensional problems is identified as a significant area for future work. This would involve handling a larger number of region types and potentially more complex multigrid strategies.
  • Nonlinear Problems: The paper focuses on linear convection-diffusion problems. Extending the approach to nonlinear problems, such as Navier-Stokes flow, is also suggested as a future research direction.
  • Theoretical Bounds in 2D: While the 1D case has a proven $\epsilon$-robust bound, the theoretical analysis for the 2D case is less comprehensive, with weaker bounds presented. Further theoretical investigation into the 2D case would be beneficial.

Summary updated

Abstract

Motivated by a wide range of real-world problems whose solutions exhibit boundary and interior layers, the numerical analysis of discretizations of singularly perturbed differential equations is an established sub-discipline within the study of the numerical approximation of solutions to differential equations. Consequently, much is known about how to accurately and stably discretize such equations on \textit{a priori} adapted meshes, in order to properly resolve the layer structure present in their continuum solutions. However, despite being a key step in the numerical simulation process, much less is known about the efficient and accurate solution of the linear systems of equations corresponding to these discretizations. In this paper, we discuss problems associated with the application of direct solvers to these discretizations, and we propose a preconditioning strategy that is tuned to the matrix structure induced by using layer-adapted meshes for convection-diffusion equations, proving a strong condition-number bound on the preconditioned system in one spatial dimension, and a weaker bound in two spatial dimensions. Numerical results confirm the efficiency of the resulting preconditioners in one and two dimensions, with time-to-solution of less than one second for representative problems on $1024\times 1024$ meshes and up to $40\times$ speedup over standard sparse direct solvers.
BibTeX
@article{maclachlan2021boundary,
  author = {Scott MacLachlan and Niall Madden and Thái Anh Nhan},
  title = {{A Boundary-Layer Preconditioner for Singularly Perturbed Convection Diffusion}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2021},
}
Figure