A fast-marching algorithm for nonmonotonically evolving fronts

DOI10.1137/15M1017302MaRDI QIDQ3186112zbMATH OpenOpenAlexFDO

Authors Alexandra Tcheng, Jean-Christophe Nave

Publication date 8 August 2016

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

fast-marching methodfinite-difference schemesfront propagationHamilton-Jacobi equationslevel-set methodviscosity solutions

Mathematics Subject Classification ID

Finite difference methods for boundary value problems involving PDEs (65N06) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22)

Abstract: The non-monotonic propagation of fronts is considered. When the speed function $F:mathbb{R}^{n}imes[0,T]ightarrowmathbbR$ is prescribed, the non-linear advection equation $ph{i}_t+F|ablaphi|=0$ is a Hamilton-Jacobi equation known as the level-set equation. It is argued that a small enough neighbourhood of the zero-level-set $mathcalM$ of the solution $phi:mathbb{R}^{n}imes[0,T]ightarrowmathbbR$ is the graph of $psi:mathbb{R}^{n}ightarrowmathbbR$ where $psi$ solves a Dirichlet problem of the form $H(vecu,psi(vecu),ablapsi(vecu))=0$. A fast-marching algorithm is presented where each point is computed using a discretization of such a Dirichlet problem, with no restrictions on the sign of $F$. The output is a directed graph whose vertices evenly sample $mathcalM$. The convergence, consistency and stability of the scheme are addressed. Bounds on the computational complexity are estimated, and experimentally shown to be on par with the Fast Marching Method. Examples are presented where the algorithm is shown to be globally first-order accurate. The complexities and accuracies observed are independent of the monotonicity of the evolution.

Recommendations

• A low complexity algorithm for non-monotonically evolving fronts
• Convergence of a generalized fast-marching method for an eikonal equation with a velocity-changing sign
• A fast marching method for Hamilton-Jacobi equations modeling monotone front propagations
• Some improvements of the fast marching method
• An O(N) level set method for eikonal equations

Cites work

• A fast marching level set method for monotonically advancing fronts.
• A Fast Method for Approximating Invariant Manifolds
• A Level Set Formulation for the Solution of the Dirichlet Problem for Hamilton–Jacobi Equations
• A low complexity algorithm for non-monotonically evolving fronts
• A note on two problems in connexion with graphs
• A simple package for front tracking
• Analysis of high order fast interface tracking methods
• Convergence of a generalized fast-marching method for an eikonal equation with a velocity-changing sign
• Convergent Difference Schemes for Degenerate Elliptic and Parabolic Equations: Hamilton--Jacobi Equations and Free Boundary Problems
• Convergent filtered schemes for the Monge-Ampère partial differential equation
• Efficient algorithms for globally optimal trajectories
• Fast Marching Methods
• Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
• Filtered schemes for Hamilton-Jacobi equations: a simple construction of convergent accurate difference schemes
• Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations
• scientific article; zbMATH DE number 4205918 (Why is no real title available?)
• scientific article; zbMATH DE number 3914081 (Why is no real title available?)
• scientific article; zbMATH DE number 3783507 (Why is no real title available?)
• scientific article; zbMATH DE number 1349965 (Why is no real title available?)
• scientific article; zbMATH DE number 653075 (Why is no real title available?)
• scientific article; zbMATH DE number 4003463 (Why is no real title available?)
• scientific article; zbMATH DE number 5681750 (Why is no real title available?)
• Level set methods and dynamic implicit surfaces
• Numerical recipes. The art of scientific computing.
• Ordered upwind methods for static Hamilton–Jacobi equations
• Redistancing by flow of time dependent eikonal equation
• Robust Computational Algorithms for Dynamic Interface Tracking in Three Dimensions
• Some Properties of Viscosity Solutions of Hamilton-Jacobi Equations
• Static PDEs for time-dependent control problems
• Three-Dimensional Front Tracking
• User’s guide to viscosity solutions of second order partial differential equations
• Viscosity Solutions of Hamilton-Jacobi Equations

Cited in

(3)

• A low complexity algorithm for non-monotonically evolving fronts
• Generalized fronts propagation on weighted graphs
• A non-monotone fast marching scheme for Hamilton-Jacobi equation modelling dislocation dynamics

Describes a project that uses

Uses Software

• FronTier

This page was built for publication: A fast-marching algorithm for nonmonotonically evolving fronts

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