Comptes Rendus Mécanique (CRM)

Kaili Xie

Marc Leonetti

Mechanical characterization of core-shell microcapsules

Tong Zhao Gong

Ahmed Kaci Boukellal

Yun Chen

Jean-Marc Debierre

Equiaxed growth of interacting Al–Cu dendrites in thin samples: a phase-field study at copper concentrations relevant for practical applications

Rabil Ayazoglu

Ebubekir Akkoyunlu

Bounds for the blow-up time a class of integro-differential problem of parabolic type with variable reaction term

Clément Bielinski

Badr Kaoui

Transfert de masse non-stationnaire depuis des particules sous écoulement

Thomas Engels

Hung Truong

Marie Farge

Dmitry Kolomenskiy

Kai Schneider

Computational aerodynamics of insect flight using volume penalization

Simon Hochgerner

Probabilistic representation of helicity in viscous fluids

Domenico Panunzio

Maria-Adela Puscas

Romain Lagrange

FSI—vibrations of immersed cylinders. Simulations with the engineering open-source code TrioCFD. Test cases and experimental comparisons

Bastien Agard

Landry Giraud

Françoise Fauvin

Jean-Christophe Roux

Pierre Monnet

Eric Feulvarch

Fast computation of critical planes for fatigue life analysis of metals

Alain Dervieux

