A fast sweeping method for Eikonal equations

2004/05/21 by Hongkai Zhao · 898 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Algorithm #Computer science #Mathematics #Matrix Theory and Algorithms #Numerical Methods and Algorithms

paper · pdf · doi:10.1090/s0025-5718-04-01678-3

published in Mathematics of Computation 74(250), 603-627 (American Mathematical Society (AMS))

crossref issued 2004/05/21 · crossref published 2004/05/21 · crossref published-online 2004/05/21 · openalex publication_date 2004/05/21 · crossref created 2005/01/14 · openalex created_date 2025/10/10 · crossref deposited 2026/04/21 · openalex updated_date 2026/08/05 · crossref indexed 2026/08/08

Abstract

In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses Gauss-Seidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of O ( N ) O(N) for N N grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that 2 n 2ⁿ Gauss-Seidel iterations is enough for the distance function in n n dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.

Cited by

• On a marching level‐set method for extended discontinuous Galerkin methods for incompressible two‐phase flows: Application to two‐dimensional settings
• Manifold-Guided Motion Planning for Tight Assemblies
• A modified static PDE-based approach for multidimensional extrapolation
• The latent variable proximal point algorithm for variational problems with inequality constraints
• Physics-Informed Fourier-DeepONet for a generalized eikonal solution
• Solving Partial Differential Equations on Manifolds From Incomplete Inter-Point Distance
• A fifth-order absolutely convergent fixed-point fast sweeping hybrid alternative WENO scheme for steady state of hyperbolic conservation laws
• An easily-implemented, block-based fast marching method with superior sequential and parallel performance
• Piecewise-Deterministic Optimal Path Planning
• Implicit reconstruction from point cloud: an adaptive level-set-based semi-Lagrangian method
• A multilayer level-set method for eikonal-based traveltime tomography
• Multi-stencils fast marching method for factored eikonal equations with quadratic anisotropy
• Higher order semi-implicit schemes for linear advection equation on Cartesian grids with numerical stability analysis
• PDE-Free Mass-Constrained Learning of Complex Systems with Hidden States
• Improved Fast Iterative Algorithm for Eikonal Equation for GPU Computing
• An Adaptive Finite Element Method for Marker-Driven Level-Set Transport on Hierarchical Meshes
• Scientific review on the Complex Eikonal, and research perspectives for the Ionospheric Ray-tracing and Absorption
• The Vanishing Moment Method for Fully Nonlinear Second Order Partial Differential Equations: Formulation, Theory, and Numerical Analysis
• A PCA Based Model for Surface Reconstruction from Incomplete Point Clouds
• A low complexity algorithm for non-monotonically evolving fronts
• The Closest Point Heat Method for Solving Eikonal Equations on Implicit Surfaces
• Coupled Time-lapse Full Waveform Inversion for Subsurface Flow Problems using Intrusive Automatic Differentiation
• THINC-scaling scheme that unifies VOF and level set methods
• A level-set based finite difference method for the ground state Bose-Einstein condensates in smooth bounded domains
• High order asymptotic preserving Hermite WENO fast sweeping method for the steady-state S_N transport equation
• Learning to Discretize: Solving 1D Scalar Conservation Laws via Deep Reinforcement Learning
• Exploiting Asynchronous Priority Scheduling in Parallel Eikonal Solvers
• Ripple : Simplified Large-Scale Computation on Heterogeneous Architectures with Polymorphic Data Layout
• Comparison study for Level set and Direct Lagrangian methods for computing Willmore flow of closed planar curves
• Reconstruction of 2D line-integrated electron density using angular filter refractometry and a fast marching Eikonal solver
• Joint inversion for Vp, Vp/Vs of the San Fransico Bay Area using ADTomo
• Global-TRANSIT: modeling global historic sailing using a least-cost surface analysis
• Arbitrary Order Solutions for the Eikonal Equation using a Discontinuous Galerkin Method
• A local version of the Hughes model for pedestrian flow
• A level set-based structural optimization code using FEniCS
• Automated Segmentation of Retinal Layers from Optical Coherent Tomography Images Using Geodesic Distance
• PINNeik: Eikonal solution using physics-informed neural networks
• A fast eikonal equation solver using the Schrodinger wave equation
• A hybrid eikonal solver for accurate first-arrival traveltime computation in anisotropic media with strong contrasts
• On the self-similar solutions of the crystalline mean curvature flow in\n three dimensions
• On a marching level-set method for extended discontinuous Galerkin methods for incompressible two-phase flows
• A predictor-corrector scheme for approximating signed distances using finite element methods
• High-Order Signed Distance Transform of Sampled Signals
• Optimality and robustness in path-planning under initial uncertainty
• Deep Eikonal Solvers
• An approximation scheme for an Eikonal Equation with discontinuous\n coefficient
• Quest for the control on the second order derivatives: topology optimization with functional includes the state's curvature
• Convexity Shape Prior for Level Set based Image Segmentation Method
• A dynamic domain decomposition for a class of second order semi-linear equations
• A New Numerical Algorithm for Thermoacoustic and Photoacoustic Tomography with Variable Sound Speed
• NPTC-net: Narrow-Band Parallel Transport Convolutional Neural Network on Point Clouds
• Equivariant Eikonal Neural Networks: Grid-Free, Scalable Travel-Time Prediction on Homogeneous Spaces
• Constructing High-Order Signed Distance Maps from Computed Tomography Data with Application to Bone Morphometry
• A new variational principle for the Euclidean distance function: Linear approach to the non-linear eikonal problem
• High-order WENO-based semi-implicit Newton-type fast sweeping methods for static Hamilton-Jacobi equations
• Convergent approximation of non-continuous surfaces of prescribed\n Gaussian curvature
• Shape-Aware Organ Segmentation by Predicting Signed Distance Maps
• High order finite difference Hermite WENO fast sweeping methods for static Hamilton-Jacobi equations
• Seismic first-arrival traveltime simulation based on reciprocity-constrained PINN
• Level Set Based Shape Prior Segmentation
• A Scalable, Linear-Time Dynamic Cutoff Algorithm for Molecular\n Simulations of Interfacial Systems
• A Mean-Field Game of Evacuation in Multilevel Building
• Neural operators struggle to learn complex PDEs in pedestrian mobility: Hughes model case study
• Calibration of a Macroscopic Coupled People-Epidemic Transport PDE Model via Density and Velocity Computation from Microscopic Data
• A highly efficient 3D level-set grain growth algorithm tailored for ccNUMA architecture
• A Hybrid Lagrangian/Eulerian Collocated Velocity Advection and Projection Method for Fluid Simulation
• A novel fast sweeping method for computing the attenuation operator t^* in absorbing media
• Marchenko Theory, Algorithms, and Applications: A Review
• A novel PET tumor delineation method based on adaptive region-growing and dual-front active contours. [europepmc]
• Energy landscape reveals that the budding yeast cell cycle is a robust and adaptive multi-stage process. [europepmc]
• Comprehensive Simulations for Ultraviolet Lithography Process of Thick SU-8 Photoresist. [europepmc]
• Modeling of Gate Stack Patterning for Advanced Technology Nodes: A Review. [europepmc]
• Interleaving Automatic Segmentation and Expert Opinion for Retinal Conditions. [europepmc]
• Non-Destructive Testing for Cavity Damages in Automated Machines Based on Acoustic Emission Tomography. [europepmc]
• A neural network based global traveltime function (GlobeNN). [europepmc]
• High-Precision Waveform Stacking Location Method for Microseismic Events Based on S-Transform. [europepmc]

Related

• Fast two-scale methods for Eikonal equations
• Improved Fast Iterative Algorithm for Eikonal Equation for GPU Computing
• Ordered Line Integral Methods for Solving the Eikonal Equation
• Fast Methods for Eikonal Equations: an Experimental Survey
• Neighbor-Gradient Single-Pass Method for solving anisotropic eikonal equation