A parallel Heap-Cell Method for Eikonal equations by Adam Chacon and Alex Vladimirsky.

A shorter version of this manuscript was published in SIAM J. on Scientific Computing
under the name "A parallel two-scale method for Eikonal equations".

Abstract

Numerous applications of Eikonal equations prompted the development of many efficient numerical algorithms. The Heap-Cell Method (HCM) is a recent serial two-scale technique that has been shown to have advantages over other serial state-of-the-art solvers for a wide range of problems [Chacon & Vladimirsky, 2012]. This paper presents a parallelization of HCM for a shared memory architecture. The numerical experiments in R^3 show that the parallel HCM exhibits good algorithmic behavior and scales well, resulting in a very fast and practical solver. We further explore the influence on performance and scaling of data precision, early termination criteria, and the hardware architecture.

Paper

Source Code

We release the implementation code of our algorithms under GNU GPL license. You can download it from here. Please refer to the readme.pdf in the source code distribution for instructions on compiling the code and setting up the tested PDE examples.

Acknowledgements