Downwind numbering: robust multigrid for convection-diffusion problems

doi:10.1016/S0168-9274(96)00067-0

Applied Numerical Mathematics

Volume 23, Issue 1, February 1997, Pages 177-192

https://doi.org/10.1016/S0168-9274(96)00067-0 Get rights and content

Abstract

In the present paper, we introduce and investigate a robust smoothing strategy for convection-diffusion problems in two and three space dimensions without any assumption on the grid structure. The main tool to obtain such a robust smoother for these problems is an ordering strategy for the grid points called “downwind numbering” which follows the flow direction and, combined with a Gauss-Seidel type smoother, yields robust multigrid convergence for adaptively refined grids, provided the convection field is cycle-free. The algorithms are of optimum complexity and the corresponding smoothers are shown to be robust in numerical tests.

References (32)

E. Bänsch
Local mesh refinement in 2 and 3 dimensions
Impact Comput. Sci. Engrg.
(1991)
A. Greenbaum
A multigrid method for multiprocessors
Appl. Math. Comput.
(1986)
G. Wittum
Linear iterations as smoothers in multigrid methods
Impact Comput. Sci. Engrg.
(1989)
R.E. Bank et al.
The hierarchical basis multigrid method
SC-87-2
(1987)
R.E. Bank
PLTMG: A Software Package for Solving Elliptic Partial Differential Equations. Users Guide 6.0
(1990)
P. Bastian
Locally refined solution of unsymmetric and nonlinear problems
P. Bastian
Parallele adaptive Mehrgitterverfahren
P. Bastian et al.
Additive and multiplicative multigrid—a comparison
P. Bastian et al.
Adaptivity and robustness
P. Bastian et al.
On robust and adaptive multigrid methods

J. Bey

Tetrahedral grid refinement

Computing

(1995)

J.H. Bramble et al.

Convergence estimates for multigrid algorithms without regularity assumptions

Math. Comp.

(1991)

J.H. Bramble et al.

Parallel multilevel preconditioners

Math. Comp.

(1990)

A. Brandt

Multi-level adaptive solution to boundary-value problems

Math. Comp.

(1977)

K. Eriksson et al.

Error estimates and automatic time step control for non-linear parabolic problems

SIAM J. Numer. Anal.

(1987)

R.P. Fedorenko

Ein Relaxationsverfahren zur Lösung elliptischer Differentialgleichungen

Zh. Vychisl. Mat. i Mat. Fiz.

(1961)

Cited by (52)

