International Journal for Numerical Methods in Fluids
Volume 97, Issue 1 pp. 88-115
RESEARCH ARTICLE
Open Access

Semi-implicit Lagrangian Voronoi approximation for the incompressible Navier–Stokes equations

Ondřej Kincl, 

Corresponding Author

Ondřej Kincl

Laboratory of Applied Mathematics, DICAM, University of Trento, Trento, Italy

Correspondence

Ondřej Kincl, Laboratory of Applied Mathematics DICAM, University of Trento, 38123 Trento, Italy.

Email: [email protected]

Search for more papers by this author
Ilya Peshkov, 

Ilya Peshkov

Laboratory of Applied Mathematics, DICAM, University of Trento, Trento, Italy

Search for more papers by this author
Walter Boscheri, 

Walter Boscheri

Laboratoire de Mathématiques UMR 5127 CNRS, Université Savoie Mont Blanc, Le Bourget du Lac, France

Department of Mathematics and Computer Science, University of Ferrara, Ferrara, Italy

Search for more papers by this author
First published: 17 September 2024
https://doi.org/10.1002/fld.5339
Citations: 2

Abstract

We introduce semi-implicit Lagrangian Voronoi approximation (SILVA), a novel numerical method for the solution of the incompressible Euler and Navier–Stokes equations, which combines the efficiency of semi-implicit time marching schemes with the robustness of time-dependent Voronoi tessellations. In SILVA, the numerical solution is stored at particles, which move with the fluid velocity and also play the role of the generators of the computational mesh. The Voronoi mesh is rapidly regenerated at each time step, allowing large deformations with topology changes. As opposed to the reconnection-based Arbitrary-Lagrangian-Eulerian schemes, we need no remapping stage. A semi-implicit scheme is devised in the context of moving Voronoi meshes to project the velocity field onto a divergence-free manifold. We validate SILVA by illustrative benchmarks, including viscous, inviscid, and multi-phase flows. Compared to its closest competitor, the Incompressible Smoothed Particle Hydrodynamics method, SILVA offers a sparser stiffness matrix and facilitates the implementation of no-slip and free-slip boundary conditions.

1 INTRODUCTION

In computational fluid dynamics, Lagrangian methods are invaluable for their ability to handle complex deformations and material interfaces. The defining feature of Lagrangian methods is that the degrees of freedom of the spatial approximation follow the motion of the material, rather than being static with respect to a selected Eulerian frame of reference. Consequently, the (often problematic) nonlinear convective terms are absent, thus obtaining a family of numerical schemes which exhibit virtually no numerical dissipation at contact discontinuities and material interfaces. Moreover, individual particles or cells preserve their identity, facilitating the mass conservation and the implementation of sharp material interfaces.

Developing a mesh-based Lagrangian method is notoriously difficult because of the large deformations inherent to the fluid motion. This problem becomes particularly evident when considering flows with high vorticity or large velocity gradients, that stretch, twist or compress the control volumes until they get invalid, that is, with negative volumes. To overcome this problem, mesh optimization algorithms have been developed,1-4 aiming at improving the mesh quality by performing a sort of regularization of the shape of each single cell. If the moving mesh scheme belongs to the category of Arbitrary-Lagrangian-Eulerian (ALE) methods, in which the mesh motion can be driven independently from the fluid velocity, the stage of mesh optimization is referred to as rezoning. The rezoning step is directly embedded in the numerical scheme for direct ALE methods,5, 6 otherwise it must be followed by a remapping step in indirect ALE methods.7-9 These techniques are all based on the assumption that the optimization process does not change the topology of the underlying computational grid, hence posing a severe limit to the possibility of improving the mesh quality for complex configurations. Moreover, the mesh optimization stage has to be compatible with some physical requirements on the numerical solution, for example, contact discontinuities must remain untouched to ensure the sharp interface resolution of Lagrangian schemes. The most general solution to this difficulty, which allows to combine mesh optimization and Lagrangian mesh motion, is to allow for topology changes. This approach is also known as reconnection, that has been originally presented in Reference 10. The idea was to use a set of Lagrangian particles, that are used to define the computational tessellation without assuming a fix connectivity: indeed, the topology of the mesh was time dependent, so that at each time step the connectivity was established by defining the surrounding domains (or control volumes) in accordance to the current particle positions. This mesh was then used to discretize the equations written in Lagrangian form. More recent developments of this seminal idea are given by Free-Lagrange methods,11, 12 Re-ALE schemes,13, 14 and finite volume ALE methods.15, 16

Among many others, a well-established mesh-free Lagrangian method is the Smoothed Particle Hydrodynamics (SPH), developed in 1970s: see Reference 17 for a review. In the SPH framework, the continuum is replaced by a finite number of material points (particles), and the gradients of physical variables (like density and velocity) are approximated using convolution and a convenient set of kernel functions. No computational grid is used in the SPH framework, hence yielding high versatility in the simulation of large deformations of the continuum. Due to its particle nature, the SPH method avoids the mesh-related issues and it is exceptionally robust. Owing to this advantage, together with the simplicity of implementation, SPH boasts with wide range of applications in science and industry.18, 19 Nevertheless, compared to mesh-based approaches, the computational cost of SPH schemes associated to each degree of freedom is typically larger, since every particle needs to communicate with every neighbor within a certain radius (as specified by the smoothing length).20 Moreover, converging to the exact solution is challenging because the spatial step must shrunk faster than the smoothing length,21 leading to an unfavorable effective convergence rate. To remain competitive in this regard, the accuracy of SPH methods needs to be improved by relying on a set of renormalized operators,22, 23 typically at the expense of discrete energy conservation.24 Lastly, let us mention the problematic of boundary conditions. While free surfaces in fluids and solids are automatically handled, implementing Dirichlet or Neumann conditions in the SPH framework is less trivial (in comparison to e.g., Finite Element Method). As it turns out, having a mesh is not completely without merit and this is where Lagrangian Voronoi Methods (LVM) enter the game.

The study of Lagrangian methods based on Voronoi tessellations dates back to the 70s and 80s, for example, see Reference 11, and received further attention in the 90s, for example, see References 25-27, and in the light of recent publications.15, 16, 28, 29 By definition, a Voronoi cell Ω i $$ {\Omega}_i $$ is the set of points which is closer to the generating particle (seed) x i $$ {\boldsymbol{x}}_i $$ than to any other particle x j $$ {\boldsymbol{x}}_j $$ . The Voronoi mesh generated by moving particles has the advantage of keeping reasonably good quality even in case of large deformations. Furthermore, the local topology of Voronoi meshes can be arbitrary, thus this kind of mesh permits to remove some mesh imprinting that might arise from the adoption of the Lagrangian frame of reference.

While the aforementioned studies revolve around compressible fluids and use explicit time steps, in this paper, we introduce some implicitness to obtain a LVM variant for the incompressible Euler and Navier–Stokes equations. With the aim of avoiding the solution of globally implicit systems defined on the entire computational grid, the implicit-explicit (IMEX) approach has emerged in the literature30-36 as a powerful time integration technique which permits to split explicit and implicit fluxes.32, 33, 37 In particular, we rely on a semi-implicit time discretization,38-41 in which the mesh motion is treated explicitly while the pressure terms are taken into account implicitly. This is well suited to enforce the divergence-free condition on the velocity field, which is nothing but the energy equation for incompressible fluids.

To the best of our knowledge, such studies on semi-implicit schemes on Lagrangian Voronoi meshes did not receive sufficient attention in the literature. Yet, we found out that our method is conceptually similar to the method by Borgers and Peskin.42, 43 Namely, the spatial and time discretization of the governing equations is similar to Reference 43, however, the key novelties lay in the fast computation of the Voronoi mesh, and a novel stabilized pressure gradient allowing to efficiently deal with the tensile instabilities known for particle methods. Also, our method is linked with the recent work of Després,29 and it relies on the improved gradient approximation by Serrano and Espanol.44

The scheme presented here is termed Semi-Implicit Lagrangian Voronoi Approximation (SILVA), since the mathematical model is given by the incompressible Navier–Stokes equations. We will show that SILVA arises quite naturally from basic assumptions. The correctness and accuracy of the scheme is verified in benchmarks, including the lid-driven cavity problem and a Rayleigh–Taylor instability test for multi-phase fluids. Not only engineers and researchers interested in new Lagrangian numerical methods for fluid mechanics may find this paper valuable, but also SPH specialists because of the deep analogies between SILVA and incompressible SPH (ISPH). Both methods involve moving particles, are based on Helmholtz decomposition, and the cell-list structure from ISPH is a perfect tool for constructing a Voronoi grid for SILVA. To summarize, the two methods are highly inter-compatible and an implementation of a physical phenomenon in one method can be painlessly imported to the other one.

The structure of the paper is as follows. In Section 2, we present the governing equations of incompressible fluids, while in Section 3 we introduce the definition and notation of the moving Voronoi mesh, including its generation. Section 4 is devoted to the description of the numerical scheme, namely our LVM, with details on the explicit and the implicit time discretization as well as on the discrete spatial operators. The numerical validation of the accuracy and robustness of SILVA is presented in Section 5 by running several benchmarks for incompressible fluids. Finally, Section 6 finalizes this article by summarizing the work and giving an outlook to future investigations.

2 GOVERNING EQUATIONS

We consider a d $$ d $$ -dimensional domain Ω ⊂ ℝ d $$ \Omega \subset {\mathbb{R}}^d $$ closed by the boundary ∂ Ω ⊂ ℝ d − 1 $$ \mathrm{\partial \Omega}\subset {\mathbb{R}}^{d-1} $$ , with x $$ \boldsymbol{x} $$ being the spatial coordinate vector and t ∈ ℝ 0 + $$ t\in {\mathbb{R}}_0^{+} $$ representing the time coordinate. In the Lagrangian frame, the mathematical model which describes the phenomena of incompressible viscous flows writes
d v d t + ∇ p ρ − ν Δ v = 0 , $$ \frac{\mathrm{d}\boldsymbol{v}}{\mathrm{d}t}+\frac{\nabla p}{\rho }-\nu \Delta \boldsymbol{v}\kern0.5em =\mathbf{0}, $$ (1a)
∇ · v = 0 , $$ \nabla \cdotp \boldsymbol{v}\kern0.5em =0, $$ (1b)
d x d t = v . $$ \frac{\mathrm{d}\boldsymbol{x}}{\mathrm{d}t}\kern0.5em =\boldsymbol{v}. $$ (1c)
Here, v ( x , t ) $$ \boldsymbol{v}\left(\boldsymbol{x},t\right) $$ identifies the velocity vector, p ( x , t ) $$ p\left(\boldsymbol{x},t\right) $$ denotes the pressure, and ρ ( x , t ) $$ \rho \left(\boldsymbol{x},t\right) $$ is the fluid density, ν $$ \nu $$ is the kinematic viscosity of the fluid and
d g d t = ∂ g ∂ t + v · ∇ g . $$ \frac{\mathrm{d}g}{\mathrm{d}t}=\frac{\partial g}{\partial t}+\boldsymbol{v}\cdotp \nabla g. $$ (2)
is the material derivative of a quantity g ( x , t ) $$ g\left(\boldsymbol{x},t\right) $$ . Equation (1c) is the so-called trajectory equation, which drives the motion of the coordinates and is the defining feature of a Lagrangian method.
The flow is incompressible, which implies that ρ $$ \rho $$ is constant along the flow trajectories, although it is not necessarily constant in space. The velocity field is subjected to the divergence constraint (1b), which can be reformulated in a weak sense. Indeed, by multiplying Equation (1b) by a smooth test function φ ( x ) ∈ 𝒞 ∞ and integrating by parts over the domain Ω $$ \Omega $$ , we have that
∫ Ω φ ∇ · v d x = ∫ ∂ Ω ϕ v · n d S − ∫ Ω ∇ φ · v d x . $$ {\int}_{\Omega}\varphi \kern0.3em \nabla \cdotp \boldsymbol{v}\kern0.3em \mathrm{d}\boldsymbol{x}={\int}_{\mathrm{\partial \Omega }}\phi \kern0.3em \boldsymbol{v}\cdotp \boldsymbol{n}\kern0.3em \mathrm{d}S-{\int}_{\Omega}\nabla \varphi \cdotp \boldsymbol{v}\kern0.3em \mathrm{d}\boldsymbol{x}. $$ (3)
We will assume that the no-penetration condition is satisfied at the boundary
v · n = 0 , ∀ x ∈ ∂ Ω , $$ \boldsymbol{v}\cdotp \boldsymbol{n}=0,\kern1em \forall \boldsymbol{x}\in \mathrm{\partial \Omega }, $$ (4)
so that Equation (3) reduces to
∫ Ω ∇ φ · v d x = 0 , ∀ φ ∈ 𝒞 ∞ . (5)
The condition (4) is not sufficient for a viscous fluid ( ν ≠ 0 $$ \nu \ne 0 $$ ) which also requires a condition for the tangential velocity. Two possibilities will be covered in this manuscript: the free-slip and no-slip condition. We return to this topic in Section 4.5. It would be also possible to consider periodic boundaries, which would imply the use of a periodic Voronoi mesh generator. We do not foresee any substantial obstacle in this regard. The implementation of other conditions, like inflows and outflows, are left for future investigations.

3 MOVING VORONOI MESH WITH TOPOLOGY CHANGES

3.1 Notation and definitions

