![]() |
![]() |
![]() |
![]() | A second-order fast marching eikonal solver | ![]() |
![]() |
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 , and so in principle, with this
algorithm, the fast marching method has a cost of
.
The left panel of Figure 4 shows a plot of CPU time
against 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
increases.
Because grows slowly compared to
, the plot of CPU time
against
is dominated by the linear term. The right panel in
Figure 4 addresses this issue by showing CPU time
divided by
versus
. On this graph, the
behaviour is
clearly visible.
![]() |
---|
times
Figure 4. Elapsed CPU time vs. the number of grid points, ![]() ![]() ![]() ![]() |
![]() ![]() |
![]() |
![]() |
![]() |
![]() | A second-order fast marching eikonal solver | ![]() |
![]() |