A second-order fast marching eikonal solver

Computational cost

The leading term in the computational cost of the fast marching algorithm comes from the first step: choosing the point on the wavefront with the smallest traveltime. Consequently, the cost should not depend strongly on the order of the finite-difference stencil, but rather the sort algorithm used. Heap sorting has a cost of $O(\log N)$, and so in principle, with this algorithm, the fast marching method has a cost of $O( N \log N)$.

The left panel of Figure 4 shows a plot of CPU time against $N$ for the same models as Figure 2. The time shown is elapsed (wall clock) time on a 300 MHz Pentium II. For the largest model computed here, the second-order code takes 11% longer to run than the first-order code, and this percentage decreases as $N$ increases.

Because $\log N$ grows slowly compared to $N$, the plot of CPU time against $N$ is dominated by the linear term. The right panel in Figure 4 addresses this issue by showing CPU time divided by $N$ versus $N$. On this graph, the $\log N$ behaviour is clearly visible.

times
Figure 4. Elapsed CPU time vs. the number of grid points, $N$, for first-order (solid line) and second order (dashed line) eikonal solvers. Left panel shows CPU time vs $N$. Right panel shows CPU time$/N$ vs $N$.

A second-order fast marching eikonal solver