Let assume Ω ⊂ ℝ d $$ \Omega \subset {\mathbb{R}}^d $$ to be an open convex and bounded polytope. We consider N $$ N $$ distinct sample points x 1 , x 2 , … , x N ∈ Ω $$ {\boldsymbol{x}}_1,{\boldsymbol{x}}_2,\dots, {\boldsymbol{x}}_N\in \Omega $$ , which will be treated as material points. The points x i $$ {\boldsymbol{x}}_i $$ are called seeds, for i = 1 , 2 , … , N $$ i=1,2,\dots, N $$ . A Voronoi cell ω i $$ {\omega}_i $$ corresponding to the seed x i $$ {\boldsymbol{x}}_i $$ is defined for every i , j = 1 , 2 , … , N $$ i,j=1,2,\dots, N $$ as
ω i = ⋂ j ≠ i { x ∈ Ω : | x − x i | < | x − x j | } . $$ {\omega}_i{=\bigcap}_{j\ne i}\left\{\boldsymbol{x}\in \Omega :\kern1em |\boldsymbol{x}-{\boldsymbol{x}}_i|<|\boldsymbol{x}-{\boldsymbol{x}}_j|\right\}. $$
To make notation easier throughout the entire paper, we assume that the cell indexes are always running in the interval i , j = 1 , 2 , … , N $$ i,j=1,2,\dots, N $$ . In the Lagrangian framework, every cell contains a portion of fluid with mass M i $$ {M}_i $$ , which is constant in time. The Voronoi cell is a convex polytope and its boundary ∂ ω i $$ \partial {\omega}_i $$ is composed of the set of facets
Γ i j = Γ j i = { x ∈ ∂ ω i : | x − x i | = | x − x j | } . $$ {\Gamma}_{ij}={\Gamma}_{ji}=\left\{\boldsymbol{x}\in \partial {\omega}_i:\kern1em |\boldsymbol{x}-{\boldsymbol{x}}_i|=|\boldsymbol{x}-{\boldsymbol{x}}_j|\right\}. $$ (6)
Furthermore, the cell boundary ∂ ω i $$ \partial {\omega}_i $$ might share a portion of the domain boundary ∂ Ω $$ \mathrm{\partial \Omega } $$ when ∂ Ω ∩ ∂ ω i ≠ 0 $$ \mathrm{\partial \Omega}\cap \partial {\omega}_i\ne 0 $$ . In such case, we refer to ω i $$ {\omega}_i $$ as a boundary-touching cell, or an interior cell otherwise. We also define the surface element:
S i = ∫ ∂ ω i n d S , $$ {\boldsymbol{S}}_i={\int}_{\partial {\omega}_i}\boldsymbol{n}\kern0.3em \mathrm{d}S, $$ (7)
where n ( x ) $$ \boldsymbol{n}\left(\boldsymbol{x}\right) $$ is the outward pointing unit normal vector defined on ∂ ω i $$ \partial {\omega}_i $$ .
The golden property of Voronoi meshes is the orthogonality between the facets Γ i j $$ {\Gamma}_{ij} $$ and the segments joining two seeds, namely x i j = x i − x j $$ {\boldsymbol{x}}_{ij}={\boldsymbol{x}}_i-{\boldsymbol{x}}_j $$ . Hence, the outer normal vector n i j $$ {\boldsymbol{n}}_{ij} $$ is simply given for each facet Γ i j $$ {\Gamma}_{ij} $$ by
n i j = − x i j r i j , $$ {\boldsymbol{n}}_{ij}=-\frac{{\boldsymbol{x}}_{ij}}{r_{ij}}, $$ (8)
where r i j = | x i j | $$ {r}_{ij}=\mid {\boldsymbol{x}}_{ij}\mid $$ represents the inter-seed distance. The d $$ d $$ -dimensional Lebesgue measure of each cell is denoted by | ω i | $$ \mid {\omega}_i\mid $$ , while | ∂ ω i | $$ \mid \partial {\omega}_i\mid $$ is the ( d − 1 ) $$ \left(d-1\right) $$ -dimensional Hausdorff measure of its boundary. Likewise, | Γ i j | $$ \mid {\Gamma}_{ij}\mid $$ represents the length of the facet Γ i j $$ {\Gamma}_{ij} $$ . In general, it is necessary to distinguish the midpoint of a facet
m i j = 1 | Γ i j | ∫ Γ i j x d S , $$ {\boldsymbol{m}}_{ij}=\frac{1}{\mid {\Gamma}_{ij}\mid }{\int}_{\Gamma_{ij}}\boldsymbol{x}\mathrm{d}S, $$ (9)
and the inter-seed midpoint
x ‾ i j = x i + x j 2 . $$ {\overline{\boldsymbol{x}}}_{ij}=\frac{{\boldsymbol{x}}_i+{\boldsymbol{x}}_j}{2}. $$ (10)
Indeed, for a general Voronoi cell, it is possible that x ‾ i j ∉ Γ i j $$ {\overline{\boldsymbol{x}}}_{ij}\notin {\Gamma}_{ij} $$ .

To evaluate partial derivatives in closed form for a Voronoi mesh, we refer to the recent developments forwarded in Reference 29. There is indeed a simple formula for computing the derivative of a Voronoi volume with respect to the other seeds,29 which is recalled in the following theorem.

Theorem 1.For j ≠ i $$ j\ne i $$ we have the closed form formulae:

∂ | ω i | ∂ x j = − | Γ i j | r i j m i j − x j , $$ \frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_j}=-\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_j\right), $$ (11)
and
∂ | ω i | ∂ x i = − ∑ j ≠ i ∂ | ω j | ∂ x i = − ∑ j ≠ i ∂ | ω i | ∂ x j − S i . $$ \frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_i}=-\sum \limits_{j\ne i}\frac{\partial \mid {\omega}_j\mid }{\partial {\boldsymbol{x}}_i}=-\sum \limits_{j\ne i}\frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_j}-{\boldsymbol{S}}_i. $$ (12)

Proof.We present a two page proof using the Lebesgue (dominated convergence) theorem in A. Other proofs can be found in References 29 and 42, which rely on a smooth function to approximate the characteristic function of ω i $$ {\omega}_i $$ . Another derivation restricted to the two-dimensional case can also be found in Reference 43.

Remark 1.It is possible to get an intuitive understanding of (11) by evaluating the rate of change of volume when the seeds are moving. By the transport theorem we have

d | ω i | d t = ∑ j ∫ Γ i j v n , i j ( x ) d S , $$ \frac{\mathrm{d}\mid {\omega}_i\mid }{\mathrm{d}t}=\sum \limits_j{\int}_{\Gamma_{ij}}{v}_{n, ij}\left(\boldsymbol{x}\right)\mathrm{d}S, $$ (13)
where v n , i j $$ {v}_{n, ij} $$ is the speed of the interface Γ i j $$ {\Gamma}_{ij} $$ in the outward normal direction with respect to ω i $$ {\omega}_i $$ . Naively, one would expect
v n , i j = 1 2 n i j · d x i d t + d x j d t . $$ {v}_{n, ij}=\frac{1}{2}{\boldsymbol{n}}_{ij}\cdotp \left(\frac{\mathrm{d}{\boldsymbol{x}}_i}{\mathrm{d}t}+\frac{\mathrm{d}{\boldsymbol{x}}_j}{\mathrm{d}t}\right). $$ (14)
Therefore, in the case when only x j $$ {\boldsymbol{x}}_j $$ is moving one obtains
d | ω i | d t = − | Γ i j | 2 r i j x i j · d x j d t = − | Γ i j | r i j ( x ‾ i j − x j ) · d x j d t . $$ \frac{\mathrm{d}\mid {\omega}_i\mid }{\mathrm{d}t}=-\frac{\mid {\Gamma}_{ij}\mid }{2{r}_{ij}}{\boldsymbol{x}}_{ij}\cdotp \frac{\mathrm{d}{\boldsymbol{x}}_j}{\mathrm{d}t}=-\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({\overline{\boldsymbol{x}}}_{ij}-{\boldsymbol{x}}_j\right)\cdotp \frac{\mathrm{d}{\boldsymbol{x}}_j}{\mathrm{d}t}. $$ (15)
As it turns out, this is true only when x j $$ {\boldsymbol{x}}_j $$ moves in a direction parallel to the vector x i j $$ {\boldsymbol{x}}_{ij} $$ , like during a linear stretching (and it is always true for a one-dimensional Voronoi mesh, where x ‾ i j = m i j $$ {\overline{\boldsymbol{x}}}_{ij}={\boldsymbol{m}}_{ij} $$ ). Formula (11) can be understood as a correction of (15) for displacements of x j $$ {\boldsymbol{x}}_j $$ that also contain transversal components to x i j $$ {\boldsymbol{x}}_{ij} $$ . To see this, take for example a rotational motion
d x j d t = Θ ( x j − x i ) , $$ \frac{\mathrm{d}{\boldsymbol{x}}_j}{\mathrm{d}t}=\Theta \left({\boldsymbol{x}}_j-{\boldsymbol{x}}_i\right), $$ (16)
where Θ $$ \Theta $$ is a skew-symmetric matrix (with other seeds, including x i $$ {\boldsymbol{x}}_i $$ , being all fixed). It is easy to see that the plane P i j $$ {P}_{ij} $$ of equidistance between x i $$ {\boldsymbol{x}}_i $$ and x j $$ {\boldsymbol{x}}_j $$ will also rotate with the velocity
v ( x ) = Θ ( x − x i ) . $$ \boldsymbol{v}\left(\boldsymbol{x}\right)=\Theta \left(\boldsymbol{x}-{\boldsymbol{x}}_i\right). $$ (17)
Substituting this velocity field into the transport theorem (13), we find
d | ω i | d t = − 1 r i j ∫ Γ i j Θ ( x − x i ) · x i j d S ( x ) = − | Γ i j | r i j Θ ( m i j − x i ) · x i j = | Γ i j | r i j ( m i j − x i ) · Θ x i j = − | Γ i j | r i j ( m i j − x j ) · Θ x i j = − | Γ i j | r i j ( m i j − x j ) · d x j d t . $$ {\displaystyle \begin{array}{ll}\hfill \frac{\mathrm{d}\mid {\omega}_i\mid }{\mathrm{d}t}& =-\frac{1}{r_{ij}}{\int}_{\Gamma_{ij}}\Theta \left(\boldsymbol{x}-{\boldsymbol{x}}_i\right)\cdotp {\boldsymbol{x}}_{ij}\mathrm{d}S\left(\boldsymbol{x}\right)\\ {}\hfill & =-\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\Theta \left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right)\cdotp {\boldsymbol{x}}_{ij}\\ {}\hfill & =\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right)\cdotp \Theta {\boldsymbol{x}}_{ij}\\ {}\hfill & =-\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_j\right)\cdotp \Theta {\boldsymbol{x}}_{ij}\\ {}\hfill & =-\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_j\right)\cdotp \frac{\mathrm{d}{\boldsymbol{x}}_j}{\mathrm{d}t}.\end{array}} $$ (18)

Remark 2.We note that formula (11) fails when Ω $$ \Omega $$ is nonconvex. This is quite a concerning limitation, which will require a special treatment in future studies. In this paper, all domains are rectangular.

3.2 Voronoi mesh generation

The problem of generating Voronoi meshes is well studied in the literature45 and Voronoi mesh generators have been implemented in a variety of open-source libraries, such as Qhull,46 Voro++47 or CGAL.48 Most of them rely on constructing the Delaunay triangulation, which is a topological dual of a Voronoi grid. However, for our LVM, it is important to have a fast algorithm for computing the Voronoi grid from the moving seeds at every time step. We found that a direct approach to compute Voronoi cells (i.e., avoiding the computation of the dual mesh) is preferable.49, 50 Such a method only involves the data from the nearest neighbors, that is, it can be considered as being local, and hence suits well to parallelization. We illustrate this iterative technique in Figure 1 for the first five iterations k = { 1 , 2 , 3 , 4 , 5 } $$ k=\left\{1,2,3,4,5\right\} $$ . In the first step, that is, for k = 0 $$ k=0 $$ , every cell ω i $$ {\omega}_i $$ is initialized as ω i 0 = Ω $$ {\omega}_i^0=\Omega $$ . We then construct a cell list, which divides the computational domain Ω $$ \Omega $$ into a finite number of partitions (squares in Figure 1) of size comparable to the spatial resolution δ r $$ \delta r $$ (in this paper, we set the side length of those partitions to be 2 δ r $$ 2\delta r $$ ). For a given x i $$ {\boldsymbol{x}}_i $$ (green particle in Figure 1), we find the containing partition P i , 0 ∋ x $$ {P}_{i,0}\ni \boldsymbol{x} $$ and proceed by generating an iterator through a sequence P i , k $$ {P}_{i,k} $$ , k = 1 , 2 , 3 , … $$ k=1,2,3,\dots $$ of all other partitions in the cell list, sorted in ascending order by their distance to P i , 0 $$ {P}_{i,0} $$ . Then, the polytopes
ω i k = ⋂ x j ∈ P i , k x ∈ ω i k − 1 : | x − x i | < | x − x j | , k = 1 , 2 , 3 , … $$ {\omega}_i^k{=\bigcap}_{{\boldsymbol{x}}_j\in {P}_{i,k}}\left\{\boldsymbol{x}\in {\omega}_i^{k-1}:|\boldsymbol{x}-{\boldsymbol{x}}_i|<|\boldsymbol{x}-{\boldsymbol{x}}_j|\right\},\kern1em k=1,2,3,\dots $$ (19)
are constructed in an iterative process. Each ω i k $$ {\omega}_i^k $$ has a radius R i k $$ {R}_i^k $$ , which is the distance between x i $$ {\boldsymbol{x}}_i $$ and the furthest vertex of ω i k $$ {\omega}_i^k $$ . The iterative procedure stops when the Hausdorff distance between P i , 0 $$ {P}_{i,0} $$ and P i , k + 1 $$ {P}_{i,k+1} $$ satisfies
R i k < 1 2 dist P i , 0 , P i , k + 1 , $$ {R}_i^k<\frac{1}{2}\mathrm{dist}\left({P}_{i,0},{P}_{i,k+1}\right), $$ (20)
thus we set ω i = ω i k $$ {\omega}_i={\omega}_i^k $$ , as all remaining points are provably too remote and can be excluded from the computation.
Details are in the caption following the image
FIGURE 1
Open in figure viewerPowerPoint
A Voronoi cell for the green particle in the center can be obtained by intersecting N − 1 $$ N-1 $$ half-planes, one for each other seed. The cell list structure optimizes the computation by focusing on nearby seed only. The orange and blue colors highlight the partition P i , k $$ {P}_{i,k} $$ and the incomplete Voronoi cell ω i k $$ {\omega}_i^k $$ , respectively, for k = 0 , 1 , … , 5 $$ k=0,1,\dots, 5 $$ . [Colour figure can be viewed at wileyonlinelibrary.com]
In the Lagrangian approach, the seeds are displaced with the fluid velocity. Therefore, the Voronoi mesh needs to be regenerated at each time step with possible changes in the mesh connectivity. Starting from the second time step, the process of mesh generation is further accelerated by initializing
ω i 0 = ⋂ j ∈ N i old x ∈ Ω : | x − x i | < | x − x j | , $$ {\omega}_i^0{=\bigcap}_{j\in {N}_i^{\mathrm{old}}}\left\{\boldsymbol{x}\in \Omega :|\boldsymbol{x}-{\boldsymbol{x}}_i|<|\boldsymbol{x}-{\boldsymbol{x}}_j|\right\}, $$ (21)
where N i old $$ {N}_i^{\mathrm{old}} $$ is the set of neighbors of ω i $$ {\omega}_i $$ from the previous mesh configuration. With this heuristics, the number of non-trivial half-plane cuts is reduced to bare minimum. In the context of numerical simulations on moving Voronoi tessellations, the method has the following advantages.
  • If diam ( ω i / δ r ) $$ \mathrm{diam}\left({\omega}_i/\delta r\right) $$ is bounded, O ( N ) $$ O(N) $$ complexity is guaranteed in the mesh generation process.
  • Since the cell constructions are independent processes, the method can be easily parallelized.
  • This technique works both in two and three dimensions.

