Showing 1–11 of 11 results for author: Engwirda, D

Local Time-Stepping for the Shallow Water Equations using CFL Optimized Forward-Backward Runge-Kutta Schemes

Authors: Jeremy R. Lilly, Giacomo Capodaglio, Darren Engwirda, Robert L. Higdon, Mark R. Petersen

Abstract: The Courant-Friedrichs-Lewy (CFL) condition is a well known, necessary condition for the stability of explicit time-stepping schemes that effectively places a limit on the size of the largest admittable time-step for a given problem. We formulate and present a new local time-stepping (LTS) scheme optimized, in the CFL sense, for the shallow water equations (SWEs). This new scheme, called FB-LTS, i… ▽ More The Courant-Friedrichs-Lewy (CFL) condition is a well known, necessary condition for the stability of explicit time-stepping schemes that effectively places a limit on the size of the largest admittable time-step for a given problem. We formulate and present a new local time-stepping (LTS) scheme optimized, in the CFL sense, for the shallow water equations (SWEs). This new scheme, called FB-LTS, is based on the CFL optimized forward-backward Runge-Kutta schemes from Lilly et al. (2023). We show that FB-LTS maintains exact conservation of mass and absolute vorticity when applied to the TRiSK spatial discretization (Ringler et al., 2010), and provide numerical experiments showing that it retains the temporal order of the scheme on which it is based (second order). In terms of computational performance, we show that when applied to a real-world test case on a highly-variable resolution mesh, the MPAS-Ocean implementation of FB-LTS is up to 10 times faster than the classical four-stage, fourth-order Runge-Kutta method (RK4), and 2.3 times faster than an existing strong stability preserving Runge-Kutta based LTS scheme (LTS3). Despite this significant increase in efficiency, the solutions produced by FB-LTS are qualitatively equivalent to those produced by both RK4 and LTS3. △ Less

Submitted 16 May, 2024; originally announced May 2024.

CFL Optimized Forward-Backward Runge-Kutta Schemes for the Shallow Water Equations

Authors: Jeremy R. Lilly, Darren Engwirda, Giacomo Capodaglio, Robert L. Higdon, Mark R. Petersen

Abstract: We present the formulation and optimization of a Runge-Kutta-type time-stepping scheme for solving the shallow water equations, aimed at substantially increasing the effective allowable time-step over that of comparable methods. This scheme, called FB-RK(3,2), uses weighted forward-backward averaging of thickness data to advance the momentum equation. The weights for this averaging are chosen with… ▽ More We present the formulation and optimization of a Runge-Kutta-type time-stepping scheme for solving the shallow water equations, aimed at substantially increasing the effective allowable time-step over that of comparable methods. This scheme, called FB-RK(3,2), uses weighted forward-backward averaging of thickness data to advance the momentum equation. The weights for this averaging are chosen with an optimization process that employs a von Neumann-type analysis, ensuring that the weights maximize the admittable Courant number. Through a simplified local truncation error analysis and numerical experiments, we show that the method is at least second order in time for any choice of weights and exhibits low dispersion and dissipation errors for well-resolved waves. Further, we show that an optimized FB-RK(3,2) can take time-steps up to 2.8 times as large as a popular three-stage, third-order strong stability preserving Runge-Kutta method in a quasi-linear test case. In fully nonlinear shallow water test cases relevant to oceanic and atmospheric flows, FB-RK(3,2) outperforms SSPRK3 in admittable time-step by factors between roughly between 1.6 and 2.2, making the scheme approximately twice as computationally efficient with little to no effect on solution quality. △ Less

Submitted 20 June, 2023; originally announced June 2023.

Storm Surge Modeling as an Application of Local Time-stepping in MPAS-Ocean

Authors: Jeremy R. Lilly, Giacomo Capodaglio, Mark R. Petersen, Steven R. Brus, Darren Engwirda, Robert L. Higdon

Abstract: This paper presents the first scientific application of local time-stepping (LTS) schemes in the Model for Prediction Across Scales-Ocean (MPAS-O). We use LTS schemes in a single-layer, global ocean model that predicts the storm surge around the eastern coast of the United States during Hurricane Sandy. The variable-resolution meshes used are of unprecedentedly high resolution in MPAS-O, containin… ▽ More This paper presents the first scientific application of local time-stepping (LTS) schemes in the Model for Prediction Across Scales-Ocean (MPAS-O). We use LTS schemes in a single-layer, global ocean model that predicts the storm surge around the eastern coast of the United States during Hurricane Sandy. The variable-resolution meshes used are of unprecedentedly high resolution in MPAS-O, containing cells as small as 125 meters wide in Delaware Bay. It is shown that a particular, third-order LTS scheme (LTS3) produces sea-surface height (SSH) solutions that are of comparable quality to solutions produced by the classical four-stage, fourth-order Runge-Kutta method (RK4) with a uniform time step on the same meshes. Furthermore, LTS3 is up to 35% faster in the best cases, showing that LTS schemes are viable for use in MPAS-O with the added benefit of substantially less computational cost. The results of these performance experiments inform us of the requirements for efficient mesh design for LTS schemes. In particular, we see that for LTS to be efficient on a given mesh, it is important to have enough cells using the coarse time-step relative to those using the fine time-step, typically at least 1:5. △ Less