Comptes Rendus
Mécanique
Alain Dervieux
To be structured, or unstructured, fifty years of slings and arrows
Volume 350, Special Issue S1 (2022), p. 53-58
Online since: 3 October 2022
Issue date: 5 November 2024
Part of Special Issue: More than a half century of Computational Fluid Dynamics
Guest editor: Mohammed El Ganaoui (Professeur des Universités, Spécialiste :
Mécanique des Fluides et Transferts de Chaleur et de Masse, Université de Lorraine)
https://doi.org/10.5802/crmeca.115
This article is licensed under the
Creative Commons Attribution 4.0 International License.
http://creativecommons.org/licenses/by/4.0/
C EN T R E
MER S ENN E
The Comptes Rendus. Mécanique are a member of the
Mersenne Center for open scientific publishing
www.centre-mersenne.org — e-ISSN : 1873-7234
Comptes Rendus
Mécanique
2022, Vol. 350, Special Issue S1, p. 53-58
https://doi.org/10.5802/crmeca.115
Research article / Article de recherche
More than a half century of Computational Fluid Dynamics / Plus
d’un demi-siècle de mécanique des fluides numérique
To be structured, or unstructured, fifty years
of slings and arrows
Alain Dervieux ,a
a Société LEMMA, 2000 route des Lucioles, Sophia-Antipolis, France, and Institut
National de Recherche en Informatique et en Automatique (INRIA), 2004 Route des
lucioles, F-06902 Sophia-Antipolis, France
E-mail: alain.dervieux@inria.fr
Abstract. This paper is not a review, but narrates the personal experiences (nearly fifty years) of the author
concerning unstructured mesh, a well debated theme during these years.
Keywords. Unstructured mesh, Finite difference, Finite element, Finite volume, Computational fluid
dynamics.
Manuscript received 10 May 2021, accepted 17 May 2022.
1. Introduction
In an unstructured mesh, the number N (i ) of nodes neighboring a node i is not regularly defined
from one node to the other one. Computing structures has led rapidly to consider unstructured
meshes. Try to mesh the Eiffel tower (in fact Sidney opera was one of the first famous success
of unstructured meshes). The static computations allowed to introduce variational formulation
and then the finite element method.
2. In the earlier times
When I started studying CFD/CSM, the two main enemies were finite differences/volumes on
my right and finite elements on my left. FD/FV were applied on structured meshes, and FE
on unstructured meshes.1 Advised by Jean Céa and then recruited by Roland Glowinski, I was
necessarily in the FE party. The preferred flow model in aeronautics was the full potential
model, a mainly elliptic model and Roland’s team and friends (involving Olivier Pironneau) in
association with the Dassault team (around Jacques Périaux) had succeeded to compute the flow
around a complete aircraft with a finite-element method and an unstructured mesh [1].
1FD = Finite Difference, FV = Finite Volume, FE = Finite Element.
ISSN (electronic): 1873-7234 https://comptes-rendus.academie-sciences.fr/mecanique/
54 Alain Dervieux
3. Euler flows
However, in the eigthies, the challenge was to compute with the Euler model, a first step before
(compressible) Navier–Stokes. The mathematical model is hyperbolic and its discretization
requires the derivation of a sophisticated stabilization. Indeed, for the convection of a scalar field,
finite element computations were limited by Peclet effects (unstability when the diffusion term
does not exists or is too small). The answer proposed by the FD/FV camp was “upwinding”, that
is managing in such a way that the concerned derivatives are not computed in a central manner
around the node but upward with respect to the convection velocity. An important activity in
finite elements developed in order to upwind this method.
A second debate in compressible CFD was related to the building of explicit time advanc-
ing having a sufficient stability domain. One-step and two-step advancing were initially pre-
ferred, like the two-step method of MacCormack [2], with a predictor step with upwinding in
one mesh direction, a corrector step upwinded in the opposite direction. Two main advantages
were identified. Firstly, such schemes need only one or two flux assemblies for a stable time
step, which was interpreted as a chance for best efficiency, secondly, the schemes were vari-
ant of the Lax–Wendroff scheme [3] and enjoyed a built-in dissipation, satisfying the dissipa-
tive Kreiss criterion [4]. The Lax–Wendroff FD method was then extended to P1 FE indepen-
dantly by three teams [5–7]. Lax–Wendroff type time-advancing took a backseat with the rise of
Jameson–Schmidt–Turkel scheme [8], derived first for structured meshes, then for unstructured
ones [9].
A third debate concerned the satisfaction of a so-called entropy condition, which is sufficient
for ensuring the uniqueness of solution of many nonlinear hyperbolic models. Conversely,
the discretization of an hyperbolic model can produce parasitic non-entropic (non-unique)
numerical solutions. The entropy issue was observed for full potential models, but it was soon
clear that a simple upwinding of the density permitted to ensure that entropic solutions were
obtained. For the Euler equations, most time advancing methods were sufficiently dissipative to
ensure entropic solutions.
The above events did not close the debate concerning upwinding. In the late fifties, Godunov
pointed the interest of using Riemann problems solution for upwinding the approximation of
nonlinear hyperbolic problems (he recounts the story of this in [10]). The option was a little
complex for routine computing and Roe proposed his approximate Riemann solver [11] and
Osher with Chakravarthy, a more sophisticated and robust one [12].
First-order accurate upwind schemes were not sufficiently accurate, and second-order
schemes not sufficiently stable for shock capturing (although artificial viscosity methods were not
so bad). Significant progress was carried by the introduction of limiters by Boris and Book [13].
van Leer [14] brought a clever synthesis between Godunov upwinding and limiters, introducing
the idea of local reconstruction. An illuminating TVD theory was then proposed by Harten [15].
Alongside, the stabilization of finite element for hyperbolic CFD models was addressed by
Hughes and Mallet [16].
Many of these ideas (together with implicit time advancing) were integrated in an unstruc-
tured method developed for hypersonic flows around the shapes considered in the European
project Hermes—Figure 1—[17], project under the direction of Pierre Perrier which gave a
favourable impulse to CFD researches in Europe.
4. Supercomputer is coming
Few remarks must be made concerning the computational time. An interesting question is: in
the 80’s–90’s, did computational aerodynamics reduce “wall clock calculation times”, thanks to
Alain Dervieux 55
Figure 1. High Mach number high angle of attack Euler computations around the geometry
of the spatial shuttle and the geometry of European space aircraft Hermes project. Meshes
(skin) and Mach number, from [17].
progress in algorithms progress rather than computer progress. It is clear that in the 80’s, we
enjoyed the rise of supercomputers like Cray 1 which was more expensive than mainframes and
more powerful. The rise of “micro killers” (IBM RS6000, etc) set the price of flop/s to a much
lower level. The answer to the above question (probably in favor to computers) is difficult to
establish, as many algorithms were designed for a better use of the pipelined number-crunchers.
Meanwhile this evolution was in some manner favourable to structured (“my pipeline prefers
structured”).
Meanwhile the scientific community was debating on the physical limits to computer speed.
Grand priests invoked the light velocity, atom size, . . . In short we were pushed towards the
unique issue, parallelism.
Indeed first parallel computers appeared, taking so many forms (network, hypercubes,
farms, . . . ), but not so powerful at the beginning as vector computers continuing their progress
and preferred by non academic institutions. Extra noise were brought by the expectation, starting
already before pipelines, of the fifth generation of computers, specialized in Artificial Intelligence.
A typical example was the development by the Thinking Machine Corporation of the Connection
Machine which became unexpectedly a much studied and appreciated number-cruncher.
5. But algorithms?
Let us examine the progress of algorithms, the focus on solution algorithms, in particular. Two
communities were particularly active.
The practitioners of multigrid had a yearly office, the Copper Mountain MG conference, also
good for skiers. A variant, full multigrid was the graal, since O(N ) complexity was attainable,
superior to other methods, as far as the problem size N is sufficiently large, going by the advice
56 Alain Dervieux
Figure 2. HL-CRM 16° high lift calculation (Courtesy of F. Alauzet). The Mach number
values demonstrate the accurate capture of the wake, with a first vortex from wing tip, a
second one from the gap between flaps, a third one starting where the wing is cracked, and
a fourth one from wing root [23].
of grand priest Achi Brandt. Extension to unstructured meshes was not a piece of cake and could
not show the miraculous speed up of certain structured demonstrations.
The practitioners of Domain Decomposition Methods (DDM) were also very active, they pro-
duced popular algorithms like Additive-Schwarz (e.g. [18]) or FETI [19], both being definitively
adapted to systems coming from unstructured meshes.
Both methodologies give parallel algorithms. A common paradox is the problem posed by the
coarse grid. In MG, the coarse grid is too small to be efficiently solved on the many processors
reserved by the user for the fine grid problem. In DDM, the use of deflation to accelerate the
global coupling also sets the question of an efficient solution of the coarse grid with one degree
of freedom by processor [20].
6. Towards high order
In earlier days, there were first-order methods and higher order ones, i.e. second order. High
order methods (order >2) are also fascinating. A graal also was identified in Spectral methods
with a convergence to continuous, better than polynomial. However, the increasing interest to
industrial issues led to concentrated investigations on unstructured high order methods. The
Discontinuous Galerkin (DG) for CFD was popularized by Cockburn [21], Bassi and Rebay [22].
It should be noted that for many higher-order approximations, “unstructured” assumes a regular
substructure inside each element.
7. Mesh generation and adaptation
The issue of easy mesh generation was the main motivation for choosing the unstructured option.
Indeed, after many works, the unstructured mesh generation became fast and robust (at least
for tetrahedra). The unstructured option eventually won the competition on preprocessing, in
terms of engineer time. But the important capabilities of unstructured mesh adaptation was
early identified. An active competition in unstructured mesh adaptation started no later than in
1986 at the Reading Conference. Unstructured mesh adaptation took a strong acceleration with
the use of mesh metrics, and goal oriented strategies. A recent impressive accomplishment [23]
is the use of goal oriented metrics for computing high-lift flows around an aircraft geometry,
Figures 2 and 3.
Alain Dervieux 57
Figure 3. HL-CRM 16° high lift calculation (Courtesy of F. Alauzet). A zoom at flaps gap
shows the initial capture of the second vortex [23].
8. Concluding remarks
The debate between unstructured and structured for compressible Navier–Stokes is at least
40 years old. It has been more or less a debate about when unstructured would be definitively
better than structured. However, examining High-lift or drag reduction workshops, we observe
that block-structured codes enjoy still higher performances for the same number of cells, and can
be used with higher numbers of cells. Regarding engineering efficiency, however, almost all main
software vendors in CFD have migrated towards unstructured.
Conflicts of interest
The author has no conflict of interest to declare.
References
[1] M.-O. Bristeau, R. Glowinski, J. Périaux, P. Perrier, O. Pironneau, “On the numerical solution of nonlinear problems in
fluid dynamics by least squares and finite element methods (II). Application to transonic flow simulations”, Comput.
Methods Appl. Mech. Eng. 17/18 (1985), p. 619-657.
[2] R. MacCormack, “The effect of viscosity in hypervelocity impact cratering”, in AIAA Paper 69-364, ARC, Reston, VA,
1969.
[3] P. Lax, B. Wendroff, “Systems of conservation laws”, Commun. Pure Appl. Math. 13 (1960), p. 217-237.
[4] A. Lerat, R. Peyret, “Noncentered schemes and shock propagation problems”, Comput. Fluids 2 (1974), p. 35-52.
[5] F. Angrand, A. Dervieux, “Some explicit triangular finite element schemes for the Euler equations”, Int. J. Numer.
Methods Fluids 4 (1984), p. 749-764.
[6] R. Löhner, K. Morgan, O. Zienkiewicz, “The solution of non-linear hyperbolic equation systems by the finite element
method”, Int. J. Numer. Methods Fluids 4 (1984), p. 1043-1063.
[7] J. Donea, “A Taylor–Galerkin method for convective transport problems”, Int. J. Numer. Methods Eng. 20 (1984),
p. 101-119.
[8] A. Jameson, W. Schmidt, E. Turkel, “Solutions of the Euler equations by finite volume methods using Runge-Kutta
time-stepping schemes”, in AIAA Paper 81-1259, ARC, Reston, VA, 1981, p. 1-17.
[9] A. Jameson, T. Baker, N. Weatherhill, “Calculation of inviscid transonic flow over a complete aircraft”, in AIAA Paper
86-0103, ARC, Reston, VA, 1986, p. 1-16.
[10] S. K. Godunov, “Reminiscences about numerical schemes”, in INRIA Report, vol. RR6666, INRIA, Rocquencourt,
2008.
[11] P. Roe, “Approximate Riemann solvers, parameter vectors, and difference schemes”, J. Comput. Phys. 43 (1981), no. 2,
p. 357-372.
[12] S. Osher, S. Chakravarthy, “Upwind difference schemes for hyperbolic systems of conservation laws”, Math. Comput.
38 (1982), no. 158, p. 339-374.
[13] D. Book, J. Boris, K. Hain, “Flux-corrected transport: II. Generalizations of the method”, J. Comput. Phys. 18 (1975),
p. 248-283.
58 Alain Dervieux
[14] B. van Leer, “Towards the ultimate conservative difference scheme IV: A new approach to numerical convection”,
J. Comput. Phys. 23 (1977), p. 276-299.
[15] A. Harten, “High resolution method for hyperbolic conservation laws”, J. Comput. Phys. 49 (1983), p. 357-393.
[16] T. Hughes, M. Mallet, “A new finite element formulations for computational fluid dynamics: III”, Comput. Methods
Appl. Mech. Eng. 58 (1986), p. 329-336.
[17] B. Stoufflet, J. Périaux, L. Fezoui, A. Dervieux., “3-D hypersonic Euler numerical simulation around space vehicles
using adapted finite elements”, in 25th AIAA Aerospace Meeting, Reno (1987), AIAA Paper 87-0560, AIAA, Reston, VA,
1987.
[18] X. Cai, M. Sarkis, “A restricted additive Schwarz preconditioner for general sparse linear systems”, SIAM J. Sci.
Comput. 21 (1999), p. 239-247.
[19] C. Farhat, F. X. Roux, “A method of finite element tearing and interconnecting and its parallel solution algorithm”,
Int. J. Numer. Methods Eng. 32 (1991), p. 1205-1227.
[20] H. Alcin, B. Koobus, O. Allain, A. Dervieux, “Efficiency and scalability of a two-level Schwarz algorithm for incom-
pressible and compressible flows”, Int. J. Numer. Methods Fluids 72 (2013), no. 1, p. 69-89.
[21] B. Cockburn, “Discontinuous Galerkin methods”, ZAMM - J. Appl. Math. Mech./Z. Angew. Math. Mech. 83 (2003),
no. 11, p. 731-754.
[22] F. Bassi, S. Rebay, “High-order accurate discontinuous finite element solution of the 2D Euler equations”, J. Comput.
Phys. 138 (1997), no. 2, p. 251-285.
[23] F. Alauzet, L. Frazza, “Feature-based and goal-oriented anisotropic mesh adaptation for RANS applications in
Aeronautic and Aerospace”, J. Comput. Phys. 439 (2021), article no. 110340.


To be structured, or unstructured, fifty years of slings and arrows

Akshai Kumar Runchal

Evolution of CFD as an engineering science. A personal perspective with emphasis on the finite volume method

Not a member yet

Mechanical characterization of core-shell microcapsules

Equiaxed growth of interacting Al–Cu dendrites in thin samples: a phase-field study at copper concentrations relevant for practical applications