4. 1. Performance
A key advantage of the heat method is that the linear systems
in steps I and III can be prefactored. Our implementation
uses sparse Cholesky factorization,
9 which for Poisson-type problems has guaranteed sub-quadratic complexity but in practice scales much better5; moreover there is
strong evidence to suggest that sparse systems arising from
elliptic PDEs can be solved in very close to linear time.
Independent of these issues, the amortized cost for problems with a large number of right-hand sides is roughly
linear, since back substitution can be applied in essentially
linear time. See inset for a breakdown of relative costs in our
Figure 13. Effect of Neumann (top-left), Dirichlet (top-right) and
averaged (bottom-left) boundary conditions on smoothed distance.
Averaged boundary conditions mimic the behavior of the same
surface without boundary.
Figure 14. For path planning, the behavior of geodesics can be
controlled via boundary conditions and the time step t. Top-left:
Neumann conditions encourage boundary adhesion. Top-right:
Dirichlet conditions encourage avoidance. Bottom-left: small values
of t yield standard straight-line geodesics. Bottom-right: large
values of t yield more natural trajectories.
Figure 15. Meshes used in Table 1. Left to right: Bunny, Isis, Horse, Bimba, Aphrodite, Lion, Ramses.
solution (see Renesse44 Corollary 2 and Norri,
1. 1, respectively). Boundary conditions do however
alter the behavior of our smoothed distance. Although there is
no well-defined “correct” behavior for this smoothed function, we advocate the use of boundary conditions obtained
by taking the mean of the Neumann solution uN and the
Dirichlet solution uD, that is, . The intuition
behind this behavior again stems from a random walker
interpretation: zero Dirichlet conditions absorb heat,
causing walkers to “fall off” the edge of the domain.
Neumann conditions prevent heat from flowing out of the
domain, effectively “reflecting” random walkers. Averaged
conditions mimic the behavior of a domain without
boundary: the number of walkers leaving equals the number of walkers returning. Figure 14 shows how boundary
conditions affect the behavior of geodesics in a path-plan-ning scenario.