Submitted 27 July, 2022; originally announced July 2022.

Fast Mapping onto Census Blocks

Authors: Jeremy Kepner, Andreas Kipf, Darren Engwirda, Navin Vembar, Michael Jones, Lauren Milechin, Vijay Gadepally, Chris Hill, Tim Kraska, William Arcand, David Bestor, William Bergeron, Chansup Byun, Matthew Hubbell, Michael Houle, Andrew Kirby, Anna Klein, Julie Mullen, Andrew Prout, Albert Reuther, Antonio Rosa, Sid Samsi, Charles Yee, Peter Michaleas

Abstract: Pandemic measures such as social distancing and contact tracing can be enhanced by rapidly integrating dynamic location data and demographic data. Projecting billions of longitude and latitude locations onto hundreds of thousands of highly irregular demographic census block polygons is computationally challenging in both research and deployment contexts. This paper describes two approaches labeled… ▽ More Pandemic measures such as social distancing and contact tracing can be enhanced by rapidly integrating dynamic location data and demographic data. Projecting billions of longitude and latitude locations onto hundreds of thousands of highly irregular demographic census block polygons is computationally challenging in both research and deployment contexts. This paper describes two approaches labeled "simple" and "fast". The simple approach can be implemented in any scripting language (Matlab/Octave, Python, Julia, R) and is easily integrated and customized to a variety of research goals. This simple approach uses a novel combination of hierarchy, sparse bounding boxes, polygon crossing-number, vectorization, and parallel processing to achieve 100,000,000+ projections per second on 100 servers. The simple approach is compact, does not increase data storage requirements, and is applicable to any country or region. The fast approach exploits the thread, vector, and memory optimizations that are possible using a low-level language (C++) and achieves similar performance on a single server. This paper details these approaches with the goal of enabling the broader community to quickly integrate location and demographic data. △ Less

Submitted 1 August, 2020; v1 submitted 6 May, 2020; originally announced May 2020.

Comments: 8 pages, 7 figures, 55 references; accepted to IEEE HPEC 2020

Generalised primal-dual grids for unstructured co-volume schemes

Authors: Darren Engwirda

Abstract: The generation of high-quality staggered unstructured grids is considered, leading to the development of a new optimisation-based strategy designed to construct weighted `Regular-Power' tessellations appropriate for co-volume type numerical discretisation techniques. This new framework aims to extend the conventional Delaunay-Voronoi primal-dual structure; seeking to assemble generalised orthogona… ▽ More The generation of high-quality staggered unstructured grids is considered, leading to the development of a new optimisation-based strategy designed to construct weighted `Regular-Power' tessellations appropriate for co-volume type numerical discretisation techniques. This new framework aims to extend the conventional Delaunay-Voronoi primal-dual structure; seeking to assemble generalised orthogonal tessellations with enhanced geometric quality. The construction of these grids is motivated by the desire to improve the performance and accuracy of numerical methods based on unstructured co-volume type schemes, including various staggered grid techniques for the simulation of fluid dynamics and hyperbolic transport. In this study, a new hybrid optimisation strategy is proposed; seeking to optimise the geometry, topology and weights associated with general, two-dimensional Regular-Power tessellations using a combination of gradient-ascent and energy-based techniques. The performance of this new method is tested experimentally, with a range of complex, multi-resolution primal-dual grids generated for various coastal and regional ocean modelling applications. △ Less

Submitted 31 May, 2018; v1 submitted 3 December, 2017; originally announced December 2017.

JIGSAW-GEO (1.0): locally orthogonal staggered unstructured grid generation for general circulation modelling on the sphere

Authors: Darren Engwirda