4 LAGRANGIAN VORONOI METHOD

In this section, we describe and analyze the discrete gradient operator on moving Voronoi grids for a generic smooth function. Then, we present the semi-discrete in space numerical scheme, and finally we provide the details of the semi-implicit time marching algorithm. For the sake of clarity, we first assume no viscous terms in the velocity equation (1a), hence focusing on the incompressible Euler model. Viscous forces will be consistently considered in the numerical scheme and presented at the end of this section.

4.1 Discrete gradient operator

Let us assume that p ( x ) $$ p\left(\boldsymbol{x}\right) $$ is a smooth function defined on Ω $$ \Omega $$ , and p i = p ( x i ) $$ {p}_i=p\left({\boldsymbol{x}}_i\right) $$ are its point values. In order to approximate ∇ p ( x i ) $$ \nabla p\left({\boldsymbol{x}}_i\right) $$ , we use the following representation of the identity matrix:
𝕀 = 1 | ω i | ∫ ∂ ω i ( x − x i ) ⊗ n d S , (22)
which holds for every cell ω i $$ {\omega}_i $$ by virtue of the divergence theorem. For any interior cell ω i $$ {\omega}_i $$ , using the orthogonality between x i j $$ {\boldsymbol{x}}_{ij} $$ and the facet Γ i j $$ {\Gamma}_{ij} $$ (see Equation 8) we obtain:
∇ p ( x i ) = 1 | ω i | ∫ ∂ ω i ( x − x i ) ∇ p ( x i ) · n d S = 1 | ω i | ∑ j ≠ i ∫ Γ i j ( x − x i ) ∇ p ( x i ) · n i j d S = − 1 | ω i | ∑ j | Γ i j | r i j ( m i j − x i ) ∇ p ( x i ) · x i j ≈ − 1 | ω i | ∑ j | Γ i j | r i j p i j ( m i j − x i ) = : ⟨ ∇ p ⟩ i , $$ {\displaystyle \begin{array}{ll}\hfill \nabla p\left({\boldsymbol{x}}_i\right)& =\frac{1}{\mid {\omega}_i\mid }{\int}_{\partial {\omega}_i}\left(\boldsymbol{x}-{\boldsymbol{x}}_i\right)\left(\nabla p\left({\boldsymbol{x}}_i\right)\cdotp \boldsymbol{n}\right)\kern0.3em \mathrm{d}S\\ {}\hfill & =\frac{1}{\mid {\omega}_i\mid}\sum \limits_{j\ne i}{\int}_{\Gamma_{ij}}\left(\boldsymbol{x}-{\boldsymbol{x}}_i\right)\left(\nabla p\left({\boldsymbol{x}}_i\right)\cdotp {\boldsymbol{n}}_{ij}\right)\kern0.3em \mathrm{d}S\\ {}\hfill & =-\frac{1}{\mid {\omega}_i\mid}\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right)\left(\nabla p\left({\boldsymbol{x}}_i\right)\cdotp {\boldsymbol{x}}_{ij}\right)\\ {}\hfill & \approx -\frac{1}{\mid {\omega}_i\mid}\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}{p}_{ij}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right)=: {\left\langle \nabla p\right\rangle}_i,\end{array}} $$ (23)
where p i j = p i − p j $$ {p}_{ij}={p}_i-{p}_j $$ . This is the definition of the discrete gradient operator ⟨ ∇ p ⟩ i $$ {\left\langle \nabla p\right\rangle}_i $$ . The only approximation occurs in the step
∇ p ( x i ) · x i j ≈ p i j , $$ \nabla p\left({\boldsymbol{x}}_i\right)\cdotp {\boldsymbol{x}}_{ij}\approx {p}_{ij}, $$ (24)
which is exact only for polynomials up to first degree. The following error estimate is from Reference 51, p. 804.

Theorem 2.Let p ( x ) ∈ 𝒞 2 , that is, p $$ p $$ is twice continuously differentiable, and let assume d = 2 $$ d=2 $$ in two space dimensions. Then for any interior cell ω i $$ {\omega}_i $$ we have that

| ∇ p ( x i ) − ⟨ ∇ p ⟩ i | ≤ 2 d ‖ ∇ 2 p ‖ ∞ diam ( ω i ) . $$ \mid \nabla p\left({\boldsymbol{x}}_i\right)-{\left\langle \nabla p\right\rangle}_i\mid \le 2d\kern0.3em {\left\Vert {\nabla}^2p\right\Vert}_{\infty}\mathrm{diam}\left({\omega}_i\right). $$ (25)

Proof.Using the idea of (23), we have

| ∇ p ( x i ) − ⟨ ∇ p ⟩ i | ≤ 1 | ω i | ∑ j | Γ i j | r i j ‖ ∇ 2 p ‖ ∞ diam ( ω i ) , $$ \mid \nabla p\left({\boldsymbol{x}}_i\right)-{\left\langle \nabla p\right\rangle}_i\mid \le \frac{1}{\mid {\omega}_i\mid}\sum \limits_j\mid {\Gamma}_{ij}\mid \kern0.3em {r}_{ij}\kern0.3em {\left\Vert {\nabla}^2p\right\Vert}_{\infty}\mathrm{diam}\left({\omega}_i\right), $$ (26)
and we get the desired result by combining this with a formula for the Voronoi cell volume:
| ω | i = 1 2 d ∑ j | Γ i j | r i j . $$ {\left|\omega \right|}_i=\frac{1}{2d}\sum \limits_j\mid {\Gamma}_{ij}\mid \kern0.3em {r}_{ij}. $$ (27)

Remark 3.Intriguingly, the error term does not depend on the mesh quality. We do not require to bound the number of facets or the ratios diam ( ω i ) / r i j $$ \mathrm{diam}\left({\omega}_i\right)/{r}_{ij} $$ .

Remark 4.If the Voronoi mesh is rectangular with the sides Δ x $$ \Delta x $$ and Δ y $$ \Delta y $$ , then (23) becomes equivalent to the central finite difference operator

⟨ ∇ p ⟩ i = p ( x + Δ x , y ) − p ( x − Δ x , y ) 2 Δ x p ( x , y + Δ y ) − p ( x , y − Δ y ) 2 Δ y , $$ {\left\langle \nabla p\right\rangle}_i=\left(\begin{array}{l}\frac{p\left(x+\Delta x,y\right)-p\left(x-\Delta x,y\right)}{2\Delta x}\\ {}\frac{p\left(x,y+\Delta y\right)-p\left(x,y-\Delta y\right)}{2\Delta y}\end{array}\right), $$ (28)
which has second order of accuracy. As we shall demonstrate in Section 5.1, it is possible to obtain a super-linear convergence in velocity if a rectangular grid is used in the initialization. This is understandable, because with decreasing spatial step, the mesh eventually becomes “locally rectangular” throughout the entire simulation time.

Remark 5.By adding a “clever zero”, we can obtain an alternative formulation (valid for interior cells):

⟨ ∇ p ⟩ i = ⟨ ∇ p ⟩ i − ∫ ∂ ω i p i n d S = − 1 | ω i | ∑ j | Γ i j | r i j p i j ( m i j − x i ) + p i x i j = − 1 | ω i | ∑ j | Γ i j | r i j p i j ( m i j − x ‾ i j ) + p ‾ i j x i j , $$ {\displaystyle \begin{array}{ll}\hfill {\left\langle \nabla p\right\rangle}_i& ={\left\langle \nabla p\right\rangle}_i-{\int}_{\partial {\omega}_i}{p}_i\boldsymbol{n}\kern0.3em \mathrm{d}S=-\frac{1}{\mid {\omega}_i\mid}\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({p}_{ij}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right)+{p}_i{\boldsymbol{x}}_{ij}\right)\\ {}\hfill & =-\frac{1}{\mid {\omega}_i\mid}\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({p}_{ij}\left({\boldsymbol{m}}_{ij}-{\overline{\boldsymbol{x}}}_{ij}\right)+{\overline{p}}_{ij}{\boldsymbol{x}}_{ij}\right),\end{array}} $$ (29)
where p ‾ i j = 1 2 ( p i + p j ) $$ {\overline{p}}_{ij}=\frac{1}{2}\left({p}_i+{p}_j\right) $$ and x ‾ i j $$ {\overline{\boldsymbol{x}}}_{ij} $$ is given by (10). This form of the gradient approximation is used in the work of Serrano et al.44 and Springel.15

Remark 6.For a boundary-touching cell, with the facet Γ i j ⊂ ∂ Ω $$ {\Gamma}_{ij}\subset \mathrm{\partial \Omega } $$ , an additional term must be considered:

∇ p ( x i ) = ⟨ ∇ p ⟩ i + 1 | ω i | ∫ Γ i j ( x − x i ) ∇ p ( x i ) · n d S + O ( diam ( ω i ) ) . $$ \nabla p\left({\boldsymbol{x}}_i\right)={\left\langle \nabla p\right\rangle}_i+\frac{1}{\mid {\omega}_i\mid }{\int}_{\Gamma_{ij}}\left(\boldsymbol{x}-{\boldsymbol{x}}_i\right)\left(\nabla p\left({\boldsymbol{x}}_i\right)\cdotp \boldsymbol{n}\right)\kern0.3em \mathrm{d}S+O\left(\mathrm{diam}\left({\omega}_i\right)\right). $$ (30)
For a Robin boundary condition of the type
a p + b ∂ p ∂ n = 0 , $$ ap+b\frac{\partial p}{\partial n}=0, $$ (31)
it is reasonable to approximate the gradient as
∇ p ( x i ) = ⟨ ∇ p ⟩ i − | Γ i | | ω i | a p i b ( m i j − x i ) + O ( diam ( ω i ) ) . $$ \nabla p\left({\boldsymbol{x}}_i\right)={\left\langle \nabla p\right\rangle}_i-\frac{\mid {\Gamma}_i\mid }{\mid {\omega}_i\mid}\frac{a{p}_i}{b}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right)+O\left(\mathrm{diam}\left({\omega}_i\right)\right). $$ (32)
Note that the extra term in (32) disappears for a homogeneous Neumann condition.

Next, we consider a different discretization of the gradient operator. This takes the form
⟨ ∇ ˜ p ⟩ i = 1 | ω i | ∑ j | Γ i j | r i j p i j ( m i j − x j ) , $$ {\left\langle \tilde{\nabla}p\right\rangle}_i=\frac{1}{\mid {\omega}_i\mid}\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}{p}_{ij}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_j\right), $$ (33)
which is motivated by the following “discrete integration by parts.”

Theorem 3.Let p ( x ) ∈ 𝒞 2 and q ( x ) ∈ 𝒞 2 , and let us consider the discrete gradient operators (23) and (33). The following identity holds true for i = 1 , 2 , … , N $$ i=1,2,\dots, N $$ :

∑ i | ω i | ( q i ⟨ ∇ p ⟩ i + p i ⟨ ∇ ˜ q ⟩ i ) = ∑ i p i q i S i . $$ \sum \limits_i\mid {\omega}_i\mid \left({q}_i{\left\langle \nabla p\right\rangle}_i+{p}_i{\left\langle \tilde{\nabla}q\right\rangle}_i\right)=\sum \limits_i{p}_i{q}_i{\boldsymbol{S}}_i. $$ (34)

Proof.Using the previously introduced definitions and some algebra, we find:

∑ i | ω i | ( q i ⟨ ∇ p ⟩ i + p i ⟨ ∇ ˜ q ⟩ i ) = ∑ i ∑ j | Γ i j | r i j − q i p i j ( m i j − x i ) + p i q i j ( m i j − x j ) = ∑ i ∑ j | Γ i j | r i j p i q i x i j + ∑ i ∑ j | Γ i j | r i j ( ( m i j − x i ) q i p j − ( m i j − x j ) p i q j ) . $$ {\displaystyle \begin{array}{ll}\hfill & \sum \limits_i\mid {\omega}_i\mid \left({q}_i{\left\langle \nabla p\right\rangle}_i+{p}_i{\left\langle \tilde{\nabla}q\right\rangle}_i\right)\\ {}\hfill & \kern1em =\sum \limits_i\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left(-{q}_i{p}_{ij}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right)+{p}_i{q}_{ij}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_j\right)\right)\\ {}\hfill & \kern1em =\sum \limits_i\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}{p}_i{q}_i{\boldsymbol{x}}_{ij}+\sum \limits_i\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left(\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right){q}_i{p}_j-\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_j\right){p}_i{q}_j\right).\end{array}} $$ (35)
The second term on the right-hand side vanishes by virtue of anti-symmetry. The first term can be simplified using
S i = ∫ Γ i n i d S = − ∑ j ∫ Γ i j n i d S = ∑ j | Γ i j | r i j x i j , $$ {\boldsymbol{S}}_i={\int}_{\Gamma_i}{\boldsymbol{n}}_i\mathrm{d}S=-\sum \limits_j{\int}_{\Gamma_{ij}}{\boldsymbol{n}}_i\mathrm{d}S=\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}{\boldsymbol{x}}_{ij}, $$ (36)
hence the result.

