The common [apparent] horizon […] appears instantaneously at some late time and without a previous good guess for its location. In practice, an estimate of the surface location and shape can be put in by hand. The quality of this guess will determine the rate of convergence of the finder and, more seriously, also determines whether a horizon is found at all. Gauge effects in the strong field region can induce distortions that have a large influence on the shape of the common horizon, making them difficult to predict, particularly after a long evolution using dynamical coordinate conditions. As such, it can be a matter of some expensive trial and error to find the common apparent horizon at the earliest possible time. Further, if a common apparent horizon is not found, it is not clear whether this is because there is none, or whether there exists one which has only been missed due to unsuitable initial guesses – for a fast apparent horizon finder, a good initial guess is crucial.
Pretracking tries (usually successfully) to eliminate these difficulties by determining – before it appears – approximately where (in space) and when (in time) the common apparent horizon will appear.
The basic idea of horizon pretracking is to consider surfaces of constant expansion (“CE surfaces”), i.e. smooth closed orientable 2surfaces in a slice satisfying the condition
where the expansion is a specified real number. Each marginally outer trapped surface (including the apparent horizon) is thus a CE surface with expansion ; more generally Equation(33) defines a 1parameter family of 2surfaces in the slice. As discussed by Schnetter et al. [133, 135], for asymptotically flat slices containing a compact strongfield region, some of the members of this family typically foliate the weakfield region.In the binarycoalescence context, for each slice we define to be the smallest for which a CE surface (containing both strongfield regions) exists with expansion . If this “minimumexpansion CE surface” is the common apparent horizon, while if this surface is an approximation to where the common apparent horizon will appear. We expect the minimumexpansion CE surface to change continuously during the evolution and its expansion to decrease towards . Essentially, horizon pretracking follows the time evolution of the minimumexpansion CE surface and uses it as an initial guess for (searching for) the common apparent horizon.
Schnetter [133] implemented an early form of horizon pretracking, which followed the evolution of the minimumexpansion constantexpansion surface, and found that it worked well for simple test problems. However, Schnetter et al. [135] found that for more realistic binaryblackhole coalescence systems the algorithm needs to be extended:
Schnetter et al. [135] discuss these problems in more detail, arguing that to solve them, the expansion should be generalized to a “shape function” given by one of
CE surfaces are then generalized to surfaces satisfying for some specified .Note that unlike , both and are typically monotonic with radius. Neither nor are 3covariantly defined, but they both still have the property that in Equation (35) implies the surface is a MOTS, and in practice they work better for horizon pretracking.
To define the single “smallest” surface at each time, Schnetter et al. [135] introduce a second generalization, that of a “goal function” , which maps surfaces to real numbers. The pretracking search then attempts, on each time slice, to find the surface (shape) satisfying with the minimum value of . They experimented with several different goal functions,
where in each case the overbar ( ) denotes an average over the surface^{51}.
Schnetter’s [133] original implementation of horizon pretracking (which followed the evolution of the minimumexpansion CE surface) used a binary search on the desired expansion . Because appears only on the right hand side of the generalized CE condition (35), it is trivial to modify any apparent horizon finder to search for a surface of specified expansion . (Schnetter used his TGRapparentHorizon2D ellipticPDE apparent horizon finder described in Section 8.5.7 for this.) A binary search on can then be used to find the minimum value .^{52}
Implementing a horizon pretracking search on any of the generalized goal functions (36) is conceptually similar but somewhat more involved: As described by Schnetter et al. [135] for the case of an ellipticPDE apparent horizon finder^{53}, we first write the equation defining a desired pretracking surface as
where is the desired value of the goal function . Since is the only term in Equation (37) which varies over the surface, it must be constant for the equation to be satisfied. In this case vanishes, so the equation just gives , as desired.Because depends on at all surface points, directly finite differencing Equation (37) would give a nonsparse Jacobian matrix, which would greatly slow the linearsolver phase of the ellipticPDE apparent horizon finder (Section 8.5.5). Schnetter et al. [135, Section III.B] show how this problem can be solved by introducing a single extra unknown into the discrete system. This gives a Jacobian which has a single nonsparse row and column, but is otherwise sparse, so the linear equations can still be solved efficiently.
When doing the pretracking search, the cost of a single binarysearch iteration is approximately the same as that of finding an apparent horizon. Schnetter et al. [135, Figure 5] report that their pretracking implementation (a modified version of Thornburg’s AHFinderDirect [156] ellipticPDE apparent horizon finder described in Section 8.5.7) typically takes on the order of 5 to 10 binarysearch iterations^{54}. The cost of pretracking is thus on the order of 5 to 10 times that of finding a single apparent horizon. This is substantial, but not prohibitive, particularly if the pretracking algorithm is not run at every time step.
As an example of the results obtained from horizon pretracking, Figure 13 shows the expansion for various pretracking surfaces (i.e. various choices for the shape function in a headon binary black hole collision). Notice how all three of the shape functions (34) result in pretracking surfaces whose expansions converge smoothly to zero just when the apparent horizon appears (at about ).

As a further example, Figure 14 shows the pretracking surfaces (more precisely, their cross sections projected into the black holes’ orbital plane) at various times in a spiraling binary black hole collision.

Pretracking is a very valuable addition to the horizon finding repertoire: It essentially gives a local algorithm (in this case, an ellipticPDE algorithm) most of the robustness of a global algorithm in terms of finding a common apparent horizon as soon as it appears. It is implemented as a higherlevel algorithm which uses a slightlymodified ellipticPDE apparent horizon finding algorithm as a “subroutine”.
The one significant disadvantage of pretracking is its cost: Each pretracking search typically takes 5 to 10 times as long as finding an apparent horizon. Further research to reduce the cost of pretracking would be useful.
Schnetter et al.’s pretracking implementation [135] is implemented as a set of modifications to Thornburg’s AHFinderDirect [156] apparent horizon finder. Like the original AHFinderDirect, the modified version is a freely available “thorn” in the Cactus toolkit (see Table 2).
http://www.livingreviews.org/lrr20073 
This work is licensed under a Creative Commons AttributionNoncommercialNo Derivative Works 2.0 Germany License. Problems/comments to 