Conference Program: Sections, Titles, and Abstracts

Delaunay-Voronoi Theory and Applications

Learning robust Delaunay/Voronoi (primal-dual) meshes with minimal uncertainty.

Chandrajit L. Bajaj (University of Texas, Austin)


A proof of the invariant-based formula for the linking number and its asymptotic behaviour.

Matthew Bright (University of Liverpool)
Olga Anosova (University of Liverpool)
Vitaliy Kurlin (University of Liverpool)

Abstract: In 1833 Gauss defined the linking number of two disjoint curves in 3-space. For open curves this double integral over the parameterised curves is real-valued and invariant modulo rigid motions or isometries that preserve distances between points, and has been recently used in the elucidation of molecular structures. In 1976 Banchoff geometrically interpreted the linking number between two line segments. An explicit analytic formula based on this interpretation was given in 2000 without proof in terms of 6 isometry invariants: the distance and angle between the segments and 4 coordinates specifying their relative positions. We give a detailed proof of this formula and describe its asymptotic behaviour that wasn't previously studied.

Local groups in Delone sets.

Nikolai Dolbilin (Steklov Mathematical Institute of the RAS)

Abstract: In the paper, we prove that in an arbitrary Delone set \(X\) in 3D space, the subset \(X_6\) of all points from \(X\) at which local groups has axes of the order not greater than 6 is also a Delone set. Here, under the local group at point \(x\in X\) is meant the symmetry group \(S_x(2R)\) of the cluster \(C_x(2R)\) of \(x\) with radius \(2R\), where \(R\) (according to Delone's empty sphere theory) is the radius of the largest empty sphere, that is, the largest sphere free of points of \(X\).

The main result seems to be the first rigorously proved statement on absolutely generic Delone sets which implies substantial statements for Delone sets with strong crystallographic restrictions. For instance, an important observation of Shtogrin on the boundedness of local groups in Delone sets with equivalent \(2R\)-clusters immediately follows from the main result.

In the paper, the crystalline kernel conjecture and its two weaker versions are suggested. According to the crystalline kernel conjecture, in a quite arbitrary Delone set, points with locally crystallographic axes (of order 2, 3, 4, or 6) only inevitably constitute essential part of the set. These conjectures significantly generalize the famous statement of Crystallography on the impossibility of a (global) 5-fold symmetry in a 3D lattice.

Manifolds of triangulations, braid groups of manifolds, and the groups \(\Gamma_{n}^{k}\).

Denis Fedoseev (Moscow State University, Moscow Center for Fundamental and Applied Mathematics)
Vassily Manturov (Moscow Institute of Physics and Technology)
Igor Nikonov (Moscow State University)

Abstract: The spaces of triangulations of a given manifold have been widely studied. The celebrated theorem of Pachner says that any two triangulations of a given manifold can be connected by a sequence of bistellar moves, or Pachner moves. In the present paper we consider groups which naturally appear when considering the set of triangulations with fixed number of simplices of maximal dimension. There are three ways of introducing this groups: the geometrical one, which depends on the metric, the topological one, and the combinatorial one. The second one can be thought of as a braid group of the manifold and, by definition, is an invariant of the topological type of manifold; in a similar way, one can construct the smooth version. We construct a series of groups \(\Gamma_{n}^{k}\) corresponding to Pachner moves of \((k-2)\)-dimensional manifolds and construct a canonical map from the braid group of any \(k\)-dimensional manifold to \(\Gamma_{n}^{k}\) thus getting topological/smooth invariants of these manifolds.

Polygonal and polyhedral Delaunay-Voronoi meshing.

Vladimir Garanzha (Dorodnicyn Computing Center FRC CSC of the RAS)
Liudmila Kudryavtseva (Dorodnicyn Computing Center FRC CSC of the RAS)

Abstract: The problem of constructing a pair of dual convex polyhedra, inscribed and superscribed around a circular paraboloid, is considered. To this end, we build the sequence of pairs of general dual convex polyhedra. The sequence of primal polyhedra should converge to the superscribed polyhedron, while the sequence of dual polyhedra converges to the inscribed polyhedron. Using a lifting analogy, we get a Delaunay partition as a limit of the sequence of radical (weighted Voronoi) partitions, while the dual Voronoi tiling is obtained as a limit of the sequence of weighted Delaunay partitions.

Different rules can be used for building different sequences of dual polyhedra. We are most interested in the case where the vertices of primal polyhedra can move or glue together, meaning that no new faces are allowed for dual polyhedra. These rules essentially define the transformation of the set of the initial spheres into the set of Delaunay spheres using sphere movement, radius variation and sphere elimination as admissible operations. In the general case, one cannot prove that the sequence of primal polyhedra will ever converge to the circumscribed polyhedron since we are interested in the constrained case, where centers or radii of the subset of spheres are constrained. Even though the rigorous foundation (existence theorems) for this problem are still unavailable, we suggest a functional which measures the deviation of the convex polyhedron from the one inscribed into a paraboloid. This functional is the discrete Dirichlet functional for the degree function which is essentially the vertical distance of the dual vertices from the paraboloid. The absolute minimizer of this functional is attained on the constant degree field, meaning that the inscribed polyhedron can be obtained by means of a simple translation. This formulation of the Dirichlet functional for the dual surface is not quadratic since unknowns are vertices of the primal polyhedron.

The transformation of the set of spheres into Delaunay spheres is not unique. The gradient of the above functional defines a manifold describing the evolution of Delaunay spheres. Hence, one can optimize Delaunay-Voronoi meshes by constrained minimization using this manifold as a constraint. Numerical results illustrate polygonal Delaunay meshing for planar domains.

Out-of-core constrained Delaunay tetrahedralizations for large scenes.

Ziya Erkoc (Bilkent University)
Aytek Aman (Bilkent University)
Ugur Gudukbay (Bilkent University)
Hang Si (Weierstrass Institute Berlin)

Abstract: Tetrahedralization algorithms are used for many applications such as Ray Tracing and Finite Element Methods. For most of the applications, constrained tetrahedralization algorithms are chosen because they can preserve input triangles. The constrained tetrahedralization algorithms developed so far might suffer from a lack of memory. We propose an out-of-core near Delaunay constrained tetrahedralization algorithm using the divide-and-conquer paradigm to decrease memory usage. If the expected memory usage is below the user-defined memory limit, we tetrahedralize using TetGen. Otherwise, we subdivide the set of input points into two halves and recursively apply the same idea to the two halves. When compared with the TetGen, our algorithm tetrahedralizes the point clouds using less amount of memory but takes more time and generates tetrahedralizations that do not satisfy the Delaunay criterion at the boundaries of the merged regions. We quantify the error using the aspect-ratio metric. The difference between the tetrahedralizations that our approach produce and the Delaunay tetrahedralization are small and the results are acceptable for most applications.

The singularity set of optimal transportation maps.

Zhongxuan Luo (Dalian University of Technology)
Wei Chen (Dalian University of Technology)
Na Lei (Dalian University of Technology)
Yang Guo (Stony Brook University)
Tong Zhao (INRIA Sophia-Antipolis & Telecom Paris)
Xianfeng Gu (Stony Brook University)

Abstract: Optimal transportation plays an important role in many engineering fields,especially in deep learning. By Brenier theorem, computating optimal transportation maps is reduced to solving Monge-Ampere equations, which in turn is equivalent to construct Alexandrov polytopes. Furthermore, the regularity theory of Monge-Ampere equation explains mode collapsing issue in deep learning. Hence, computingand studying the singularity sets of OT maps become important.In this work, we generalize the concept of medial axis to power medial axis, which describes the singularity sets of optimal transportation maps. Then we propose a computational algorithm based on variational approach using power diagrams.Furthermore, we prove that when the measures are changed homotopically, the corresponding singularity sets of the optimal transportation maps are homotoic equivalent as well.

On decomposition of embedded prismatoids in \(\mathbb{R}^3\) without additional points.

Hang Si (Weierstrass Institute Berlin)

Abstract: This paper considers three-dimensional prismatoids which can be embedded in \(\mathbb{R}^3\). A subclass of this family are twisted prisms, which includes the family of non-triangulable Schönhardt polyhedra. We call a prismatoid decomposable if it can be cut into two smaller prismatoids (which have smaller volumes) without using additional points. Otherwise it is indecomposable. The indecomposable property implies the non-triangulable property of a prismatoid but not vice versa.

In this paper we prove two basic facts about the decomposability of embedded prismatoid in \(\mathbb{R}^3\) with convex bases. Let \(P\) be such a prismatoid, call an edge interior edge of \(P\) if its both endpoints are vertices of \(P\) and its interior lies inside \(P\). Our first result is a condition to characterise indecomposable twisted prisms. It states that a twisted prism is indecomposable without additional points if and only if it allows no interior edge. Our second result shows that any embedded prismatoid in \(\mathbb{R}^3\) with convex base polygons can be decomposed into the union of two sets (one of them may be empty): a set of tetrahedra and a set of indecomposable twisted prisms, such that all elements in these two sets have disjoint interiors.

Update weighted Delaunay triangulations by flips.

Hang Si (Weierstrass Institute Berlin)


Adaptive Meshing

Recent developments for anisotropic mesh adaptation for turbulent flows in aeronautics.

Frédéric Alauzet / Adrien Loseille (INRIA Saclay Ile-de-France)

Abstract: If anisotropic mesh adaptation has been an active field of research for more than a decade, turbulent flows on complex geometries still offer multiple challenges in the quest of certified and accurate numerical predictions. In addition to the many components of the adaptive loop: error estimates, numerical schemes, interpolation, the adaptive mesh generation process remains a crucial step as it should mitigate high quality/high anisotropy to guarantee the stability/accuracy of the flow solver. The talk will review some recent developments within the cavity-framework from anisotropic mesh generation to hybrid boundary layer mesh generation.

Adjoint computation on anisotropic meshes in high-fidelity RANS simulations.

Francesco Clerici (INRIA Saclay Ile-de-France)
Frédéric Alauzet (INRIA Saclay Ile-de-France)

Abstract: In the context of high-fidelity RANS simulation, anisotropic mesh adaptation turns out to be an excellent tool to get mesh-independent solutions on complex geometries. In particular, anisotropic mesh adaptation is used to predict accurately dimensionless quantities such as the lift and the drag coefficients, and, in general, functionals depending on the solution field. Anyway, in order to get the optimal mesh with respect to the accuracy of a goal functional, it is necessary to solve an adjoint system providing the sensitivity of the goal functional with respect to the residuals of the equations. The linear system associated to the adjoint problem revealed to be stiff for RANS equations with a standard solver such as the GMRES preconditioned with several SGS iterations, and hence an alternative method has been developed, which is based on the transient simulation of the RANS adjoint state.

Moving deforming mesh generation based on quasi-isometric functional

Vladimir Garanzha (Dorodnicyn Computing Center FRC CSC of the RAS)
Liudmila Kudryavtseva (Dorodnicyn Computing Center FRC CSC of the RAS)

Abstract: We propose an algorithm which allows for generation of a moving adaptive mesh with a fixed topology using a time-dependent control metric in the computational domain. Each cell of an ideal mesh, at a given time after a local transformation into uniform coordinates related to metric, should be congruent to the same cell at the initial time level. The quasi-isometric functional is used to measure and control the matching between the real and the ideal mesh.

We have found that when global large deformations of the initial mesh are necessary in order to satisfy the mesh compression criteria inside thin moving layers, simple explicit mesh optimization methods fail to follow the metric precisely. Unfortunately, the preconditioned gradient search algorithm for a quasi-isometric functional is very expensive, so that coupling it directly to the flow solver is highly inefficient. In this work, we suggest a very simple and efficient algorithm which is based on the direct mesh interpolation. Our gradient search algorithm is based on the predictor, which constructs the minimization direction (displacement field) for each mesh vertex for a large time step.

Every intermediate mesh computed using this displacement algorithm is guaranteed to be correct. We have found that the length of the computed displacement field is very large compared to the displacement allowed by the flow solver. Hence, the number of computationally expensive implicit minimizations can be significantly reduced. Assuming that the time dependence of the metric is a smooth function, we obtain a mesh deformation/adaptation algorithm which requires one linear solve for about 10 time steps, making it a quite efficient component of the moving mesh flow solver. We have found the IC2-based linear solver by Kaporin to be a very efficient tool, especially for the parallel version of algorithm. 2D and 3D numerical results are presented.

A surface moving mesh PDE method.

Weizhang Huang (University of Kansas)
Avary Kolasinski (Lawrence Livermore National Laboratory)

Abstract: We will present a surface moving mesh method for general surfaces with or without explicit parameterization. The method is an extension of the moving mesh partial differential equation (MMPDE) method that has been developed for bulk meshes. Its moving mesh equation is defined as the gradient system of a meshing energy function, with the nodal mesh velocities being projected onto the underlying surface. Like the bulk mesh situation, we show that any mesh generated by the surface moving mesh method remains nonsingular if it is so initially. Moreover, a surface meshing energy function is presented based on mesh equidistribution and alignment. The main challenges in the development come from the fact that the Jacobian matrix of the affine mapping between the reference element and any simplicial surface element is not square. It is emphasized that the method is developed directly on surface meshes, making no use of any information on surface parameterization. It utilizes surface normal vectors to ensure that the mesh vertices remain on the surface while moving, and also assumes that the initial surface mesh is given. The new method can apply to general surfaces with or without explicit parameterization since the surface normal vectors can be computed based on the current mesh. A selection of two- and three-dimensional examples will be presented.

RBF-VerBSS hybrid method for mesh deformation.

Chang Jihai (Dalian University of Technology)
Yu Fei (Dalian University of Technology)
Cao Jie (Dalian University of Technology)
Guan Zhenqun (Dalian University of Technology)

Abstract: The mesh deformation method has been widely applied to numerical simulation of time-variant problems. In the present study, we proposed a hybrid mesh deformation method based on radial basis functions (RBF) method and vertex-ball-spring-smoothing (VerBSS) method. Firstly, a coarse background mesh which is consistent with the boundary of the computational mesh was generated and deformed by RBF. The internal nodal displacements were duplicated to the corresponding nodes of computational mesh. The perturbed nodes and the boundary nodes were then utilized together to calculate the deformation of the computational mesh by employing VerBSS. By such means, better convergence performance was achieved. Results of numerical examples indicate that the proposed method has higher efficiency and better robustness than conventional RBF method or background mesh method for large scale problem.

Preserved structure constants for red refinements of product elements.

Sergey Korotov (Western Norway University of Applied Sciences)
Jon Eivind Vatne (Western Norway University of Applied Sciences)

Abstract: In this paper we discuss some strategy for red refinements of product elements and show that there are certain structure characteristics (\(d\)-sines of angles formed by certain edges in the initial partition) which remain constant during refinement processes. Such a property immediately implies the validity of the so-called maximum angle condition, which is strongly desired property in interpolation theory and finite element analysis. Our construction also gives a clear refinement scheme preserving shape regularity.

On a comprehensive grid for solving problems having exponential or power–of–first–type layers.

Vladimir Liseikin (Institute of Computational Technologies SB RAS)
Samir Karasuljic (University of Tuzla)
Aleksandr Mukhortov (Novosibirsk State University)
Viktor Paasonen (Institute of Computational Technologies SB RAS)

Abstract: This paper describes an explicit approach for generating layer–resolving grids in problems having exponential or power–of–first–type layers. The grids are generated on the basis of qualitative estimates of solution derivatives in the layers of one-dimensional singularly perturbed problems. The paper presents results of numerical experiments, using appropriate grids and high–order schemes, for two-point boundary-value problems and two–dimensional Navier–Stokes equations.

A uniform convergence analysis for a Bakhvalov-type mesh with an explicitly defined transition point.

Thai Anh Nhan (Holy Names University)

Abstract: For singularly perturbed convection-diffusion problems, the truncation error and barrier-function technique for proving parameter-uniform convergence is well-known for finite-difference methods on Shishkin-type meshes [Roos and Linß, Computing, 63 (1999), pp. 27–45]. In this paper, we show that it is also possible to generalize this technique to a modification of the Bakhvalov mesh, such that the transition point between the fine and crude parts of the mesh only depends on the perturbation parameter and is defined explicitly. We provide a complete analysis for 1D problems for the simplicity of the present paper, but the analysis can be easily extended to 2D problems. With numerical results for 2D problems we show that the finite-difference discretization on the Bakhvalov-type mesh performs better than the Bakhvalov-Shishkin mesh.

Size gradation control for anisotropic hybrid meshes.

Lucille-Marie Tenkès (INRIA Saclay Ile-de-France)
Frédéric Alauzet (INRIA Saclay Ile-de-France)

Abstract: Metric-based generation methods provide high-quality anisotropic meshes. Yet, it is necessary to ensure the smoothness of the metric field in the first place. This is achieved through the so-called "metric gradation" process, that is the correction of the size growth throughout the mesh. The smallest size prescriptions are spread using a metric intersection algorithm. In this paper, we demonstrate the relevance of size gradation control in metric-based hybrid mesh generation using a metric-orthogonal point placement. We also show how to design a gradation process that maximizes the number and quality of structured elements in these hybrid meshes.

An application of the adaptation criterion in the grid generation technology for volumes bounded by the surfaces of revolution.

Olga Ushakova (N.N. Krasovskii Institute of Mathematics and Mechanics UB RAS, Ural Federal University)

Abstract: The experience of application of the adaptation criterion in the grid generation technology developed for volumes bounded by the surfaces of revolution is presented. The technology has been elaborated for numerical modeling the processes of multi-component hydrodynamics. The technology includes several types of algorithms differed by their functional aims and developed for various types of constructions. The basic construction is the volume of revolution formed by the rotation through \(180^{\circ}\) about the axis of the planar curve composed of straight line segments, arcs of circles and ellipses. The generalizations of the volume of revolution (formed by the surfaces of revolution with parallel axes of revolution) and constructions that are the volumes of revolution deformed by other volumes of revolution or their generalizations are considered. The algorithms are developed within the variational approach for construction of nondegenerate optimal grids satisfying the optimality criteria: closeness of a grid to a uniform one (criterion of uniformity), closeness of a grid to an orthogonal one (criterion of orthogonality) and adaptation of a grid under a given function (criterion of adaptation). Earlier in the three-dimensional case, only two optimality criteria are realized: criteria of uniformity and orthogonality. Now, the third criterion that is the criterion of adaptation is implemented. It is applied for an additional control of cell quality. A series of numerical experiments for different monitoring functions is performed. Examples of computed grids are demonstrated.

Adaptive grids for detecting non-monotone waves and instabilities in a non-equilibrium PDE model from porous media.

Paul A. Zegeling (Universiteit Utrecht)

Abstract: Space-time evolution described by nonlinear PDE models involves patterns and qualitative changes induced by parameters. In this talk I will emphasize the importance of both the analysis and computation in relation to a bifurcation problem in a non-equilibrium Richard's equation from hydrology. The extension of this PDE model for the water saturation S, to take into account additional dynamic memory effects, was suggested by Hassanizadeh and Gray in the nineties of the last century. This gives rise to an extra third-order mixed space-time derivative term in the PDE of the form \(\tau ~ \nabla \cdot [f(S) \nabla (S_t)]\).

In one space dimension, traveling wave analysis is able to predict the formation of steep non-monotone waves depending on the parameter \(\tau\). It is shown that, in this framework, theory from applied analysis, accurate numerical PDE solutions and also the experimental observations from the laboratory can be nicely matched. In two space dimensions, the parameters \(\tau\) and the frequency \(\omega\) (appearing in a small perturbation term), predict that the waves may become unstable, thereby initiating so-called gravity-driven fingering structures. This phenomenon can be analysed with a linear stability analysis and its effects are supported by the numerical experiments of the 2D time-dependent PDE model. For this purpose, we have used a sophisticated adaptive grid r-refinement technique based on a scaled monitor function. The numerical experiments in one and two space dimensions show the effectiveness of the adaptive grid solver.

Meshing and CAD

Generation of boundary layer meshes by the enhanced Jump-and-Walk method with a fast collision detecting algorithm

Jie Cao (Dalian University of Technology)
Fei Yu (Dalian University of Technology)
Z.H. Gao (Dalian University of Technology)
S.H. Lo (University of Hong Kong)
Zhenqun Guan (Dalian University of Technology)

Abstract: Boundary layer meshes as an important part of hybrid mesh are often constructed via advancing layer method for RANS fluid simulations. One major difficulty in implementing a robust boundary layer meshing tool is to handle mesh collisions. In this work, the authors propose to enhance the Jump-and-Walk method by constructing a medial surface mesh in a constrained Delaunay triangulation to detect the safe marching space of front points. Medial surface can build a separation wall between adjacent boundary surfaces to prevent the intersection of boundary layer elements, and the computation of the distance between front points and the medial surface can be accelerated by walking through tetrahedra in sequence without additional data structures. A range of tests were performed for several complex configurations to demonstrate the capability of the method.

Global parametrization based on Ginzburg-Landau functional.

Étienne Corman (Université de Lorraine, CNRS, Inria, LORIA)
Victor Blanchi (École Normale Supérieure)
Nicolas Ray (Université de Lorraine, CNRS, Inria, LORIA)
Dmitry Sokolov (Université de Lorraine, CNRS, Inria, LORIA)

Abstract: Quad meshing is a fundamental preprocessing task for many applications (subdivision surfaces, boundary layer simulation). State-of-the-art quad mesh generators proceed in three steps: first a guiding cross field is computed, then a parametrization representing the quads is generated, and finally a mesh is extracted from the parameterization. In this paper we show that in the case of a periodic global parameterization two first steps answer to the same equation and inherently face the same challenges. This new insight allows us to use recent cross field generation algorithms based on Ginzburg-Landau equations to accurately solve the parametrization step. We provide practical evidence that this formulation enables us to overcome common shortcomings in parametrization computation (inaccuracy away from the boundary, singular dipole placement).

Hexahedral mesh generation using voxel field recovery.

Alexandr Karavaev (Udmurt State University)
Sergey Kopysov (Udmurt State University)

Abstract: We consider a modification of the previously developed voxel-based mesh algorithm to generate models given in triangular surface mesh format (STL). Proposed hexahedral mesh generator belongs to the family of grid methods, and its capable to use as source data both volume and surface types of model geometry representation. To define the initial position of mesh nodes, a «signed distance field» volume data file, obtained from the STL geometry, is used. A special projection technique was developed to adapt constructed orthogonal mesh on the models boundary. It provides an approximation of sharp edges and corners and performs before running any other operations with the mesh. Finally, to improve the quality of the mesh, additional procedures were implemented, including boundary layers insertion, bad quality cells splitting, and optimization-based smoothing technique.

Parametrization of plane irregular regions: a semiautomatic approach I.

Pablo Barrera Sánchez (Universidad Nacional Autónoma de México)
Iván Méndez Cruz (Universidad Nacional Autónoma de México)

Abstract: In some problems, the solutions of partial differential equations require to parametrize planar regions. However, it is hard to get suitable parametrizations of irregular regions. In this paper we introduce a method for finding a parametrization of a simply connected irregular region \(\Omega\) in \(\mathbb{R}^{2}\). Our method decomposes \(\Omega\) into a finite collection of admissible subregions. We use compatible parametrizations of the subregions to construct the parametrization of \(\Omega\) as a block structured mesh.

Bottom-up discrete CAD model generation.

Fei Yu (Dalian University of Technology)
Jie Cao (Dalian University of Technology)
Julin Shan (ArcherSim Co. Ltd.)
S.H. Lo (University of Hong Kong)
Zhenqun Guan (Dalian University of Technology)

Abstract: The discrete CAD model made up of triangular facets is the discrete representation of the continuous CAD model, which has been widely used to geometry visualization, mesh generation, and geometry defects elimination. Many geometry defects elimination methods resort to the graphical tessellation. However, it usually lacks the conformity of meshes of different surface patches at the shared border, and its facets may be badly-shaped. This paper addresses this issue from the viewpoint of mesh generation. The discrete CAD model is generated in the bottom-up (i.e., curve-surface) sequence to achieve the mesh conformity. An aligned curve meshing (ACM) is developed to generate the curve mesh whose nodes are aligned with nearby nodes of other curves. By this virtue, the boundary discretization of sliver surfaces (i.e. the extreme thin surface bounded by tangent of near coincident curves) will not intersect. Afterwards, the surface patch is meshed efficiently by combining the lattice tessellation of the surface and the discretization of bounding curves. The presented method is verified with several examples and compared with the tessellation method provided by Open Cascade and Parasolid. It is found that sliver surfaces can be coped with and the mesh quality is better than graphical tessellation.

A hybrid approach to fast indirect quadrilateral mesh generation.

Daniel Zint (Friedrich-Alexander-Universität Erlangen-Nürnberg)
Roberto Grosso (Friedrich-Alexander-Universität Erlangen-Nürnberg)

Abstract: Indirect quadrilateral mesh generation methods are commonly used particularly for numerical simulations due to their adaptiveness to different element sizes across the domain. The well-known Blossom-Quad algorithm generates high quality meshes but has a worst case complexity of \(O(N^2 + N \log N)\). A method which merges triangles using topological operations is less complex, indeed we show that it has a complexity of \(O(N \log N)\), but resulting meshes might have low quality especially near boundaries. We propose a combination of these two methods. Boundary regions are processed by Blossom-Quad and the interior by triangle merging. Post-processing solves quality issues caused by triangle merging. The results are comparable to pure Blossom-Quad but this approach is much faster. Therefore, it is favorable especially on large meshes where the runtime of Blossom-Quad might become troublesome. The efficiency of this hybrid approach is shown on ocean meshes with up to several million triangles.

Numerical Geometry and Applications

On integral-based (transfinite) Laplace coordinates

Alexander Belyaev (Heriot-Watt University)
Pierre-Alain Fayolle (University of Aizu)

Abstract: In this theoretical work, we analyze general constructions for integral-based (transfinite, continuous) barycentric coordinates and consider a simple variational principle to arrive at a continuous version of the Laplace barycentric coordinates. We demonstrate how our approach leads to a general description of the integral-based barycentric coordinates and establish links with Dirichlet energy minimization problems for ruled surfaces. Both the 2D and 3D cases are studied. An application to a surface generation problem is briefly considered.

Polyhedral annexation method for polytope projection in Julia.

Maxim Demenkov (Institute of Control Sciences)

Abstract: We consider a class of oracle-based algorithms for inner polyhedral approximation of convex sets with application to the polytope projection problem. Our method builds a sequence of inner simplicial approximations of the projection, adding new points by optimizing linear functions (constructed from the outer facets of simplices) over the original set of constraints. We provide a thorough bibliography on the related algorithms and describe our method implementation using Julia programming language.

Optimization-based PDE-constrained discontinuity tracking with high-order curved unstructured meshes

Per-Olof Persson (University of California, Berkeley; Lawrence Berkeley National Laboratory)


An improved algorithm for scattered data interpolation using quartic triangular Bézier surfaces.

Krassimira Vlachkova (Sofia University St. Kliment Ohridski)

Abstract: We revisit the problem of interpolation of scattered data in \(\mathbb{R}^3\) and propose a solution based on Nielson's minimum norm network and triangular Bézier patches. We aimed at solving the problem using the least number of polynomial patches of the smallest possible degree. We propose an alternative to the previously known algorithms, see [Clough and Tocher, 1965] and [Shirman and Séquin, 1987, 1991]. Although conceptually similar, our algorithm differs from the previous in all its steps. As a result the complexity of the resulting surface is reduced and its smoothness is improved. We present results of our numerical experiments.

Numerical Methods

Exponential time integrators for unsteady advection-diffusion problems on refined meshes.

Mikhail Botchev (Keldysh Institute of Applied Mathematics of the RAS)

Abstract: Time integration of advection dominated advection-diffusion problems on refined meshes can be a challenging task, since local refinement can lead to a severe time step restriction, whereas standard implicit time stepping is usually hardly suitable for treating advection terms. We show that exponential time integrators can be an efficient, yet conceptually simple, option in this case. Our comparison includes three exponential integrators and one conventional scheme, the two-stage Rosenbrock method ROS2 which has been a popular alternative to splitting methods for solving advection-diffusion problems.

Discrete dissipative structures and relation to meshing.

Klaus Gärtner (m4sim GmbH)

Abstract: For systems with a large and varying energy density one can't expect to resolve all features everywhere. Hence, stating that "the solution of a discretization is in a subspace of the original problem" is not sufficient, because it does not give any hint with respect to stability for finite size discretizations. A short look at Boltzmann-equation and various multi-particle systems shows the charge transport in semiconductors to be a nice example with strong nonlinearities, having moderate but significant deviations with respect to the particle energy distribution function due to large forces and one dominating scattering effect on the time scale of \(10^{-13}s\), which is fast compared with any state transition achieved up to now. The deviations become more significant with shrinking dimensions and in all cases aiming at special, energy dependent reactions, such as light emission and absorption.

As a consequence, unconditionally stable discretizations are desired that preserve the stability properties of the original model equations. This favors boundary conforming Delaunay meshes due to their flexibility and proven stability for the nonlinear systems. On the other hand, model extensions are very limited up to now and, in a particular sense, extreme: a drift-diffusion approximation as a working horse on the one end, the Keldysh-formalism (NEGF) on the another, and not much in between. However, as long as one is interested in systems which show large amplifications and limited fluctuations, better approximations (more Boltzmann-like equations) are of interest and quantum mechanics should supply the cross sections. It is to expect that the meshing requirements for an extended approach will include what is needed for drift-diffusion. The talk exercises this for Fermi-statistics in some detail.

Efficient steady flow computations with exponential multigrid methods

Shu-Jie Li (Beijing Computational Science Research Center)

Abstract: A exponential multigrid framework is realized and assessed with a modal high-order discontinuous Galerkin method in space. The algorithm based on a global coupling, exponential time integration scheme provides strong damping effects to accelerate the convergence towards the steady-state, while high-frequency, high-order spatial error modes are smoothed out with a \(s\)-stage preconditioned Runge-Kutta method. Numerical studies show that the exponential time integration substantially improves the damping and propagative efficiency of Runge-Kutta time-stepping for use with the \(p\)-multigrid method, yielding rapid and \(p\)-independent convergences to steady flows in both two and three dimensions.

Fully-implicit collocated Finite Volume Method for the unsteady incompressible Navier-Stokes problem

Kirill Terekhov (Marchuk Institute of Numerical Mathematics of the RAS)

Abstract: This article introduces a collocated finite-volume method for the incompressible Navier-Stokes equations. Based on the linearity assumption of the velocity and pressure unknowns, the coupled one-sided flux expression is derived. Analysis and correction of the eigenvalues in the matrix coefficients of the vector flux expression result in the inf-sup stable method. A single continuous flux expression follows from the continuity of the one-sided flux approximations. As a result, the conservation for the momentum and the divergence is discretely exact. The method handles general polyhedral meshes but requires an artificial pressure boundary condition for the pressure gradient reconstruction.