Abstract: An algorithm for the generation of non-uniform, locally-orthogonal staggered unstructured spheroidal grids is described. This technique is designed to generate very high-quality staggered Voronoi/Delaunay meshes appropriate for general circulation modelling on the sphere, including applications to atmospheric simulation, ocean-modelling and numerical weather prediction. Using a recently developed… ▽ More An algorithm for the generation of non-uniform, locally-orthogonal staggered unstructured spheroidal grids is described. This technique is designed to generate very high-quality staggered Voronoi/Delaunay meshes appropriate for general circulation modelling on the sphere, including applications to atmospheric simulation, ocean-modelling and numerical weather prediction. Using a recently developed Frontal-Delaunay refinement technique, a method for the construction of high-quality unstructured spheroidal Delaunay triangulations is introduced. A locally-orthogonal polygonal grid, derived from the associated Voronoi diagram, is computed as the staggered dual. It is shown that use of the Frontal-Delaunay refinement technique allows for the generation of very high-quality unstructured triangulations, satisfying a-priori bounds on element size and shape. Grid-quality is further improved through the application of hill-climbing type optimisation techniques. Overall, the algorithm is shown to produce grids with very high element quality and smooth grading characteristics, while imposing relatively low computational expense. A selection of uniform and non-uniform spheroidal grids appropriate for high-resolution, multi-scale general circulation modelling are presented. These grids are shown to satisfy the geometric constraints associated with contemporary unstructured C-grid type finite-volume models, including the Model for Prediction Across Scales (MPAS-O). The use of user-defined mesh-spacing functions to generate smoothly graded, non-uniform grids for multi-resolution type studies is discussed in detail. △ Less

Submitted 6 June, 2017; v1 submitted 28 November, 2016; originally announced November 2016.

Comments: Final revisions, as per: Engwirda, D.: JIGSAW-GEO (1.0): locally orthogonal staggered unstructured grid generation for general circulation modelling on the sphere, Geosci. Model Dev., 10, 2117-2140, https://doi.org/10.5194/gmd-10-2117-2017, 2017

High-order accurate finite-volume formulations for the pressure gradient force in layered ocean models

Authors: Darren Engwirda, Maxwell Kelley, John Marshall

Abstract: The development of a set of high-order accurate finite-volume formulations for evaluation of the pressure gradient force in layered ocean models is described. A pair of new schemes are presented, both based on an integration of the contact pressure force about the perimeter of an associated momentum control-volume. The two proposed methods differ in their choice of control-volume geometries. High-… ▽ More The development of a set of high-order accurate finite-volume formulations for evaluation of the pressure gradient force in layered ocean models is described. A pair of new schemes are presented, both based on an integration of the contact pressure force about the perimeter of an associated momentum control-volume. The two proposed methods differ in their choice of control-volume geometries. High-order accurate numerical integration techniques are employed in both schemes to account for non-linearities in the underlying equation-of-state definitions and thermodynamic profiles, and details of an associated vertical interpolation and quadrature scheme are discussed in detail. Numerical experiments are used to confirm the consistency of the two formulations, and it is demonstrated that the new methods maintain hydrostatic and thermobaric equilibrium in the presence of strongly-sloping layer-wise geometry, non-linear equation-of-state definitions and non-uniform vertical stratification profiles. Additionally, one scheme is shown to maintain high levels of consistency in the presence of non-linear thermodynamic stratification. Use of the new pressure gradient force formulations for hybrid vertical coordinate and/or terrain-following general circulation models is discussed. △ Less

Submitted 18 August, 2016; originally announced August 2016.

A WENO-type slope-limiter for a family of piecewise polynomial methods

Authors: Darren Engwirda, Maxwell Kelley

Abstract: A new, high-order slope-limiting procedure for the Piecewise Parabolic Method (PPM) and the Piecewise Quartic Method (PQM) is described. Following a Weighted Essentially Non-Oscillatory (WENO)-type paradigm, the proposed slope-limiter seeks to reconstruct smooth, non-oscillatory piecewise polynomial profiles as a non-linear combination of the natural and monotone-limited PPM and PQM interpolants.… ▽ More A new, high-order slope-limiting procedure for the Piecewise Parabolic Method (PPM) and the Piecewise Quartic Method (PQM) is described. Following a Weighted Essentially Non-Oscillatory (WENO)-type paradigm, the proposed slope-limiter seeks to reconstruct smooth, non-oscillatory piecewise polynomial profiles as a non-linear combination of the natural and monotone-limited PPM and PQM interpolants. Compared to existing monotone slope-limiting techniques, this new strategy is designed to improve accuracy at smooth extrema, while controlling spurious oscillations in the neighbourhood of sharp features. Using the new slope-limited PPM and PQM interpolants, a high-order accurate Arbitrary-Lagrangian-Eulerian framework for advection-dominated flows is constructed, and its effectiveness is examined using a series of one- and two-dimensional benchmark cases. It is shown that the new WENO-type slope-limiting techniques offer a significant improvement in accuracy compared to existing strategies, allowing the PPM- and PQM- based schemes to achieve fully third- and fifth-order accurate convergence, respectively, for sufficiently smooth problems. △ Less