We shall refer to (23) and (33) as strong and weak gradient, respectively. Unfortunately, our investigation reveals that the weak gradient is no longer first-order exact, but it exhibits an oscillatory nature and cannot be used to obtain reliable point-wise approximations of the continuous gradient operator, especially on highly irregular meshes. See Figure 2 for a comparison between the two gradient operators. The situation is similar to SPH, where a pair of gradient operators is defined, such that they satisfy a discrete integration by parts. Enforcing some degrees of exactness on one operator does not carry over to the other one.20

Details are in the caption following the image
FIGURE 2
Open in figure viewerPowerPoint
The magnitude of ∇ f $$ \nabla f $$ on a square Ω = [ 0 , 1 ] 2 $$ \Omega ={\left[0,1\right]}^2 $$ with an irregular Voronoi grid of 6400 cells (A) for f = 1 π cos ( π x ) cos ( π y ) $$ f=\frac{1}{\pi}\cos \left(\pi x\right)\cos \left(\pi y\right) $$ . The image (B) and (C) show exact solution and the strong gradient (23), respectively, and they are barely distinguishable. The image (D) uses the weak gradient (33) and is infested with spurious noise. (A) Mesh; (B) Exact; (C) Strong; (D) Weak. [Colour figure can be viewed at wileyonlinelibrary.com]
Nonetheless, the weak gradient is useful to derive the variation of the cell volume δ | ω i | $$ \delta \mid {\omega}_i\mid $$ . By virtue of (12), we get
δ | ω i | = ∑ j ∂ | ω i | ∂ x j · δ x j = ∑ j ≠ i ∂ | ω i | ∂ x j · δ x j + ∂ | ω i | ∂ x i · δ x i = − ∑ j ≠ i ∂ | ω i | ∂ x j · δ x i j − S i · δ x i . $$ {\displaystyle \begin{array}{ll}\hfill \delta \mid {\omega}_i\mid & =\sum \limits_j\frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_j}\cdotp \delta {\boldsymbol{x}}_j\\ {}\hfill & =\sum \limits_{j\ne i}\frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_j}\cdotp \delta {\boldsymbol{x}}_j+\frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_i}\cdotp \delta {\boldsymbol{x}}_i\\ {}\hfill & =-\sum \limits_{j\ne i}\frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_j}\cdotp \delta {\boldsymbol{x}}_{ij}-{\boldsymbol{S}}_i\cdotp \delta {\boldsymbol{x}}_i.\end{array}} $$ (37)
Next, we substitute (11), to find
δ | ω i | = ∑ j ≠ i | Γ i j | r i j ( m i j − x j ) · δ x i j − S i · δ x i , $$ \delta \mid {\omega}_i\mid =\sum \limits_{j\ne i}\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_j\right)\cdotp \delta {\boldsymbol{x}}_{ij}-{\boldsymbol{S}}_i\cdotp \delta {\boldsymbol{x}}_i, $$ (38)
and so, we recognize the definition (33):
δ | ω i | = ⟨ ∇ ˜ · δ x ⟩ i − S i · δ x i . $$ \delta \mid {\omega}_i\mid ={\left\langle \tilde{\nabla}\cdotp \delta \boldsymbol{x}\right\rangle}_i-{\boldsymbol{S}}_i\cdotp \delta {\boldsymbol{x}}_i. $$ (39)

4.2 Semi-discrete space discretization

We consider the seeds of a moving Voronoi mesh x i $$ {\boldsymbol{x}}_i $$ being the material particles with point-values of velocity v i $$ {\boldsymbol{v}}_i $$ , density ρ i $$ {\rho}_i $$ and pressure p i $$ {p}_i $$ . The mathematical model is given by the velocity equation (1a), the divergence constraint in weak form (5), and the trajectory equation (1c). For the first exposition of the method we shall ignore the viscous terms and only include them later.

For each cell ω i $$ {\omega}_i $$ , a natural semi-discrete space discretization writes
d v i d t = − 1 ρ i ⟨ ∇ p ⟩ i $$ \kern0.5em \frac{\mathrm{d}{\boldsymbol{v}}_i}{\mathrm{d}t}=-\frac{1}{\rho_i}{\left\langle \nabla p\right\rangle}_i $$ (40a)
∑ i | ω i | v i · ⟨ ∇ φ ⟩ i = 0 , ∀ φ ( x ) , $$ \kern0.5em \sum \limits_i\mid {\omega}_i\mid \kern0.3em {\boldsymbol{v}}_i\cdotp {\left\langle \nabla \varphi \right\rangle}_i=0,\kern1em \forall \kern0.3em \varphi \left(\boldsymbol{x}\right), $$ (40b)
d x i d t = v i . $$ \kern0.5em \frac{\mathrm{d}{\boldsymbol{x}}_i}{\mathrm{d}t}={\boldsymbol{v}}_i. $$ (40c)

Theorem 4.Any solution of the semi-discrete scheme (40) satisfies the following properties.

  • The individual cell volumes | ω i | $$ \mid {\omega}_i\mid $$ are conserved:
    d | ω i | d t = 0 . $$ \frac{\mathrm{d}\mid {\omega}_i\mid }{\mathrm{d}t}=0. $$ (41)
  • The energy
    E = 1 2 ∑ i | ω i | ρ i ‖ v i ‖ 2 , $$ E=\frac{1}{2}\sum \limits_i\mid {\omega}_i\mid \kern0.3em {\rho}_i\kern0.3em {\left\Vert {\boldsymbol{v}}_i\right\Vert}^2, $$ (42)
    is conserved.

Proof.Using the variation (39), the time evolution of ω i $$ {\omega}_i $$ is given by

d | ω i | d t = | ω i | ⟨ ∇ ˜ · v ⟩ i − S i · v i . $$ \frac{\mathrm{d}\mid {\omega}_i\mid }{\mathrm{d}t}=\mid {\omega}_i\mid {\left\langle \tilde{\nabla}\cdotp \boldsymbol{v}\right\rangle}_i-{\boldsymbol{S}}_i\cdotp {\boldsymbol{v}}_i. $$ (43)
Multiplication by a smooth test function φ ( x ) $$ \varphi \left(\boldsymbol{x}\right) $$ and integration over all cells, leads to
∑ i d | ω i | d t φ i = ∑ i | ω i | ⟨ ∇ ˜ · v ⟩ i φ i − ∑ i φ i v i · S i . $$ \sum \limits_i\frac{\mathrm{d}\mid {\omega}_i\mid }{\mathrm{d}t}\kern0.3em {\varphi}_i=\sum \limits_i\mid {\omega}_i\mid {\left\langle \tilde{\nabla}\cdotp \boldsymbol{v}\right\rangle}_i{\varphi}_i-\sum \limits_i{\varphi}_i{\boldsymbol{v}}_i\cdotp {\boldsymbol{S}}_i. $$ (44)
Using the identity (34) and the semi-discrete divergence constraint (40b), from the above relation we find that
∑ i d | ω i | d t φ i = − ∑ i | ω i | v i · ⟨ ∇ φ ⟩ i = 0 , $$ \sum \limits_i\frac{\mathrm{d}\mid {\omega}_i\mid }{\mathrm{d}t}\kern0.3em {\varphi}_i=-\sum \limits_i\mid {\omega}_i\mid {\boldsymbol{v}}_i\cdotp {\left\langle \nabla \varphi \right\rangle}_i=0, $$ (45)
which implies (41) after localization.

In light of the previous result we deduce that the cell volume does not depend on time, thus the time evolution of the total energy (42) yields

d E d t = ∑ i | ω i | ρ i v i · d v i d t . $$ \frac{\mathrm{d}E}{\mathrm{d}t}=\sum \limits_i\mid {\omega}_i\mid \kern0.3em {\rho}_i{\boldsymbol{v}}_i\cdotp \frac{\mathrm{d}{\boldsymbol{v}}_i}{\mathrm{d}t}. $$ (46)
Inserting the balance of momentum (40a) and using the incompressibility constraint (40b), we obtain
d E d t = − ∑ i | ω i | v i · ⟨ ∇ p ⟩ i = 0 . $$ \frac{\mathrm{d}E}{\mathrm{d}t}=-\sum \limits_i\mid {\omega}_i\mid \kern0.3em {\boldsymbol{v}}_i\cdotp {\left\langle \nabla p\right\rangle}_i=0. $$ (47)

4.3 Semi-implicit time discretization

The idea behind the semi-implicit time discretization for incompressible fluid is fairly standard, although it is not frequently applied in the context of LVM (we are aware of only43). It can be understood as Chorin iterations,52 or equivalently, the projection of the velocity field onto the solenoidal space in the sense of Helmholtz decomposition. This requires the solution of an implicit system on the pressure, globally defined on the entire computational domain, which is obtained by combining the velocity equation (1a) with divergence-free constraint (5). On the other hand, the mesh motion is explicit, using the trajectory equation (1c).

Let us consider the time interval T = [ 0 , t f ] $$ T=\left[0,{t}_f\right] $$ , with t ∈ T $$ t\in T $$ and t f $$ {t}_f $$ being the final time of the simulation. The time interval is discretized by a sequence of time steps Δ t = t n + 1 − t n $$ \Delta t={t}^{n+1}-{t}^n $$ , with t n $$ {t}^n $$ denoting the current time. We proceed by introducing a semi-implicit time discretization for the semi-discrete scheme (40).

