An adaptive domain-decomposition technique for parallelization of the fast marching method

The fast marching method (FMM) is an efficient technique to solve numerically the Eikonal equation. The parallelization of the FMM is not easy because of its intrinsic sequential nature. In this paper we propose a novel approach to parallelize the FMM. It leads to an equation-dependent domain decomposition and it turns out to be particularly suitable for machines with two or four cores that are in common use today. Compared to other techniques in the field, the proposed method is much simpler to implement and it gives a slightly better computational speed-up. In order to test the new method on a real-world application, we solve the shape-from-shading problem based on a Hamilton-Jacobi equation. On a standard four-core machine, the method confirms the good properties. It shows a reasonable speedup factor of about 2.5, and it reveals its potential to good performance if the arithmetic density of the problem is high. (C) 2011 Elsevier Inc. All rights reserved.