Ordered line integral methods for solving the eikonal equation
From MaRDI portal
Publication:2291900
eikonal equationsemi-Lagrangian methodfast marching methodfactored eikonal equationordered line integral methodsimplified midpoint rule
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)
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.
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
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3658896 (Why is no real title available?)
- scientific article; zbMATH DE number 43417 (Why is no real title available?)
- scientific article; zbMATH DE number 1239298 (Why is no real title available?)
- scientific article; zbMATH DE number 1349965 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- A Fast Iterative Method for Eikonal Equations
- A fast marching algorithm for the factored eikonal equation
- 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
- A viscosity solution method for Shape-From-Shading without image boundary data
- An \(\mathcal O(N)\) level set method for eikonal equations
- An ordered line integral method for computing the quasi-potential in the case of variable anisotropic diffusion
- Anisotropic fast-marching on Cartesian grids using lattice basis reduction
- Computational high frequency wave propagation
- Computing geodesic paths on manifolds
- Computing the quasipotential for nongradient SDEs in 3D
- Convergence analysis of the fast sweeping method for static convex Hamilton-Jacobi equations
- Corner cases, singularities, and dynamic factoring
- Efficient algorithms for globally optimal trajectories
- Efficient fast marching with Finsler metrics
- Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
- Fast methods for the Eikonal and related Hamilton– Jacobi equations on unstructured meshes
- Fast sweeping method for the factored eikonal equation
- Fast sweeping methods for factored anisotropic eikonal equations: multiplicative and additive factors
- Fast two-scale methods for eikonal equations
- Fast-phase space computation of multiple arrivals
- High order fast sweeping methods for static Hamilton-Jacobi equations
- Legendre-transform-based fast sweeping methods for static Hamilton-Jacobi equations on triangulated meshes
- Level set methods and dynamic implicit surfaces
- Matters computational. Ideas, algorithms, source code.
- Numerical Geometry of Non-Rigid Shapes
- O(\(N\)) implementation of the fast marching algorithm
- Optimal algorithm for shape from shading and path planning
- Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and Algorithms
- Ordered line integral methods for computing the quasi-potential
- Some improvements of the fast marching method
- The Discrete Geodesic Problem
- Viscosity Solutions of Hamilton-Jacobi Equations
Cited in
(9)- Numerical geometric acoustics: an eikonal-based approach for modeling sound propagation in 3D environments
- Neighbor-gradient single-pass method for solving anisotropic eikonal equation
- A fast iterative method for solving the eikonal equation on tetrahedral domains
- A Fast Iterative Method for Eikonal Equations
- Computing the quasipotential for nongradient SDEs in 3D
- A fast iterative method for solving the eikonal equation on triangulated surfaces
- Jet marching methods for solving the eikonal equation
- libeikonal
- Deep Eikonal solvers
Describes a project that uses
Uses Software
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)