The Voronoi seed positions are advected explicitly by the velocity field, that is
x i n + 1 = x i n + Δ t v i n , $$ {\boldsymbol{x}}_i^{n+1}={\boldsymbol{x}}_i^n+\Delta t\kern0.3em {\boldsymbol{v}}_i^n, $$ (48)
and the Voronoi mesh is regenerated at the new time level t n + 1 $$ {t}^{n+1} $$ , hence obtaining the new tessellation. All geometry related quantities can now be computed, for example, facet lengths | Γ i j | n + 1 $$ {\left|{\Gamma}_{ij}\right|}^{n+1} $$ , inter-seed distances r i j n + 1 $$ {r}_{ij}^{n+1} $$ and facet midpoints m i j n + 1 $$ {\boldsymbol{m}}_{ij}^{n+1} $$ . As proven in Theorem 4, cell volumes are instead constructed to be constant in time, hence we simply have | ω i | n + 1 = | ω i | n = | ω i | $$ {\left|{\omega}_i\right|}^{n+1}={\left|{\omega}_i\right|}^n=\mid {\omega}_i\mid $$ .
Even though this step does not modify the velocity v i n $$ {\boldsymbol{v}}_i^n $$ per se, it introduces a non-vanishing divergence of the velocity field through the deformation of the mesh. Therefore, the velocity needs to be updated at the next time level by the correct pressure gradient, which can be interpreted as a Lagrangian multiplier enforcing the incompressibility constraint. To this aim, we impose that the new velocity v i n + 1 $$ {\boldsymbol{v}}_i^{n+1} $$ and pressure p i n + 1 $$ {p}_i^{n+1} $$ satisfy
v i n + 1 = v i n − Δ t ρ i ⟨ ∇ p ⟩ i n + 1 , $$ \kern0.5em {\boldsymbol{v}}_i^{n+1}={\boldsymbol{v}}_i^n-\frac{\Delta t}{\rho_i}{\left\langle \nabla p\right\rangle}_i^{n+1}, $$ (49a)
∑ i | ω i | v i n + 1 · ⟨ ∇ φ ⟩ i = 0 , ∀ φ ( x n + 1 ) . $$ \kern0.5em \sum \limits_i\mid {\omega}_i\mid \kern0.3em {\boldsymbol{v}}_i^{n+1}\cdotp {\left\langle \nabla \varphi \right\rangle}_i=0,\kern1em \forall \kern0.3em \varphi \left({\boldsymbol{x}}^{n+1}\right). $$ (49b)
Formal substitution of the velocity equation (49a) into the divergence-free constraint (49b), yields an elliptic problem for the pressure
∑ i | ω i | ρ i ⟨ ∇ p ⟩ i n + 1 · ⟨ ∇ φ ⟩ i = 1 Δ t ∑ i | ω i | v i n · ⟨ ∇ φ ⟩ i . $$ \sum \limits_i\frac{\mid {\omega}_i\mid }{\rho_i}{\left\langle \nabla p\right\rangle}_i^{n+1}\cdotp {\left\langle \nabla \varphi \right\rangle}_i=\frac{1}{\Delta t}\sum \limits_i\mid {\omega}_i\mid \kern0.3em {\boldsymbol{v}}_i^n\cdotp {\left\langle \nabla \varphi \right\rangle}_i. $$ (50)
The associated N × N $$ N\times N $$ system matrix A $$ \mathbf{A} $$ is defined for any function p $$ p $$ and φ $$ \varphi $$ to satisfy the following relation:
∑ i | ω i | ρ i ⟨ ∇ p ⟩ i n + 1 · ⟨ ∇ φ ⟩ i = ∑ i ∑ j φ i A i j p j n + 1 , $$ \sum \limits_i\frac{\mid {\omega}_i\mid }{\rho_i}{\left\langle \nabla p\right\rangle}_i^{n+1}\cdotp {\left\langle \nabla \varphi \right\rangle}_i=\sum \limits_i\sum \limits_j{\varphi}_i\kern0.3em {\mathbf{A}}_{ij}\kern0.3em {p}_j^{n+1}, $$ (51)
thus the matrix A $$ \mathbf{A} $$ is clearly symmetric. The right-hand side of (50) is an N $$ N $$ -element vector representing the linear functional
∑ i b i φ i = 1 Δ t ∑ i | ω i | v i n · ⟨ ∇ φ ⟩ i = | ω i | Δ t ⟨ ∇ ˜ · v ⟩ i n . $$ {\displaystyle \begin{array}{ll}\hfill \sum \limits_i{\mathbf{b}}_i\kern0.3em {\varphi}_i& =\frac{1}{\Delta t}\sum \limits_i\mid {\omega}_i\mid \kern0.3em {\boldsymbol{v}}_i^n\cdotp {\left\langle \nabla \varphi \right\rangle}_i\\ {}\hfill & =\frac{\mid {\omega}_i\mid }{\Delta t}{\left\langle \tilde{\nabla}\cdotp \boldsymbol{v}\right\rangle}_i^n.\end{array}} $$ (52)
The coefficients of the system can be evaluated by setting φ i = δ i k $$ {\varphi}_i={\delta}_{ik} $$ and p j = δ j ℓ $$ {p}_j={\delta}_{j\mathit{\ell}} $$ for fixed indexes ( k , ℓ ) $$ \left(k,\ell \right) $$ . Unfortunately, the matrix is not very sparse because A i j ≠ 0 $$ {\mathbf{A}}_{ij}\ne 0 $$ not only when i , j $$ i,j $$ are neighbors, but also when j $$ j $$ is a neighbor of i $$ i $$ .
In the case when the fluid is incompressible and homogeneous ( ρ i = ρ = c o n s t $$ {\rho}_i=\rho = const $$ ), it is possible to sparsify the problem (51) through the following “approximation of approximation,” in a direct analogy to incompressible SPH. Recalling the strong gradient definition (23) and using the homogeneous condition ρ i = ρ $$ {\rho}_i=\rho $$ , the system matrix in (51) is rewritten as follows:
∑ i | ω i | ρ i ⟨ ∇ p ⟩ i n + 1 · ⟨ ∇ φ ⟩ i = − 1 ρ ∑ i ∑ j | Γ i j | n + 1 r i j n + 1 p i j n + 1 ( m i j n + 1 − x i ) · ⟨ ∇ φ ⟩ i ≈ − 1 ρ ∑ i ∑ j | Γ i j | n + 1 r i j n + 1 p i j n + 1 ( φ ( m i j n + 1 ) − φ i ) = 1 ρ ∑ i ∑ j | Γ i j | n + 1 r i j n + 1 p i j n + 1 φ i . $$ {\displaystyle \begin{array}{ll}\hfill \sum \limits_i\frac{\mid {\omega}_i\mid }{\rho_i}{\left\langle \nabla p\right\rangle}_i^{n+1}\cdotp {\left\langle \nabla \varphi \right\rangle}_i& =-\frac{1}{\rho}\sum \limits_i\sum \limits_j\frac{{\left|{\Gamma}_{ij}\right|}^{n+1}}{r_{ij}^{n+1}}\kern0.3em {p}_{ij}^{n+1}\kern0.3em \left({\boldsymbol{m}}_{ij}^{n+1}-{\boldsymbol{x}}_i\right)\cdotp {\left\langle \nabla \varphi \right\rangle}_i\\ {}\hfill & \approx -\frac{1}{\rho}\sum \limits_i\sum \limits_j\frac{{\left|{\Gamma}_{ij}\right|}^{n+1}}{r_{ij}^{n+1}}\kern0.3em {p}_{ij}^{n+1}\kern0.3em \left(\varphi \left({\boldsymbol{m}}_{ij}^{n+1}\right)-{\varphi}_i\right)\\ {}\hfill & =\frac{1}{\rho}\sum \limits_i\sum \limits_j\frac{{\left|{\Gamma}_{ij}\right|}^{n+1}}{r_{ij}^{n+1}}\kern0.3em {p}_{ij}^{n+1}{\varphi}_i.\end{array}} $$ (53)
The term involving φ ( m i j n + 1 ) $$ \varphi \left({\boldsymbol{m}}_{ij}^{n+1}\right) $$ disappears because of the anti-symmetry of the addends. The new matrix B i j $$ {\mathbf{B}}_{ij} $$ is thus defined such as
∑ j B i j p j n + 1 = 1 ρ ∑ j | Γ i j | n + 1 r i j n + 1 p i j n + 1 , $$ \sum \limits_j{\mathbf{B}}_{ij}{p}_j^{n+1}=\frac{1}{\rho}\sum \limits_j\frac{{\left|{\Gamma}_{ij}\right|}^{n+1}}{r_{ij}^{n+1}}\kern0.3em {p}_{ij}^{n+1}, $$ (54)
and it is much simpler, more sparse and still symmetric compared to the matrix A $$ \mathbf{A} $$ in (51). Figure 3 depicts an illustration of the sparsity of B $$ \mathbf{B} $$ when compared to incompressible SPH. SILVA produces much sparser matrices, which is a great advantage compared to SPH-based methods: for SILVA, the number of non-zeros per node is less than 7, but for SPH it is about 24. We expect that the difference becomes even more pronounced in three space dimensions. In the definition (54), we can recognize the approximation of the Laplacian operator as used in the Finite Volume Method on Voronoi meshes, which generalizes the standard central finite difference operator on Cartesian meshes.53 Since
∑ i ∑ j p i n + 1 B i j p j n + 1 = 1 2 ρ ∑ i ∑ j | Γ i j | n + 1 r i j n + 1 ( p i j n + 1 ) 2 , $$ \sum \limits_i\sum \limits_j{p}_i^{n+1}\kern0.3em {\mathbf{B}}_{ij}\kern0.3em {p}_j^{n+1}=\frac{1}{2\rho}\kern0.3em \sum \limits_i\sum \limits_j\frac{{\left|{\Gamma}_{ij}\right|}^{n+1}}{r_{ij}^{n+1}}{\left({p}_{ij}^{n+1}\right)}^2, $$ (55)
we see that the matrix B $$ \mathbf{B} $$ is positive semi-definite and singular, with kernel generated by a constant vector p i n + 1 ≡ 1 $$ {p}_i^{n+1}\equiv 1 $$ (since Ω $$ \Omega $$ is connected). This implies that an additive constant on the pressure must be added to solve the Poisson problem with Neumann boundary conditions. Luckily, when we use a Krylov solver, like the Conjugate Gradient (CG) or the minimal residual (MINRES) method, this never becomes a real issue, since the matrix B $$ \mathbf{B} $$ is regular in the invariant subspace of vectors with zero average. The right-hand side b $$ \mathbf{b} $$ defined by (52) clearly belongs to this vector space, since
∑ i b i = 1 Δ t ∑ i | ω i | v i n · ⟨ ∇ 1 ⟩ i = 0 . $$ \sum \limits_i{\mathbf{b}}_i=\frac{1}{\Delta t}\sum \limits_i\mid {\omega}_i\mid \kern0.3em {\boldsymbol{v}}_i^n\cdotp {\left\langle \nabla 1\right\rangle}_i=0. $$ (56)
Details are in the caption following the image
FIGURE 3
Open in figure viewerPowerPoint
Example of a sparsity pattern of the left-hand-side matrix in semi-implicit Lagrangian Voronoi approximation (SILVA) and incompressible smoothed particle hydrodynamics (ISPH) on uniformly random distribution of 625 points (Voronoi seeds) in two dimensions. The smoothing length for ISPH is 1 . 5 δ r $$ 1.5\delta r $$ and the Wendland quintic kernel is used. For the sake of readability, the points are sorted by their occurrence in the cell list. (A) SILVA; (B) ISPH.

Once the new pressure field p i n + 1 $$ {p}_i^{n+1} $$ is determined, the divergence-free velocity field v i n + 1 $$ {\boldsymbol{v}}_i^{n+1} $$ is readily updated by means of (49a).

Remark 7.As an alternative to (53) it could be possible to obtain a sparse matrix by adopting the staggered grid approach, along the lines of the semi-implicit finite volume schemes proposed in.38 We leave this option for future investigations.

4.4 Vortex core instability: stabilized pressure gradient

In the SPH method, a well-known numerical artifact, called tensile instability, appears in regions with negative pressure and leads to undesirable clustering of particles.54 In a naive implementation of a LVM, a similar problem arises. Even if every sample point occupies the same area in the sense of the Voronoi mesh, this does not forbid the seeds to approach each other arbitrarily close, leading to stability issues. This problem is particularly evident near pressure minima (such as vortex cores). To shed some light on this problem, let us suppose that close to a seed x i $$ {\boldsymbol{x}}_i $$ , the pressure is given by
p = λ | x − x i | 2 , $$ p=\lambda \kern0.3em {\left|\boldsymbol{x}-{\boldsymbol{x}}_i\right|}^2, $$ (57)
where λ $$ \lambda $$ is a positive constant. Then ∇ p ( x i ) = 0 $$ \nabla p\left({\boldsymbol{x}}_i\right)=0 $$ and the particle should not be accelerated. Unfortunately, this is not what we observe because at the discrete level, the strong gradient operator (23) applied to the above pressure filed yields
⟨ ∇ p ⟩ i = λ ⟨ ∇ | x − x i | 2 ⟩ i = λ | ω i | ∑ j | Γ i j | r i j ( m i j − x i ) ≠ 0 . $$ {\left\langle \nabla p\right\rangle}_i=\lambda {\left\langle \nabla {\left|\boldsymbol{x}-{\boldsymbol{x}}_i\right|}^2\right\rangle}_i=\frac{\lambda }{\mid {\omega}_i\mid}\sum \limits_j\mid {\Gamma}_{ij}\mid \kern0.3em {r}_{ij}\kern0.3em \left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_i\right)\ne 0. $$ (58)
Indeed, a Voronoi cell ω i $$ {\omega}_i $$ can be divided into subcells (triangles for d = 2 $$ d=2 $$ ), each of which is a convex hull of { x i } ∪ Γ i j $$ \left\{{\boldsymbol{x}}_i\right\}\cup {\Gamma}_{ij} $$ and has volume
V i j = 1 d | Γ i j | r i j , $$ {V}_{ij}=\frac{1}{d}\mid {\Gamma}_{ij}\mid {r}_{ij}, $$ (59)
and a centroid
c i j = d d + 1 m i j + 1 d + 1 x i . $$ {\boldsymbol{c}}_{ij}=\frac{d}{d+1}{\boldsymbol{m}}_{ij}+\frac{1}{d+1}{\boldsymbol{x}}_i. $$ (60)
Substitution of (59) and (60) into (58) leads to
⟨ ∇ p ⟩ i = λ ( d + 1 ) | ω i | ∑ j V i j c i j − x i = λ ( d + 1 ) c i − x i , $$ {\left\langle \nabla p\right\rangle}_i=\frac{\lambda \left(d+1\right)}{\mid {\omega}_i\mid}\sum \limits_j{V}_{ij}\left({\boldsymbol{c}}_{ij}-{\boldsymbol{x}}_i\right)=\lambda \left(d+1\right)\left({\boldsymbol{c}}_i-{\boldsymbol{x}}_i\right), $$ (61)
where c i $$ {\boldsymbol{c}}_i $$ is the centroid of ω i $$ {\omega}_i $$ . Therefore, unless x i = c i $$ {\boldsymbol{x}}_i={\boldsymbol{c}}_i $$ , the seed x i $$ {\boldsymbol{x}}_i $$ will be accelerated away from the centroid, hence distorting the cell. This means that we have to remove the potentially nonzero term given by λ ( d + 1 ) c i − x i $$ \lambda \left(d+1\right)\left({\boldsymbol{c}}_i-{\boldsymbol{x}}_i\right) $$ . To determine the positive coefficient λ $$ \lambda $$ , let us compute the Laplacian of the pressure field (57), which leads to
λ = Δ p ( x i ) 2 d . $$ \lambda =\frac{\Delta p\left({\boldsymbol{x}}_i\right)}{2d}. $$ (62)
The above expression is then inserted in (61) to obtain the following definition of a stabilized pressure gradient:
⟨ ∇ p ⟩ i s = ⟨ ∇ p ⟩ i − d + 1 2 d [ ⟨ Δ p ⟩ i ] + c i − x i , $$ {\left\langle \nabla p\right\rangle}_i^{\mathrm{s}}={\left\langle \nabla p\right\rangle}_i-\frac{d+1}{2d}{\left[{\left\langle \Delta p\right\rangle}_i\right]}^{+}\left({\boldsymbol{c}}_i-{\boldsymbol{x}}_i\right), $$ (63)
where ⟨ Δ p ⟩ i $$ {\left\langle \Delta p\right\rangle}_i $$ is evaluated relying on the discrete Laplace operator (64), which will be introduced in the next section. Here, [ f ] + = max ( f , 0 ) $$ {\left[f\right]}^{+}=\max \left(f,0\right) $$ denotes the positive part of a function. We shall use (63) instead of ⟨ ∇ p ⟩ i $$ {\left\langle \nabla p\right\rangle}_i $$ in (49a) for the update of the velocity field. Note that this stabilizer does not introduce any numerical parameter nor does it interfere with the exactness of the discrete gradient on linear functions.

Other stabilization techniques for LVM are suggested in the literature and can be used also in our setting. In Reference 15, the clustering is prevented in the spirit of ALE method, by introducing a velocity of coordinates in the direction defined by the vector c i − x i $$ {\boldsymbol{c}}_i-{\boldsymbol{x}}_i $$ . In,29 a stabilizer is designed which adds a repulsion force nearby particles and is proven to be weakly consistent. We prefer to adopt the stabilizer (63) because it is relatively simple to implement and it preserves the fully Lagrangian nature of SILVA.

4.5 Discrete viscous operator

