A highly scalable massively parallel fast marching method for the eikonal equation

DOI10.1016/J.JCP.2016.12.012MaRDI QIDQ680108zbMATH OpenOpenAlexFDO

Authors Frederick Stern, Jianming Yang

Publication date 22 January 2018

Published in Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.07303

zbMATH Keywords

parallel algorithmdomain decompositiondistance functionlevel seteikonal equationfast marching methodreinitializationmassively parallel implementationnarrow band approachstatic Hamilton-Jacobi equation

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Finite difference methods for boundary value problems involving PDEs (65N06)

Abstract: The fast marching method is a widely used numerical method for solving the Eikonal equation arising from a variety of scientific and engineering fields. It is long deemed inherently sequential and an efficient parallel algorithm applicable to large-scale practical applications is not available in the literature. In this study, we present a highly scalable massively parallel implementation of the fast marching method using a domain decomposition approach. Central to this algorithm is a novel restarted narrow band approach that coordinates the frequency of communications and the amount of computations extra to a sequential run for achieving an unprecedented parallel performance. Within each restart, the narrow band fast marching method is executed; simple synchronous local exchanges and global reductions are adopted for communicating updated data in the overlapping regions between neighboring subdomains and getting the latest front status, respectively. The independence of front characteristics is exploited through special data structures and augmented status tags to extract the masked parallelism within the fast marching method. The efficiency, flexibility, and applicability of the parallel algorithm are demonstrated through several examples. These problems are extensively tested on six grids with up to 1 billion points using different numbers of processes ranging from 1 to 65536. Remarkable parallel speedups are achieved using tens of thousands of processes. Detailed pseudo-codes for both the sequential and parallel algorithms are provided to illustrate the simplicity of the parallel implementation and its similarity to the sequential narrow band fast marching algorithm.

Recommendations

• An easily implemented, block-based fast marching method with superior sequential and parallel performance
• A massive parallel fast marching method
• A fast iterative method for solving the eikonal equation on tetrahedral domains
• A Fast Iterative Method for Eikonal Equations
• A fast iterative method for solving the eikonal equation on triangulated surfaces

Cites work

• scientific article; zbMATH DE number 1349965 (Why is no real title available?)
• A Fast Iterative Method for Eikonal Equations
• A Viscosity Solutions Approach to Shape-From-Shading
• A fast marching level set method for monotonically advancing fronts.
• A fast sweeping method for Eikonal equations
• A note on two problems in connexion with graphs
• A parallel two-scale method for eikonal equations
• An adaptive domain-decomposition technique for parallelization of the fast marching method
• Efficient algorithms for globally optimal trajectories
• Fast two-scale methods for eikonal equations
• Parallel solutions of static Hamilton-Jacobi equations for simulations of geological folds

Cited in

(23)

• Development of efficient and robust eikonal solver variants for first-arrival seismic modeling
• A simple iterative geometry-based interface-preserving reinitialization for the level set method
• A fast iterative method for solving the eikonal equation on tetrahedral domains
• A shared memory parallel multi-mesh fast marching method for re-distancing
• A volume-conserving balanced-force level set method on unstructured meshes using a control volume finite element formulation
• Fast flow computation methods on unstructured tetrahedral meshes for rapid reservoir modelling
• A massive parallel fast marching method
• MG-FIM: a multi-GPU fast iterative method using adaptive domain decomposition
• A multiscale domain decomposition algorithm for boundary value problems for eikonal equations
• An efficient interface capturing method for a large collection of interacting bodies immersed in a fluid
• Shared-memory block-based fast marching method for hierarchical meshes
• A second-order distributed memory parallel fast sweeping method for the eikonal equation
• A fast iterative method for solving the eikonal equation on triangulated surfaces
• Improvement of parallel fast marching method for reconstruction of level set function
• Parallel redistancing using the Hopf-Lax formula
• Overhang control based on front propagation in 3D topology optimization for additive manufacturing
• Hybrid massively parallel fast sweeping method for static Hamilton-Jacobi equations
• High order finite volume schemes for solving the non-conservative convection equations on the unstructured grids
• An easily implemented, block-based fast marching method with superior sequential and parallel performance
• Diffusion-redistanciation schemes for 2D and 3D constrained Willmore flow: application to the equilibrium shapes of vesicles
• A parallel two-scale method for eikonal equations
• A fast Eulerian approach for computation of global isochrons in high dimensions
• An adaptive domain-decomposition technique for parallelization of the fast marching method

This page was built for publication: A highly scalable massively parallel fast marching method for the eikonal equation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q680108)