A Massively Parallel Multilevel Framework for Eikonal Solvers

Jeffrey Donatelli, University of California, Berkeley

The Eikonal equation is a static Hamilton-Jacobi partial differential equation that describes high-frequency wave propagation. Solutions of this equation have applications in several fields, including fluid dynamics, chemistry, computation geometry, image processing, and robotic navigation. Numerical solutions to the Eikonal equation typically require one to maintain a notion of causality in the evaluation orderings, which has served as an obstacle to parallelization. We discuss a novel approach which relaxes the causality constraint while still maintaining the correct solution. Furthermore, this is done in a multilevel framework where a series of coarser problems is first solved to predict the general flow of information which allows for highly efficient load balancing.

Abstract Author(s): Jeffrey J. Donatelli