It remains to discretize the viscous terms in the velocity equation (1a). In a finite volume sense, the Laplacian of a twice differentiable vector field can be estimated as follows:
Δ v ( x i ) ≈ 1 | ω i | ∫ ω i Δ v d x = 1 | ω i | ∫ ∂ ω i ∇ v n d S ≈ − 1 | ω i | ∑ j | Γ i j | r i j v i j = : ⟨ Δ v ⟩ i . $$ {\displaystyle \begin{array}{ll}\hfill \Delta \boldsymbol{v}\left({\boldsymbol{x}}_i\right)& \approx \frac{1}{\mid {\omega}_i\mid }{\int}_{\omega_i}\Delta \boldsymbol{v}\kern0.3em \mathrm{d}\boldsymbol{x}\\ {}\hfill & =\frac{1}{\mid {\omega}_i\mid }{\int}_{\partial {\omega}_i}\nabla \boldsymbol{v}\boldsymbol{n}\kern0.3em \mathrm{d}S\\ {}\hfill & \approx -\frac{1}{\mid {\omega}_i\mid}\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}{\boldsymbol{v}}_{ij}=: {\left\langle \Delta \boldsymbol{v}\right\rangle}_i.\end{array}} $$ (64)
Using the above definition and assuming a constant kinematic viscosity coefficient ν $$ \nu $$ , the viscous force in the incompressible Navier–Stokes model (1) can be easily implemented within each cell ω i $$ {\omega}_i $$ as
f visc , i = ν Δ v ( x i ) ≈ ν ⟨ Δ v ⟩ i = − ν | ω i | ∑ j | Γ i j | r i j v i j , $$ {\boldsymbol{f}}_{\mathrm{visc},i}=\nu \Delta \boldsymbol{v}\left({\boldsymbol{x}}_i\right)\approx \nu {\left\langle \Delta \boldsymbol{v}\right\rangle}_i=-\frac{\nu }{\mid {\omega}_i\mid}\sum \limits_j\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}{\boldsymbol{v}}_{ij}, $$ (65)
with v i j = v i − v j $$ {\boldsymbol{v}}_{ij}={\boldsymbol{v}}_i-{\boldsymbol{v}}_j $$ . Naturally, if viscosity is included, we can no longer expect the conservation of energy E $$ E $$ in (42), since E $$ E $$ represents only the mechanical component of energy and does not take into account entropy production. However, the velocity field is still divergence-free and the cell areas | ω i | $$ \mid {\omega}_i\mid $$ are still preserved. Regarding the time discretization, we include the viscous force right after the advection step (48) in an explicit manner. In this way, we obtain an intermediate velocity field
v i n ∗ = v i n + Δ t f visc , i ( x i n + 1 , v i n ) , $$ {\boldsymbol{v}}_i^{n\ast }={\boldsymbol{v}}_i^n+\Delta t\kern0.3em {\boldsymbol{f}}_{\mathrm{visc},i}\left({\boldsymbol{x}}_i^{n+1},{\boldsymbol{v}}_i^n\right), $$ (66)
which is then projected to a solenoidal space by the implicit pressure step (49) with v n ∗ $$ {\boldsymbol{v}}^{n\ast } $$ in place of v n $$ {\boldsymbol{v}}^n $$ .

Remark 8.To prescribe a Dirichlet condition for the velocity vector of the type

v = v D , x ∈ Γ D , $$ \boldsymbol{v}={\boldsymbol{v}}_D,\kern1em \boldsymbol{x}\in {\Gamma}_D, $$ (67)
on a linear boundary Γ D $$ {\Gamma}_D $$ , we need to take into account the viscous force by which walls act onto Voronoi cells. The force can be introduced by means of a fictitious mirror polygon ω j ′ $$ {\omega}_j^{\prime } $$ , which is the reflection of ω i $$ {\omega}_i $$ with respect to Γ D $$ {\Gamma}_D $$ and which has velocity
v j ′ = 2 v D − v i . $$ {\boldsymbol{v}}_j^{\prime }=2{\boldsymbol{v}}_D-{\boldsymbol{v}}_i. $$ (68)
Including these reflected cells, Equation (65) can be used without modification by setting v i j = v i − v j ′ $$ {\boldsymbol{v}}_{ij}={\boldsymbol{v}}_i-{\boldsymbol{v}}_j^{\prime } $$ . Following the same reasoning, no-slip boundary conditions are obtained by setting v j ′ = − v i $$ {\boldsymbol{v}}_j^{\prime }=-{\boldsymbol{v}}_i $$ , which means v D = 0 $$ {\boldsymbol{v}}_D=\mathbf{0} $$ .

4.6 Summary of the SILVA method

Finally, let us briefly summarize what one time step of SILVA looks like.
  1. Update of the seed positions x i n + 1 $$ {\boldsymbol{x}}_i^{n+1} $$ with (48), hence by solving explicitly the trajectory equation (1c).
  2. Re-generation of the Voronoi mesh according to the procedure detailed in Section 3. Update of all geometry related quantities (facet lengths, midpoints and inter-seed distances).
  3. Explicit computation of the viscous forces using (65).
  4. Computation of the new pressure p i n + 1 $$ {p}_i^{n+1} $$ by implicitly solving the discrete pressure Poisson equation (50) with the matrix B $$ \mathbf{B} $$ given by (54) and the right-hand-side vector b $$ \mathbf{b} $$ given by (52) using the MINRES method.
  5. Update of the divergence-free velocity field v i n + 1 $$ {\boldsymbol{v}}_i^{n+1} $$ by means of (49a) with the stabilized pressure gradient (63).

5 NUMERICAL RESULTS

5.1 Taylor–Green vortex

We consider the Taylor–Green vortex benchmark on the computational domain Ω = [ − 0 . 5 , 0 . 5 ] 2 $$ \Omega ={\left[-0.5,0.5\right]}^2 $$ . This test case has the analytical solution in the form of an exponentially decaying vortex with the velocity field given by
v ( t , x , y ) = cos π x sin π y − sin π x cos π y , exp − 2 t π 2 Re , $$ \boldsymbol{v}\left(t,x,y\right)=\left(\begin{array}{l}\kern1em \cos \pi x\sin \pi y\\ {}-\sin \pi x\cos \pi y,\end{array}\right)\exp \left(-\frac{2t{\pi}^2}{\operatorname{Re}}\right), $$ (69)
while the pressure field is
p ( t , x , y ) = sin 2 π x + sin 2 π x − 1 2 exp − 2 t π 2 Re . $$ p\left(t,x,y\right)=\frac{\sin^2\pi x+{\sin}^2\pi x-1}{2}\exp \left(-\frac{2t{\pi}^2}{\operatorname{Re}}\right). $$ (70)
The total kinetic energy is
E = 1 2 exp − 2 t π 2 Re . $$ E=\frac{1}{2}\exp \left(-\frac{2t{\pi}^2}{\operatorname{Re}}\right). $$ (71)
Re = U 0 L 0 / ν $$ \operatorname{Re}={U}_0\kern0.3em {L}_0/\nu $$ is the Reynolds number and it represents the ratio between inertial and viscous forces in the studied phenomenon. U 0 = 1 $$ {U}_0=1 $$ and L 0 = 1 $$ {L}_0=1 $$ are the reference velocity and domain size, respectively. A free-slip boundary and a compatible initial condition is prescribed. In accordance with Reference 41, the simulation is terminated at time t f = 0 . 2 $$ {t}_f=0.2 $$ , and we measure the energy conservation error as well as the L 2 $$ {L}^2 $$ error of pressure, velocity and the divergence of velocity, evaluated using the discrete operator (33). The mesh convergence is tested on two types of Voronoi meshes: one is initiated as a structured Cartesian mesh, while the other one as an unstructured mesh, see Figure 4. Three different values of Reynolds number are considered, namely Re = { 400 , 1000 , ∞ } $$ \operatorname{Re}=\left\{400,1000,\infty \right\} $$ , and the obtained convergence rates are depicted in Figure 5. The convergence tables to these graphs can be found in B. Compared to the results by Borgers & Peskin,43 we report a super-linear, rather than linear, convergence in velocity and we do not suffer any major issues in the inviscid case Re = ∞ $$ \operatorname{Re}=\infty $$ . However, we also observe a relatively larger error in the pressure field. The divergence of the velocity field is not conserved up to the machine precision, due to the adoption of a sparser matrix and algebraic errors, but has a very fast convergence rate.
Details are in the caption following the image
FIGURE 4
Open in figure viewerPowerPoint
The final time step of Taylor–Green Vortex for N = 16 $$ N=16 $$ , Re = ∞ $$ \operatorname{Re}=\infty $$ . (A) Rectangular grid; (B) Unstructured grid. [Colour figure can be viewed at wileyonlinelibrary.com]
Details are in the caption following the image
FIGURE 5
Open in figure viewerPowerPoint
Errors of velocity, pressure, energy and velocity divergence in the Taylor–Green vortex benchmark. The horizontal axis corresponds to log 10 N $$ {\log}_{10}N $$ , where N $$ N $$ is the number of cells per side of the computational domain. The vertical axis indicates the logarithm of error. We also compare the result for a structured (ST) rectangular and an unstructured (UN) Vogel grid for Re = { 400 , 1000 , ∞ } $$ \operatorname{Re}=\left\{400,1000,\infty \right\} $$ . The dashed triangles indicate what the reference linear and quadratic convergence slopes. The convergence curves on unstructured grids are more erratic for unknown reasons. Nonetheless, the overall convergence rate is comparable. (A) Velocity error; (B) Pressure error; (C) Energy error; (D) Divergence error. [Colour figure can be viewed at wileyonlinelibrary.com]

5.2 Gresho vortex

The Gresho vortex problem is a standard test case for inviscid fluids. The initial conditions impose a vortex with a triangular velocity profile. With no viscosity, the flow field is stable under evolution, but this behavior is difficult to recover numerically. For the initial setup of this test, we refer to Reference 55. The computational domain is initially discretized with three different resolutions, namely with N = 5 0 2 $$ N=5{0}^2 $$ , N = 10 0 2 $$ N=10{0}^2 $$ and N = 20 0 2 $$ N=20{0}^2 $$ Voronoi seeds. The results of the simulation are depicted in Figure 6, and they indicate that SILVA preserves the triangular profile with reasonable accuracy, while exhibiting some diffusive behavior. Furthermore, mesh convergence with the respect to the loss of energy is shown. The color map of the velocity field is shown in Figure 7. Note that the final time t f = 3 $$ {t}_f=3 $$ corresponds to more than three full revolutions of the vortex, which would be clearly impossible to simulate on a Lagrangian mesh with fixed topology. Without using the stabilizer introduced in Section 4.4, we observe the well-known vortex core instability, as illustrated in Figure 8.

Details are in the caption following the image
FIGURE 6
Open in figure viewerPowerPoint
Left: comparison of the tangential velocity along the x $$ x $$ -axis with the exact solution in the Gresho vortex benchmark. The result is at t = 3 $$ t=3 $$ and compares three different resolutions and an analytical solution. Right: time evolution of energy (relative to the initial state). The graph can be compared to the high-order semi-implicit method presented in Reference 33. [Colour figure can be viewed at wileyonlinelibrary.com]
Details are in the caption following the image
FIGURE 7
Open in figure viewerPowerPoint
Gresho vortex at t = { 0 , 1 , 3 } $$ t=\left\{0,1,3\right\} $$ . The color map indicates magnitude of velocity. A group of Voronoi cells is highlighted in green. In the last frame, the vortex structure is starting to deteriorate. The resolution in this figure is 200 × 200 $$ 200\times 200 $$ . [Colour figure can be viewed at wileyonlinelibrary.com]
Details are in the caption following the image
FIGURE 8
Open in figure viewerPowerPoint
Zoom at the vortex core at t = 0 $$ t=0 $$ and t = 0 . 8 $$ t=0.8 $$ with and without stabilization. The Voronoi mesh becomes distorted as seeds are propagated away from their respective centroids. (A) Initial state; (B) Unstable ( t = 0 . 8 $$ t=0.8 $$ ). (C) Stabilized ( t = 0 . 8 $$ t=0.8 $$ ).

5.3 Lid-driven cavity

To test the correct simulation of the viscous forces, we consider the lid-driven cavity problem for an incompressible fluid. The computational domain is given by Ω = [ − 0 . 5 , 0 . 5 ] 2 $$ \Omega ={\left[-0.5,0.5\right]}^2 $$ , and the fluid is initially at rest, that is, p = 0 $$ p=0 $$ and v = 0 $$ \boldsymbol{v}=\mathbf{0} $$ . No-slip wall boundary conditions are defined on the vertical sides ( x = ± 0 . 5 $$ x=\pm 0.5 $$ ) and at the bottom ( y = − 0 . 5 $$ y=-0.5 $$ ) of the domain, while on the top side ( y = 0 . 5 $$ y=0.5 $$ ) the velocity field v = ( 1 , 0 ) $$ \boldsymbol{v}=\left(1,0\right) $$ is imposed. The simulations are performed as time-dependent problems on a Voronoi grid of 10,000 sample points, and four different Reynolds numbers are consider, namely Re = { 100 , 400 , 1000 , 3200 } $$ \operatorname{Re}=\left\{100,400,1000,3200\right\} $$ . An excellent agreement with the notorious referential solution by Ghia et al.56 is achieved and plot in Figure 9. More precisely, the agreement for Reynolds numbers Re = 100 , 400 , 1000 $$ \operatorname{Re}=100,400,1000 $$ is almost perfect. At Re = 3200 $$ \operatorname{Re}=3200 $$ , we observe some discrepancy, presumably because of the numerical diffusion and insufficient resolution near boundary layers. However, SILVA is sufficiently precise to indicate subtle features of the flow, such as the left and right bottom corner vortices as well as the emergence of top left corner vortex for Re = 3200 $$ \operatorname{Re}=3200 $$ , see Figure 10. To emphasize the Lagrangian character of SILVA, Figure 11 shows the trajectories of some Voronoi cells.

