← All papers
First page of A narrow band method for non-causal discretizations of anisotropic eikonal equations, with adaptive width, sub-and super-solution construction, and quasi-linear complexity

A narrow band method for non-causal discretizations of anisotropic eikonal equations, with adaptive width, sub-and super-solution construction, and quasi-linear complexity

Jean-Marie Mirebeau, Yanis Mouheb

math.NA Nov 13, 2026 · v1
All lemmas, propositions and theorems on the narrow band method were formalized in Lean with Claude AI assistance, marked Lean✓ throughout.
We describe a narrow band method for numerically solving anisotropic eikonal equations, and more generally static first order Hamilton-Jacobi equations with possibly non-convex Hamiltonians, discretized using standard schemes (semi-Lagrangian, upwind-differences, Lax-Friedrichs). The causality property is not needed, in contrast with the fast marching method. The proposed approach simultaneously builds a numerical sub-solution u and super-solution u to the problem, and adapts the width of the narrow band based on their comparison. We prove that (1 + $ε$)u $\ge$ u at termination, where $ε$ > 0 is any given tolerance parameter, and that the worst case complexity is O(N | ln $ε$| ln(N/$ε$)), where N denotes the number of discretization points, and the underlying constant is explicit in terms of those associated with the scheme properties. Numerical experiments illustrate our results.

Anisotropic eikonal and static first-order Hamilton-Jacobi equations, possibly with non-convex Hamiltonians, are often discretized with non-causal schemes. Fast marching methods do not apply to such schemes, so an efficient solver with guaranteed accuracy is needed.

A narrow band method simultaneously builds a numerical sub-solution and super-solution and adapts the band width by comparing them. Scheme properties are stated as abstract operator axioms (monotonicity, additive invariance, comparison, sub-additivity). All mathematical results were formalized in Lean using Claude AI together with Scott Armstrong's Lean skills, and the formal statements were reviewed as they were produced.

At termination the method guarantees (1+ε) times the sub-solution bounds the super-solution, with worst-case complexity O(N |ln ε| ln(N/ε)) and an explicit constant. The Lean formalization of all lemmas, propositions and theorems took about three days, and numerical experiments illustrate the results.