A narrow band method for non-causal discretizations of anisotropic eikonal equations, with adaptive width, sub-and super-solution construction, and quasi-linear complexity
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.