Details are in the caption following the image
FIGURE 9
Open in figure viewerPowerPoint
Horizontal velocity u $$ u $$ along the vertical center-line (orange) and vertical velocity v $$ v $$ along the horizontal center-line (blue) in the lid-driven cavity benchmark computed using semi-implicit Lagrangian Voronoi approximation (SILVA) for various Reynolds numbers. We compare the result with the referential solution of Ghia et al.56 (A) Re = 100, t = 10 $$ t=10 $$ ; (B) Re = 400, t = 40 $$ t=40 $$ ; (C) Re = 1000, t = 100 $$ t=100 $$ (D) Re = 3200, t = 320 $$ t=320 $$ . [Colour figure can be viewed at wileyonlinelibrary.com]
Details are in the caption following the image
FIGURE 10
Open in figure viewerPowerPoint
Streamline plots in the lid-driven cavity benchmark. (A) Re = 100, t = 10 $$ t=10 $$ ; (B) Re = 3200, t = 320 $$ t=320 $$ .
Details are in the caption following the image
FIGURE 11
Open in figure viewerPowerPoint
Color-map of the velocity magnitude for Re = 1000 $$ \operatorname{Re}=1000 $$ . A group of Voronoi cells is highlighted in magenta. Some of these cells remain trapped in the corner vortex. (A) t = 90 $$ t=90 $$ ; (B) t = 92 $$ t=92 $$ ; (C) t = 94 $$ t=94 $$ ; (D) t = 96 $$ t=96 $$ ; (E) t = 98 $$ t=98 $$ ; (F) t = 100 $$ t=100 $$ . [Colour figure can be viewed at wileyonlinelibrary.com]

5.4 Rayleigh–Taylor instability

