Eikonal Equations: New Two-Scale Algorithms And Error Analysis

Other Titles
Hamilton-Jacobi equations arise in a number of seemingly disparate applications, from front propagation to photolithography to robotic navigation. Eikonal equations fall into an important subset representing isotropic optimal control and often are used as a first benchmark for numerical methods. Many of the interesting geometrical properties of Eikonal and related equations are exploited in two families of popular algorithms: the single-pass Fast Marching Methods and the iterative Fast Sweeping Methods. We start by developing a class of two-scale hybrid algorithms that combine the ideas of these prior methods on different scales. These hybrid methods are shown to have a clear advantage compared to other serial algorithms, but more importantly, one of them ("HCM") is very suitable for parallelization on a shared memory architecture. Our extensive numerical experiments benchmark this parallel HCM against current serial methods and another parallel state-of-the-art solver for the same computer architecture. We demonstrate the robustness of the parallel HCM on a wide range of problems, its good scaling in the number of processors, and its efficiency in solving a problem from exploratory geophysics. In the last part, we focus on estimating the error committed by fast approximate methods that introduce boundary data pollution. Examples include domain restriction methods for recovering only a single optimal path between a source/target pair and a domain decomposition method that creates subdomains whose boundaries are approximately characteristic. In simple cases we use a novel technique to estimate the sensitivity of a gridpoint to other gridpoints in its computational domain of dependence and use this to bound the error.
Journal / Series
Volume & Issue
Date Issued
eikonal; numerical; parallel; shortest path; causality
Effective Date
Expiration Date
Union Local
Number of Workers
Committee Chair
Vladimirsky, Alexander B.
Committee Co-Chair
Committee Member
Wahlbin, Lars Bertil
Bindel, David S.
Van Loan, Charles Francis
Degree Discipline
Applied Mathematics
Degree Name
Ph. D., Applied Mathematics
Degree Level
Doctor of Philosophy
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
Link(s) to Reference(s)
Previously Published As
Government Document
Other Identifiers
Rights URI
dissertation or thesis
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record