Submitted 27 June, 2016; originally announced June 2016.

Conforming restricted Delaunay mesh generation for piecewise smooth complexes

Authors: Darren Engwirda

Abstract: A Frontal-Delaunay refinement algorithm for mesh generation in piecewise smooth domains is described. Built using a restricted Delaunay framework, this new algorithm combines a number of novel features, including: (i) an unweighted, conforming restricted Delaunay representation for domains specified as a (non-manifold) collection of piecewise smooth surface patches and curve segments, (ii) a prote… ▽ More A Frontal-Delaunay refinement algorithm for mesh generation in piecewise smooth domains is described. Built using a restricted Delaunay framework, this new algorithm combines a number of novel features, including: (i) an unweighted, conforming restricted Delaunay representation for domains specified as a (non-manifold) collection of piecewise smooth surface patches and curve segments, (ii) a protection strategy for domains containing curve segments that subtend sharply acute angles, and (iii) a new class of off-centre refinement rules designed to achieve high-quality point-placement along embedded curve features. Experimental comparisons show that the new Frontal-Delaunay algorithm outperforms a classical (statically weighted) restricted Delaunay-refinement technique for a number of three-dimensional benchmark problems. △ Less

Submitted 26 July, 2016; v1 submitted 3 June, 2016; originally announced June 2016.

Comments: To appear at the 25th International Meshing Roundtable

Multi-resolution unstructured grid-generation for geophysical applications on the sphere

Authors: Darren Engwirda

Abstract: An algorithm for the generation of non-uniform unstructured grids on ellipsoidal geometries is described. This technique is designed to generate high quality triangular and polygonal meshes appropriate for general circulation modelling on the sphere, including applications to atmospheric and ocean simulation, and numerical weather predication. Using a recently developed Frontal-Delaunay-refinement… ▽ More An algorithm for the generation of non-uniform unstructured grids on ellipsoidal geometries is described. This technique is designed to generate high quality triangular and polygonal meshes appropriate for general circulation modelling on the sphere, including applications to atmospheric and ocean simulation, and numerical weather predication. Using a recently developed Frontal-Delaunay-refinement technique, a method for the construction of high-quality unstructured ellipsoidal Delaunay triangulations is introduced. A dual polygonal grid, derived from the associated Voronoi diagram, is also optionally generated as a by-product. Compared to existing techniques, it is shown that the Frontal-Delaunay approach typically produces grids with near-optimal element quality and smooth grading characteristics, while imposing relatively low computational expense. Initial results are presented for a selection of uniform and non-uniform ellipsoidal grids appropriate for large-scale geophysical applications. The use of user-defined mesh-sizing functions to generate smoothly graded, non-uniform grids is discussed. △ Less

Submitted 1 December, 2015; originally announced December 2015.

Comments: This paper was presented as a research note at the 24th International Meshing Roundtable, University of Texas at Austin, October, 2015

Size-optimal Steiner points for Delaunay-refinement on curved surfaces

Authors: Darren Engwirda, David Ivers

Abstract: An extension of the restricted Delaunay-refinement algorithm for surface mesh generation is described, where a new point-placement scheme is introduced to improve element quality in the presence of mesh size constraints. Specifically, it is shown that the use of off-centre Steiner points, positioned on the faces of the associated Voronoi diagram, typically leads to significant improvements in the… ▽ More An extension of the restricted Delaunay-refinement algorithm for surface mesh generation is described, where a new point-placement scheme is introduced to improve element quality in the presence of mesh size constraints. Specifically, it is shown that the use of off-centre Steiner points, positioned on the faces of the associated Voronoi diagram, typically leads to significant improvements in the shape- and size-quality of the resulting surface tessellations. The new algorithm can be viewed as a Frontal-Delaunay approach -- a hybridisation of conventional Delaunay-refinement and advancing-front techniques in which new vertices are positioned to satisfy both element size and shape constraints. The performance of the new scheme is investigated experimentally via a series of comparative studies that contrast its performance with that of a typical Delaunay-refinement technique. It is shown that the new method inherits many of the best features of classical Delaunay-refinement and advancing-front type methods, leading to the construction of smooth, high quality surface triangulations with bounded radius-edge ratios and convergence guarantees. Experiments are conducted using a range of complex benchmarks, verifying the robustness and practical performance of the proposed scheme. △ Less

Submitted 27 June, 2016; v1 submitted 16 January, 2015; originally announced January 2015.

Comments: Submitted to Computer-Aided Design (23rd International Meshing Roundtable special issue). A short version appears in the proceedings of the 23rd International Meshing Roundtable. (v2 - revisions to description of point-placement scheme, figures.) (v3 - updated to final pre-print version.)