A high resolution Physics-informed neural networks for high-dimensional convection–diffusion–reaction equations
2023, Applied Soft Computing
In practical problems, some partial differential equations defined in high-dimensional domains or complex surfaces are difficult to calculate by traditional methods. In this paper, a novel data-driven deep learning algorithm is proposed to solve high-dimensional convection–diffusion–reaction equations. The main idea of the method is to use the neural network which combines the physical characteristics of the equation to get high accuracy numerical solution. The proposed method not only avoids the high cost of mesh generation, but also effectively reduces the numerical oscillation caused by the domination of the convection. In addition, two types of loss functions are designed to force physical properties, such as the positivity or maximum principle of the solution. Various numerical examples are performed to demonstrate the validity and accuracy of the proposed method.
An extremum-preserving finite volume scheme for convection-diffusion equation on general meshes
2020, Applied Mathematics and Computation
Citation Excerpt :
Therefore, a reliable extremum-preserving scheme is needed for the numerical simulation of convection-diffusion equation. Some effective numerical schemes have been developed for the convection-diffusion equation to solve the convection-dominated problem [4–8]. These schemes only can be used on the regular meshes and don’t satisfy the discrete extremum principle.
We present an extremum-preserving finite volume scheme for the convection-diffusion equation on general meshes in this article. The harmonic averaging point locating at the interface of heterogeneity are utilized to define the auxiliary unknowns. The second-order upwind method with a slope limiter is used for the discretization of convection flux. This scheme has only cell-centered unknowns and possesses a small stencil. The extremum-preserving property of this scheme is proved by standard assumption. Numerical results demonstrate that the extremum-preserving scheme is an efficient method in solving the convection-diffusion equation on distorted meshes.
High-order implicit palindromic discontinuous Galerkin method for kinetic-relaxation approximation
2019, Computers and Fluids
Citation Excerpt :
This kind of ideas is mentioned in several works. See for instance in [7,15,34,37,45]. In a recent work, we have evaluated the parallel scalability of the triangular solver [6].
We construct a high order discontinuous Galerkin method for solving general hyperbolic systems of conservation laws. The method is CFL-less, matrix-free, has the complexity of an explicit scheme and can be of arbitrary order in space and time. The construction is based on: (a) the representation of the system of conservation laws by a kinetic vectorial representation with a stiff relaxation term; (b) a matrix-free, CFL-less implicit discontinuous Galerkin transport solver; and (c) a stiffly accurate composition method for time integration. The method is validated on several one-dimensional test cases. It is then applied on two-dimensional and three-dimensional test cases: flow past a cylinder, magnetohydrodynamics and multifluid sedimentation.
Optimizing a multigrid Runge–Kutta smoother for variable-coefficient convection–diffusion equations
2017, Linear Algebra and Its Applications
Citation Excerpt :
The unsteady case is much more difficult and the multigrid strategy tuned on the steady case deteriorates dramatically, when moving to the unsteady setting. In this direction see, e.g., the works in [3,4], in which a coarsening that “follows” the flow, thus producing flow related aggregates, is used, or the works in [5–7], in which multigrid solvers for the convection–diffusion equation are investigated, both on the smoothing and on the coarsening side. As already mentioned, in the constant coefficient case, this issue is considered in [1], with the use of a specific class of smoothers based on explicit Runge–Kutta methods, which show low storage requirements and scale well in parallel: the tuning of a number of parameters makes the whole strategy very fast and efficient.
The theory of Generally Locally Toeplitz (or GLT for short) sequences of matrices is proposed in the analysis of a multigrid solver for the linear systems generated by finite volume/finite difference approximations of variable-coefficients linear convection–diffusion equations in 1D, proposed by Birken in 2012, and extended here to 2D problems. The multigrid solver is used with a Runge–Kutta smoother. Optimal coefficients for the smoother are found by considering the unsteady linear advection equation and using optimization algorithms. In particular, in order to reduce the issues of having multiple local minima, the sequential quadratic programming (SQP) mixed with genetic and particle swarm optimization algorithms are proposed. Numerical results show that our proposals are competitive with respect to other multigrid implementations.
Variational space–time elements for large-scale systems
2017, Computer Methods in Applied Mechanics and Engineering
Citation Excerpt :
Space–time problems are only first order in time direction and they can be considered as the limit of singularly perturbed diffusion–reaction problems. For this class of operators, multigrid solvers are known not to perform efficiently [54–57]. The main problem is that standard finite element methods provide matrices that are not M-matrices, and hence do not preserve the positivity and monotonicity properties of the solution.
In this paper, we introduce a new Galerkin based formulation for transient continuum problems, governed by partial differential equations in space and time. Therefore, we aim at a direct finite element discretization of the space–time, suitable for massive parallel analysis of the arising large-scale problem. The proposed formulation is applied to thermal, mechanical and fluid systems, as well as to a Kuramoto–Sivashinsky problem, representing the general class of higher-order formulations in material science using NURBS based shape functions. We verify whenever possible the conservation properties of the formulation. Finally, a series of examples demonstrate the applicability to all systems presented in this paper.
A geometric multigrid preconditioning strategy for DPG system matrices
2017, Computers and Mathematics with Applications
The discontinuous Petrov–Galerkin (DPG) methodology of Demkowicz and Gopalakrishnan (2010, 2011) guarantees the optimality of the solution in an energy norm, and provides several features facilitating adaptive schemes. A key question that has not yet been answered in general – though there are some results for Poisson, e.g.– is how best to precondition the DPG system matrix, so that iterative solvers may be used to allow solution of large-scale problems.
In this paper, we detail a strategy for preconditioning the DPG system matrix using geometric multigrid which we have implemented as part of Camellia (Roberts, 2014, 2016), and demonstrate through numerical experiments its effectiveness in the context of several variational formulations. We observe that in some of our experiments, the behavior of the preconditioner is closely tied to the discrete test space enrichment.
We include experiments involving adaptive meshes with hanging nodes for lid-driven cavity flow, demonstrating that the preconditioners can be applied in the context of challenging problems. We also include a scalability study demonstrating that the approach – and our implementation – scales well to many MPI ranks.

View all citing articles on Scopus

View full text

Downwind numbering: robust multigrid for convection-diffusion problems

Abstract

Impact Comput. Sci. Engrg.

Appl. Math. Comput.

Impact Comput. Sci. Engrg.

The hierarchical basis multigrid method

SC-87-2

PLTMG: A Software Package for Solving Elliptic Partial Differential Equations. Users Guide 6.0

Locally refined solution of unsymmetric and nonlinear problems

Parallele adaptive Mehrgitterverfahren

Additive and multiplicative multigrid—a comparison

Adaptivity and robustness

On robust and adaptive multigrid methods

Tetrahedral grid refinement

Computing

Convergence estimates for multigrid algorithms without regularity assumptions

Math. Comp.

Parallel multilevel preconditioners

Math. Comp.

Multi-level adaptive solution to boundary-value problems

Math. Comp.

Error estimates and automatic time step control for non-linear parabolic problems

SIAM J. Numer. Anal.

Ein Relaxationsverfahren zur Lösung elliptischer Differentialgleichungen

Zh. Vychisl. Mat. i Mat. Fiz.