Ordered line integral methods for solving the eikonal equation

DOI10.1007/S10915-019-01077-ZzbMATH Open1434.65307arXiv1902.06825OpenAlexW2988353054WikidataQ126842995 ScholiaQ126842995MaRDI QIDQ2291900FDOQ2291900

Authors: S. Potter, Maria Kourkina Cameron 

Publication date: 31 January 2020

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Abstract: We present a family of fast and accurate Dijkstra-like solvers for the eikonal equation and factored eikonal equation which compute solutions on a regular grid by solving local variational minimization problems. Our methods converge linearly but compute significantly more accurate solutions than competing first order methods. In 3D, we present two different families of algorithms which significantly reduce the number of FLOPs needed to obtain an accurate solution to the eikonal equation. One method employs a fast search using local characteristic directions to prune unnecessary updates, and the other uses the theory of constrained optimization to achieve the same end. The proposed solvers are more efficient than the standard fast marching method in terms of the relationship between error and CPU time. We also modify our method for use with the additively factored eikonal equation, which can be solved locally around point sources to maintain linear convergence. We conduct extensive numerical simulations and provide theoretical justification for our approach. A library that implements the proposed solvers is available on GitHub.

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

Recommendations

• A Fast Iterative Method for Eikonal Equations
• A fast iterative method for solving the eikonal equation on tetrahedral domains
• A fast iterative method for solving the eikonal equation on triangulated surfaces
• A third order accurate fast marching method for the eikonal equation in two dimensions
• Fast methods for the Eikonal and related Hamilton– Jacobi equations on unstructured meshes

zbMATH Keywords

eikonal equationsemi-Lagrangian methodfast marching methodfactored eikonal equationordered line integral methodsimplified midpoint rule

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Complexity and performance of numerical algorithms (65Y20) Numerical quadrature and cubature formulas (65D32) Second-order nonlinear hyperbolic equations (35L70) Dynamic programming in optimal control and differential games (49L20) Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games (49L25) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12) Hydro- and aero-acoustics (76Q05) Numerical methods for partial differential equations, boundary value problems (65N99)

Cites Work

• Matters computational. Ideas, algorithms, source code.
• Title not available (Why is that?)
• A note on two problems in connexion with graphs
• Level set methods and dynamic implicit surfaces
• Title not available (Why is that?)
• Viscosity Solutions of Hamilton-Jacobi Equations
• Title not available (Why is that?)
• Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and Algorithms
• Efficient fast marching with Finsler metrics
• Anisotropic fast-marching on Cartesian grids using lattice basis reduction
• Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
• A fast sweeping method for Eikonal equations
• Efficient algorithms for globally optimal trajectories
• A fast marching level set method for monotonically advancing fronts.
• Title not available (Why is that?)
• A Fast Iterative Method for Eikonal Equations
• Fast methods for the Eikonal and related Hamilton– Jacobi equations on unstructured meshes
• A viscosity solution method for Shape-From-Shading without image boundary data
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational high frequency wave propagation
• The Discrete Geodesic Problem
• Computing geodesic paths on manifolds
• High order fast sweeping methods for static Hamilton-Jacobi equations
• Fast sweeping methods for factored anisotropic eikonal equations: multiplicative and additive factors
• Legendre-transform-based fast sweeping methods for static Hamilton-Jacobi equations on triangulated meshes
• Some improvements of the fast marching method
• Fast sweeping method for the factored eikonal equation
• O(\(N\)) implementation of the fast marching algorithm
• Numerical Geometry of Non-Rigid Shapes
• Optimal algorithm for shape from shading and path planning
• Fast two-scale methods for eikonal equations
• A Parallel Two-Scale Method for Eikonal Equations
• Convergence analysis of the fast sweeping method for static convex Hamilton-Jacobi equations
• A fast marching algorithm for the factored eikonal equation
• Fast-phase space computation of multiple arrivals
• An \(\mathcal O(N)\) level set method for eikonal equations
• Corner cases, singularities, and dynamic factoring
• Ordered line integral methods for computing the quasi-potential
• An ordered line integral method for computing the quasi-potential in the case of variable anisotropic diffusion
• Computing the quasipotential for nongradient SDEs in 3D

Cited In (7)

• A fast iterative method for solving the eikonal equation on tetrahedral domains
• Numerical geometric acoustics: an eikonal-based approach for modeling sound propagation in 3D environments
• Computing the quasipotential for nongradient SDEs in 3D
• libeikonal
• A fast iterative method for solving the eikonal equation on triangulated surfaces
• A Fast Iterative Method for Eikonal Equations
• Jet Marching Methods for Solving the Eikonal Equation

Uses Software

• Valgrind
• FXT
• hfloat
• scikit-image
• Python
• Algorithm 360
• libolim
• GitHub

This page was built for publication: Ordered line integral methods for solving the eikonal equation

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