Finally, we present the simulation of a multiphase problem with SILVA, namely the Rayleigh–Taylor instability57 of an inviscid fluid without surface tension. Our setup is the same as in the SPH study presented in Reference 58. The domain is the rectangle Ω = [ 0 , 1 ] × [ 0 , 2 ] $$ \Omega =\left[0,1\right]\times \left[0,2\right] $$ which is discretized with 80,000 Voronoi seeds. The initial density field is given by
ρ ( x , y ) = 1 . 8 y > ϕ ( x ) 1 y < ϕ ( x ) . $$ \rho \left(x,y\right)=\left\{\begin{array}{ll}1.8\kern1em & y>\phi (x)\\ {}1\kern1em & y<\phi (x)\end{array}\right.. $$ (72)
Two immiscible fluids of different densities are involved, which are separated by a curve described as
ϕ ( x ) = 1 − 0 . 15 cos ( 2 π x ) . $$ \phi (x)=1-0.15\cos \left(2\pi x\right). $$ (73)
The densities correspond to Atwood number A = 2 / 7 $$ \mathrm{A}=2/7 $$ . The two fluids begin at rest, have identical viscosity and are subjected to a homogeneous gravitational field. The Reynolds number is Re = 420 $$ \operatorname{Re}=420 $$ and the Froude number is Fr = 1 $$ \mathrm{Fr}=1 $$ . No-slip boundary conditions are imposed on all sides of the domain.
This problem is concerned with an incompressible fluid but with a heterogeneous density field. Hence, the approximation (53) is no longer valid when we need to take into account the gradient of pressure. The correct discrete equation is now given by
− ⟨ Δ p ⟩ i n + 1 = − ρ i Δ t ⟨ ∇ ˜ · v ⟩ i n − 1 ρ i ⟨ ∇ ρ ⟩ i · ⟨ ∇ p ⟩ i n + 1 . $$ -{\left\langle \Delta p\right\rangle}_i^{n+1}=-\frac{\rho_i}{\Delta t}{\left\langle \tilde{\nabla}\cdotp \boldsymbol{v}\right\rangle}_i^n-\frac{1}{\rho_i}{\left\langle \nabla \rho \right\rangle}_i\cdotp {\left\langle \nabla p\right\rangle}_i^{n+1}. $$ (74)
The above system can be solved quite efficiently by means of fixed-point iterations, with m $$ m $$ denoting the current iteration number:
− ⟨ Δ p n + 1 , ( m + 1 ) ⟩ i = − ρ i Δ t ⟨ ∇ ˜ · v ⟩ i n − 1 ρ i ⟨ ∇ ρ ⟩ i · ⟨ ∇ p n + 1 , ( m ) ⟩ i , $$ -{\left\langle \Delta {p}^{n+1,\left(m+1\right)}\right\rangle}_i=-\frac{\rho_i}{\Delta t}{\left\langle \tilde{\nabla}\cdotp \boldsymbol{v}\right\rangle}_i^n-\frac{1}{\rho_i}{\left\langle \nabla \rho \right\rangle}_i\cdotp {\left\langle \nabla {p}^{n+1,(m)}\right\rangle}_i, $$ (75)
starting with p n + 1 , ( 0 ) = p n $$ {p}^{n+1,(0)}={p}^n $$ . The iterative process stops when the condition | p n + 1 , ( m + 1 ) − p n + 1 , ( m ) | < 1 0 − 12 $$ \mid {p}^{n+1,\left(m+1\right)}-{p}^{n+1,(m)}\mid <1{0}^{-12} $$ is satisfied. Figure 12 displays the result of SILVA computation, which are in qualitative agreement with the ISPH solution.58 We also perform a mesh convergence study of this test for three different mesh resolutions ( N = { 60 , 100 , 200 } $$ N=\left\{60,100,200\right\} $$ ), and the results are depicted in Figure 13. We observe that the interface profile between the two immiscible fluids becomes increasingly more smooth, and the numerical artifacts disappear.
Details are in the caption following the image
FIGURE 12
Open in figure viewerPowerPoint
Snapshots of the Rayleigh–Taylor instability at output times t = { 1 , 3 , 5 } $$ t=\left\{1,3,5\right\} $$ . The lighter fluid is orange and the heavier is dark blue. The simulation contained 80,000 Voronoi cells. (A) t = 1 $$ t=1 $$ ; (B) t = 3 $$ t=3 $$ ; (C) t = 5 $$ t=5 $$ . [Colour figure can be viewed at wileyonlinelibrary.com]
Details are in the caption following the image
FIGURE 13
Open in figure viewerPowerPoint
The Rayleigh–Taylor instability at t = 3 $$ t=3 $$ for three different resolutions. N $$ N $$ is the number of Voronoi seeds per shorter side of the domain, so there are 2 N 2 $$ 2{N}^2 $$ Voronoi seeds in total. (A) N = 60; (B) N = 100 $$ N=100 $$ ; (C) N = 200 $$ N=200 $$ . [Colour figure can be viewed at wileyonlinelibrary.com]

6 CONCLUSION

In this paper, a new LVM for the solution of the incompressible Navier–Stokes equations has been presented. The spatial discretization is carried out by means of moving Voronoi cells that are regenerated at each time step with an efficient cell-list-based Voronoi mesh generation technique, optimized for multithreaded time-dependent problems. To overcome the problem related to the vortex-core instability associated with the established LVM gradient operator, we have proposed a new stabilizing procedure, which is notable by the lack of numerical parameters and by preserving the exactness of linear gradients. A semi-implicit time discretization has been developed for the first time in the context of LVM, which discretizes explicitly the trajectory equation, that drives the mesh motion, and the viscous terms in the velocity equation. To enforce the projection of the velocity onto the associated divergence-free manifold, the velocity equation is inserted in the divergence-free constraint, yielding an implicit linear system for the pressure that corresponds to the well-known elliptic Poisson equation. The matrix of the system is provably symmetric and can therefore be solved with very efficient iterative linear solvers like the Conjugate Gradient method or MINRES. The accuracy of the scheme has been assessed in four different test-cases, featuring both viscous and inviscid fluids as well as multiphase flow. Linear convergence has been empirically studied in a Gresho vortex benchmark. Our novel scheme, referred to as SILVA, is able to run long-time simulations without any mesh degeneration, inspired by the so-called reconnection-based algorithms on moving meshes.

SILVA is an interesting alternative to the incompressible SPH method, because of the benefits coming from a sparser matrix associated to the elliptic Poisson system, and a relatively easy implementation of free-slip and Dirichlet boundary conditions. Multiphase problems with sharp interface reconstruction and fluid–structure interaction are among the most promising applications. So far, a limitation of our scheme is the requirement of domain convexity and the inability to treat free surfaces. The benchmarks in this paper are two-dimensional, although we do not foresee major obstacles regarding the extension to three-dimensional problems. Further research could be directed toward improving the order of convergence, both in space (by means of a second-order reconstruction) and in time (using high-order IMEX schemes, such as CNAB integrator or implicit-explicit midpoint rule41). Compressible flows will also be addressed in the future, by solving a mildly nonlinear system for the pressure. For the sake of simplicity, we have used an explicit treatment of the viscous terms, but an implicit approach would be preferable for flows with very small Reynolds number, as presented in Reference 59.

ACKNOWLEDGMENTS

This work was financially supported by the Italian Ministry of University and Research (MUR) in the framework of the PRIN 2022 project number 2022N9BM3N. WB received financial support by Fondazione Cariplo and Fondazione CDP (Italy) under the project number 2022-1895. IP and WB are members of the INdAM GNCS group in Italy. Open access publishing facilitated by Universita degli Studi di Trento, as part of the Wiley - CRUI-CARE agreement.

    APPENDIX A: PROOF OF THEOREM 1

    We remind that Ω $$ \Omega $$ is an open, bounded and convex polytope and the seeds x i ∈ Ω $$ {\boldsymbol{x}}_i\in \Omega $$ are distinct. We wish to prove that for any j ≠ i $$ j\ne i $$ :
    ∂ | ω i | ∂ x j = − | Γ i j | r i j m i j − x j , $$ \frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_j}=-\frac{\mid {\Gamma}_{ij}\mid }{r_{ij}}\left({\boldsymbol{m}}_{ij}-{\boldsymbol{x}}_j\right), $$ (A1)
    and that
    ∂ | ω i | ∂ x i = − ∑ j ≠ i ∂ | ω j | ∂ x i = − ∑ j ≠ i ∂ | ω i | ∂ x j − S i . $$ \frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_i}=-\sum \limits_{j\ne i}\frac{\partial \mid {\omega}_j\mid }{\partial {\boldsymbol{x}}_i}=-\sum \limits_{j\ne i}\frac{\partial \mid {\omega}_i\mid }{\partial {\boldsymbol{x}}_j}-{\boldsymbol{S}}_i. $$ (A2)

    Proof.Let us show (A1) for i = 1 $$ i=1 $$ and j = 2 $$ j=2 $$ . Choosing an appropriate coordinate system, we can freely assume x 1 = 0 $$ {\boldsymbol{x}}_1=\mathbf{0} $$ and

    x 2 = μ ν , $$ {\boldsymbol{x}}_2=\left(\begin{array}{l}\mu \\ {}\boldsymbol{\nu} \end{array}\right), $$ (A3)
    where μ > 0 $$ \mu >0 $$ and ν ∈ ℝ d − 1 $$ \boldsymbol{\nu} \in {\mathbb{R}}^{d-1} $$ . Let us define
    ω ˜ 1 = Ω ∩ ⋂ k = 3 N { x : | x − x 1 | ≤ | x − x k | } . $$ {\tilde{\omega}}_1=\Omega {\cap \bigcap}_{k=3}^N\left\{\boldsymbol{x}:|\boldsymbol{x}-{\boldsymbol{x}}_1|\le |\boldsymbol{x}-{\boldsymbol{x}}_k|\right\}. $$ (A4)
    Then ω ˜ 1 $$ {\tilde{\omega}}_1 $$ does not depend on x 2 $$ {\boldsymbol{x}}_2 $$ and
    ω 1 = { x ∈ ω ˜ 1 : | x − x 1 | ≤ | x − x 2 | } = { z w ∈ ω ˜ 1 : z ≤ ζ ( w ) } , $$ {\omega}_1=\left\{\boldsymbol{x}\in {\tilde{\omega}}_1:|\boldsymbol{x}-{\boldsymbol{x}}_1|\le |\boldsymbol{x}-{\boldsymbol{x}}_2|\right\}=\left\{\left(\begin{array}{l}z\\ {}\boldsymbol{w}\end{array}\right)\in {\tilde{\omega}}_1:z\le \zeta \left(\boldsymbol{w}\right)\right\}, $$ (A5)
    where
    ζ ( w ) = μ 2 + | ν | 2 − 2 ν · w 2 μ . $$ \zeta \left(\boldsymbol{w}\right)=\frac{\mu^2+{\left|\boldsymbol{\nu} \right|}^2-2\boldsymbol{\nu} \cdotp \boldsymbol{w}}{2\mu }. $$ (A6)
    Having this notation in place, we can perform a formal computation:
    ∂ | ω i | ∂ μ = ∂ ∂ μ ∫ ω 1 d x = ∂ ∂ μ ∫ ℝ d − 1 ∫ − ∞ ζ ( w ) 1 ω ˜ 1 ( z , w ) d z d w = ∗ ∫ ℝ d − 1 ∂ ∂ μ ∫ − ∞ ζ ( w ) 1 ω ˜ 1 ( z , w ) d z d w = † ∫ ℝ d − 1 ∂ ζ ∂ μ ( w ) 1 ω ˜ 1 ( ζ ( w ) , w ) d w = 1 μ ∫ ℝ d − 1 ( μ − ζ ( w ) ) 1 ω ˜ 1 ( ζ ( w ) , w ) d w . $$ {\displaystyle \begin{array}{ll}\hfill \frac{\partial \mid {\omega}_i\mid }{\partial \mu }& =\frac{\partial }{\partial \mu }{\int}_{\omega_1}\mathrm{d}\boldsymbol{x}\\ {}\hfill & =\frac{\partial }{\partial \mu }{\int}_{{\mathbb{R}}^{d-1}}{\int}_{-\infty}^{\zeta \left(\boldsymbol{w}\right)}{1}_{{\tilde{\omega}}_1}\left(z,\boldsymbol{w}\right)\mathrm{d}z\mathrm{d}\boldsymbol{w}\\ {}\hfill & \overset{\ast }{=}{\int}_{{\mathbb{R}}^{d-1}}\frac{\partial }{\partial \mu }{\int}_{-\infty}^{\zeta \left(\boldsymbol{w}\right)}{1}_{{\tilde{\omega}}_1}\left(z,\boldsymbol{w}\right)\mathrm{d}z\mathrm{d}\boldsymbol{w}\\ {}\hfill & \overset{\dagger }{=}{\int}_{{\mathbb{R}}^{d-1}}\frac{\partial \zeta }{\partial \mu}\left(\boldsymbol{w}\right){1}_{{\tilde{\omega}}_1}\left(\zeta \left(\boldsymbol{w}\right),\boldsymbol{w}\right)\mathrm{d}\boldsymbol{w}\\ {}\hfill & =\frac{1}{\mu }{\int}_{{\mathbb{R}}^{d-1}}\left(\mu -\zeta \left(\boldsymbol{w}\right)\right){1}_{{\tilde{\omega}}_1}\left(\zeta \left(\boldsymbol{w}\right),\boldsymbol{w}\right)\mathrm{d}\boldsymbol{w}.\end{array}} $$ (A7)
    And similarly:
    ∂ | ω i | ∂ ν = 1 μ ∫ ℝ d − 1 ( ν − w ) 1 ω ˜ 1 ( ζ ( w ) , w ) d w . $$ \frac{\partial \mid {\omega}_i\mid }{\partial \boldsymbol{\nu}}=\frac{1}{\mu }{\int}_{{\mathbb{R}}^{d-1}}\left(\boldsymbol{\nu} -\boldsymbol{w}\right){1}_{{\tilde{\omega}}_1}\left(\zeta \left(\boldsymbol{w}\right),\boldsymbol{w}\right)\mathrm{d}\boldsymbol{w}. $$ (A8)
    Needless to say, it is not a priori clear that all steps in this computation were legal. To begin with, the interchange of the integral and derivative sign ( ∗ $$ \ast $$ ) requires a further justification. So does the usage of Leibniz rule for a discontinuous integrand ( † $$ \dagger $$ ). We shall address these concerns later. Now, we notice that
    w ↦ ζ ( w ) w , $$ \boldsymbol{w}\mapsto \left(\begin{array}{l}\zeta \left(\boldsymbol{w}\right)\\ {}\boldsymbol{w}\end{array}\right), $$ (A9)
    parametrizes a plane (or line, if d = 2 $$ d=2 $$ ). Let us call the plane P 12 $$ {P}_{12} $$ . Then P 12 $$ {P}_{12} $$ has a surface element
    d S = 1 + d ζ d w 2 d w = r 12 μ d w . $$ \mathrm{d}S=\sqrt{1+{\left|\frac{\mathrm{d}\zeta }{\mathrm{d}w}\right|}^2}\mathrm{d}\boldsymbol{w}=\frac{r_{12}}{\mu}\mathrm{d}\boldsymbol{w}. $$ (A10)
    and P 12 ∩ ω ˜ 1 = Γ 12 $$ {P}_{12}\cap {\tilde{\omega}}_1={\Gamma}_{12} $$ . Combining (6), (A8), and (A10) yields
    ∂ | ω 1 | ∂ x 2 = 1 r 12 ∫ Γ 12 ( x 2 − x ) d S ( x ) = − | Γ 12 | r 12 ( m 12 − x 2 ) , $$ \frac{\partial \mid {\omega}_1\mid }{\partial {\boldsymbol{x}}_2}=\frac{1}{r_{12}}{\int}_{\Gamma_{12}}\left({\boldsymbol{x}}_2-\boldsymbol{x}\right)\mathrm{d}S\left(\boldsymbol{x}\right)=-\frac{\mid {\Gamma}_{12}\mid }{r_{12}}\left({\boldsymbol{m}}_{12}-{\boldsymbol{x}}_2\right), $$ (A11)
    which is the sought result (A1). Equation (A2) can be easily deduced from (A1) by writing
    | Ω | = ∑ j | ω j | , $$ \mid \Omega \mid =\sum \limits_j\mid {\omega}_j\mid, $$ (A12)
    and differentiating both sides of the equation with respect to x i $$ {\boldsymbol{x}}_i $$ .

    To justify the step ( † ) $$ \left(\dagger \right) $$ , we would like to verify

    d d ζ ∫ − ∞ ζ 1 ω ˜ 1 ( z , w ) d z = 1 ω ˜ 1 ( ζ , w ) , $$ \frac{\mathrm{d}}{\mathrm{d}\zeta }{\int}_{-\infty}^{\zeta }{1}_{{\tilde{\omega}}_1}\left(z,\boldsymbol{w}\right)\mathrm{d}z={1}_{{\tilde{\omega}}_1}\left(\zeta, \boldsymbol{w}\right), $$ (A13)
    for all w ∈ ℝ d − 1 $$ \boldsymbol{w}\in {\mathbb{R}}^{d-1} $$ . Such claim is quite challenging to prove because it is not true. It only holds when 1 ω ˜ 1 $$ {1}_{{\tilde{\omega}}_1} $$ is continuous at ( ζ , w ) $$ \left(\zeta, \boldsymbol{w}\right) $$ . Fortunately, it is enough to show (A13) for almost every w ∈ ℝ d − 1 $$ \boldsymbol{w}\in {\mathbb{R}}^{d-1} $$ . In other words, we need that ∂ ω ˜ 1 ∩ P 12 $$ \partial {\tilde{\omega}}_1\cap {P}_{12} $$ is a null set with respect to the surface measure d S $$ \mathrm{d}S $$ on P 12 $$ {P}_{12} $$ . To see this, consider that ∂ ω ˜ 1 $$ \partial {\tilde{\omega}}_1 $$ is a subset of a finite union of planes, where each of them falls into one of two categories:
    • a plane Q $$ Q $$ that extends a facet of the polytope ∂ Ω $$ \mathrm{\partial \Omega } $$ ,
    • a plane P 1 k $$ {P}_{1k} $$ , which is the locus of points equidistant to x 1 $$ {\boldsymbol{x}}_1 $$ and some other generating seed x k $$ {\boldsymbol{x}}_k $$ , where k > 2 $$ k>2 $$ .

    In the former case, Ω $$ \Omega $$ is contained in the open half-space defined by the plane Q $$ Q $$ and the inward normal vector. Then, Q ≠ P 12 $$ Q\ne {P}_{12} $$ because P 12 ∩ Ω $$ {P}_{12}\cap \Omega $$ is nonempty. (It is here and only here, where the convexity of Ω $$ \Omega $$ is required.) In the latter case, we have P 1 k ≠ P 12 $$ {P}_{1k}\ne {P}_{12} $$ since x k $$ {\boldsymbol{x}}_k $$ is a reflection of x 1 $$ {\boldsymbol{x}}_1 $$ with respect to P 1 k $$ {P}_{1k} $$ and x k ≠ x 2 $$ {\boldsymbol{x}}_k\ne {\boldsymbol{x}}_2 $$ . Since the planes which compose (a superset of) the boundary of ∂ ω ˜ 1 $$ \partial {\tilde{\omega}}_1 $$ are different from P 12 $$ {P}_{12} $$ , their intersection is either empty or a linear space of lower dimension and hence, a null set in the d S $$ \mathrm{d}S $$ measure.

    To finalize the proof, we need to justify ( ∗ $$ \ast $$ ). Using the dominated convergence theorem (see, e.g., Corol. 5.7 in Reference 61), it suffices to find an integrable function g ( w ) $$ g\left(\boldsymbol{w}\right) $$ such that

    g ( w ) ≥ ∂ ∂ μ ∫ − ∞ ζ ( w ) 1 ω ˜ 1 ( z , w ) d z = | μ − ζ ( w ) | μ 1 ω ˜ 1 ( ζ ( w ) , w ) , $$ g\left(\boldsymbol{w}\right)\ge \left|\frac{\partial }{\partial \mu }{\int}_{-\infty}^{\zeta \left(\boldsymbol{w}\right)}{1}_{{\tilde{\omega}}_1}\left(z,\boldsymbol{w}\right)\mathrm{d}z\right|=\frac{\mid \mu -\zeta \left(\boldsymbol{w}\right)\mid }{\mu }{1}_{{\tilde{\omega}}_1}\left(\zeta \left(\boldsymbol{w}\right),\boldsymbol{w}\right), $$ (A14)
    for almost every w ∈ ℝ d − 1 $$ \boldsymbol{w}\in {\mathbb{R}}^{d-1} $$ and every x 2 $$ {\boldsymbol{x}}_2 $$ in some neighborhood. Let the neighborhood be
    U = { μ ν ∈ Ω : μ > ϵ } ∖ ⋃ k > 2 { x k } , $$ U=\left\{\left(\begin{array}{l}\mu \\ {}\boldsymbol{\nu} \end{array}\right)\in \Omega :\mu >\epsilon \right\}{\setminus \bigcup}_{k>2}\left\{{\boldsymbol{x}}_k\right\}, $$ (A15)
    where ϵ > 0 $$ \epsilon >0 $$ is a fixed positive number. Denoting R $$ R $$ the diameter of Ω $$ \Omega $$ , we find
    ( ζ ( w ) , w ) ∈ ω ˜ 1 ⇒ | ζ ( w ) | ≤ R ∧ | w | ≤ R , $$ \left(\zeta \left(\boldsymbol{w}\right),\boldsymbol{w}\right)\in {\tilde{\omega}}_1\Rightarrow \mid \zeta \left(\boldsymbol{w}\right)\mid \le R\wedge \mid \boldsymbol{w}\mid \le R, $$ (A16)
    and so we satisfy (A14) with
    g ( w ) = 2 R ϵ 1 D ( R ) ( w ) , $$ g\left(\boldsymbol{w}\right)=\frac{2R}{\epsilon }{1}_{D(R)}\left(\boldsymbol{w}\right), $$ (A17)
    where D ( R ) $$ D(R) $$ is the zero-centered unit disk (segment in two dimensions) in ℝ d − 1 $$ {\mathbb{R}}^{d-1} $$ .

    APPENDIX B: TAYLOR–GREEN VORTEX CONVERGENCE TABLES

    Tables B1–B4 show the numerical errors in the Taylor–Green vortex benchmark (see Section 5.1).

    TABLE B1. L 2 $$ {L}^2 $$ velocity error per resolution N $$ N $$ .
    Structured mesh Unstructured mesh
    N Re = 400 Re = 1000 Re = Inf Re = 400 Re = 1000 Re = Inf
    16 8.37E−03 8.37E−03 8.45E−03 1.74E−02 1.84E−02 1.97E−02
    32 2.79E−03 2.15E−03 1.84E−03 3.84E−03 7.98E−03 9.28E−03
    48 1.24E−03 1.27E−03 8.47E−04 2.42E−03 2.36E−03 3.80E−03
    72 5.06E−04 6.33E−04 4.19E−04 6.58E−04 7.29E−04 1.46E−03
    108 2.36E−04 2.67E−04 2.39E−04 2.49E−03 1.67E−03 3.04E−03
    162 1.41E−04 1.44E−04 1.46E−04 3.51E−04 2.26E−04 1.41E−04
    TABLE B2. L 2 $$ {L}^2 $$ pressure error per resolution N $$ N $$ .
    Structured mesh Unstructured mesh
    N Re = 400 Re = 1000 Re = Inf Re = 400 Re = 1000 Re = Inf
    16 3.54E−02 3.63E−02 3.66E−02 2.54E−02 2.54E−02 6.38E−02
    32 1.33E−02 1.33E−02 1.53E−02 4.20E−03 4.20E−03 2.45E−02
    48 7.92E−03 8.55E−03 9.78E−03 1.90E−03 1.90E−03 5.47E−03
    72 5.20E−03 5.16E−03 6.37E−03 1.94E−03 1.94E−03 3.44E−03
    108 3.47E−03 3.47E−03 4.18E−03 2.65E−03 2.65E−03 7.56E−03
    162 2.42E−03 2.44E−03 2.77E−03 1.86E−03 1.86E−03 9.59E−04
    TABLE B3. Total energy error per resolution N $$ N $$ .
    Structured mesh Unstructured mesh
    N Re = 400 Re = 1000 Re = Inf Re = 400 Re = 1000 Re = Inf
    16 2.87E−03 2.87E−03 2.82E−03 6.89E−03 1.18E−02 1.34E−02
    32 1.08E−03 1.02E−03 1.00E−03 4.52E−04 1.71E−02 1.20E−02
    48 6.15E−04 6.05E−04 6.05E−04 6.89E−04 1.07E−03 2.65E−03
    72 4.30E−04 3.78E−04 3.78E−04 1.05E−04 1.45E−04 1.23E−03
    108 2.87E−04 2.65E−04 2.44E−04 2.73E−03 3.84E−03 4.37E−03
    162 1.79E−04 1.79E−04 1.57E−04 8.64E−05 7.71E−05 3.32E−06
    TABLE B4. L 2 $$ {L}^2 $$ divergence error per resolution N $$ N $$ .
    Structured mesh Unstructured mesh
    N Re = 400 Re = 1000 Re = Inf Re = 400 Re = 1000 Re = Inf
    16 9.53E−05 8.82E−05 8.65E−05 3.29E−04 3.04E−04 2.98E−04
    32 1.80E−05 1.01E−05 6.99E−06 2.61E−05 4.39E−05 1.05E−04
    48 4.48E−06 3.95E−06 1.67E−06 2.93E−06 3.95E−06 1.25E−05
    72 1.03E−06 1.23E−06 3.76E−07 1.01E−06 1.05E−06 1.84E−06
    108 1.70E−07 2.23E−07 8.32E−08 2.93E−07 1.07E−06 2.82E−06
    162 1.27E−08 3.22E−08 1.80E−08 6.53E−08 5.03E−08 5.65E−08

    DATA AVAILABILITY STATEMENT

    The algorithm presented in this paper is implemented in the code which is publicly available under the MIT license.60 All other data are available upon reasonable request to the corresponding author.

      The full text of this article hosted at iucr.org is unavailable due to technical difficulties.