{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/36002"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/36002","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Eikonal Equations: New Two-Scale Algorithms And Error Analysis","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.","abstract_html":"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 (&quot;HCM&quot;) 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.","abstract_has_math":false,"creators":["Chacon, Adam"],"institution":"Cornell University","degree_name":"Ph. D., Applied Mathematics","degree_level":"Doctor of Philosophy","degree_discipline":"Applied Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Vladimirsky, Alexander B."],"committee_members":["Wahlbin, Lars Bertil","Bindel, David S.","Van Loan, Charles Francis"],"year":2014,"date_issued":"2014-01-27","date_published":"2014-01-27","updated_at":"2026-11-19T03:17:47Z","subjects":["eikonal","numerical","parallel","shortest path","causality"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["8442194"],"render_values":[{"text":"8442194","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/36002","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/36002","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F36002","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Vladimirsky, Alexander B."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Wahlbin, Lars Bertil","Bindel, David S.","Van Loan, Charles Francis"]},{"key":"dc:creator","label":"Author","values":["Chacon, Adam"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-02-25T18:36:29Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-02-25T18:36:29Z"]},{"key":"dc:date.issued","label":"Date","values":["2014-01-27"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Applied Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Applied Mathematics"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["eikonal","numerical","parallel","shortest path","causality"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["8442194"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/36002"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"5ccd17a0-3ec0-4089-8700-f091fbbdcc65\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Eikonal Equations: New Two-Scale Algorithms And Error Analysis</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2014-01-27</PublicationDate> <Authors> <Author> <DisplayName>Chacon, Adam</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>eikonal</Keyword> <Keyword>numerical</Keyword> <Keyword>parallel</Keyword> <Keyword>shortest path</Keyword> <Keyword>causality</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Chacon, Adam"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Eikonal Equations: New Two-Scale Algorithms And Error Analysis"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"5ccd17a0-3ec0-4089-8700-f091fbbdcc65\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Eikonal Equations: New Two-Scale Algorithms And Error Analysis</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2014-01-27</PublicationDate> <Authors> <Author> <DisplayName>Chacon, Adam</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>eikonal</Keyword> <Keyword>numerical</Keyword> <Keyword>parallel</Keyword> <Keyword>shortest path</Keyword> <Keyword>causality</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Chacon, Adam"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Vladimirsky, Alexander B."],"dc:contributor.committeemember":["Wahlbin, Lars Bertil","Bindel, David S.","Van Loan, Charles Francis"],"dc:creator":["Chacon, Adam"],"dc:date.accessioned":["2014-02-25T18:36:29Z"],"dc:date.available":["2014-02-25T18:36:29Z"],"dc:date.issued":["2014-01-27"],"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."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["8442194"],"dc:identifier.uri":["https://hdl.handle.net/1813/36002"],"dc:language.iso":["en_US"],"dc:subject":["eikonal","numerical","parallel","shortest path","causality"],"dc:title":["Eikonal Equations: New Two-Scale Algorithms And Error Analysis"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"],"thesis:degree_discipline":["Applied Mathematics"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Applied Mathematics"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:17:47Z"}