7.7 Local versus global algorithms
Apparent horizon finding algorithms can usefully be divided into two broad classes:
- are those whose convergence is only guaranteed in some (functional)
neighborhood of a solution. These algorithms require a “good” initial guess in order to find the
apparent horizon. Most apparent horizon finding algorithms are local.
- are those which can (in theory, ignoring finite-step-size and other numerical
effects) converge to the apparent horizon independent of any initial guess. Flow algorithms
(Section 8.7) are the only truely global algorithms. Zero-finding in spherical symmetry
(Section 8.1) and shooting in axisymmetry (Section 8.2) are “almost global” algorithms:
They require only 1-dimensional searches, which (as discussed in Appendix A) can be
programmed to be very robust and efficient. In many cases horizon pretracking (Section 8.6)
can semi-automatically find an initial guess for a local algorithm, essentially making the local
algorithm behave like an “almost global” one.
One might wonder why local algorithms are ever used, given the apparently superior robustness
(guaranteed convergence independent of any initial guess) of global algorithms. There are two basic
- In practice, local algorithms are much faster than global ones, particularly when “tracking” the
time evolution of an existing apparent horizon.
- Due to finite-step-size and other numerical effects, in practice even “global” algorithms may
fail to converge to an apparent horizon. (That is, the algorithms may sometimes fail to find an
apparent horizon even when one exists in the slice.)