Eikonal Equations: New Two-Scale Algorithms And Error Analysis
Files
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
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
Description
Sponsorship
Date Issued
Publisher
Keywords
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Bindel, David S.
Van Loan, Charles Francis