Back to search

Cornell University

Eikonal Equations: New Two-Scale Algorithms And Error Analysis

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Applied Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Applied Mathematics
Grantor
Cornell University
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chacon, Adam
Chair dc:contributor.chair
  • Vladimirsky, Alexander B.
Committee members dc:contributor.committeemember
  • Wahlbin, Lars Bertil
  • Bindel, David S.
  • Van Loan, Charles Francis

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
8442194

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chacon, Adam. Eikonal Equations: New Two-Scale Algorithms And Error Analysis. Doctor of Philosophy thesis, Cornell University, 2014. https://hdl.handle.net/1813/36002