### 8.3 Minimization algorithms

This family of algorithms defines a scalar norm on the expansion over the space of possible trial surfaces, typically the mean-squared norm
where the integral is over all solid angles on a trial surface.

Assuming the horizon surface to be a Strahlkörper and adopting the spectral representation (5) for the horizon surface, we can view the norm (20) as being defined on the space of spectral coefficients .

This norm clearly has a global minimum for each solution of the apparent horizon equation (16). To find the apparent horizon we numerically search the spectral-coefficient space for this (a) minimum, using a general-purpose “function-minimization” algorithm (code) such as Powell’s algorithm.

Evaluating the norm (20) requires a numerical integration over the horizon surface: We choose some grid of points on the surface, interpolate the slice geometry fields (, , and ) to this grid (see Section 7.5), and use numerical quadrature to approximate the integral. In practice this must be done for many different trial surface shapes (see Section 8.3.2), so it is important that it be as efficient as possible. Anninos et al. [8] and Baumgarte et al. [26] discuss various ways to optimize and/or parallelize this calculation.

Unfortunately, minimization algorithms have two serious disadvantages for apparent horizon finding: They can be susceptible to spurious local minima, and they’re very slow at high angular resolutions. However, for the (fairly common) case where we want to find a common apparent horizon as soon as it appears in a binary black-hole (or neutron-star) simulation, minimization algorithms do have a useful ability to “anticipate” the formation of the common apparent horizon, in a manner similar to the pretracking algorithms discussed in Section 8.6. I discuss the properties of minimization algorithms further in the following.

#### 8.3.1 Spurious local minima

While the norm (20) clearly has a single global minimum for each MOTS , it typically also has a large number of other local minima with , which are “spurious” in the sense that they do not correspond (even approximately) to MOTSs. Unfortunately, general-purpose “function-minimization” routines only locate local minima and, thus, may easily converge to one of the spurious minima.

What this problem means in practice is that a minimization algorithm needs quite a good (accurate) initial guess for the horizon shape in order to ensure that the algorithm converges to the true global minimum rather than to one of the spurious local minima.

To view this problem from a different perspective, once the function-minimization algorithm does converge, we must somehow determine whether the “solution” found is the true one, , or a spurious one, . Due to numerical errors in the geometry interpolation and the evaluation of the integral (20), will almost never evaluate to exactly zero; rather, we must set a tolerance level for how large may be. Unfortunately, in practice it is hard to choose this tolerance: If it is too small, the genuine solution may be falsely rejected, while if it is too large, we may accept a spurious solution (which may be very different from any of the true solutions).

Anninos et al. [8] and Baumgarte et al. [26] suggest screening out spurious solutions by repeating the algorithm with varying resolutions of the horizon-surface grid and checking that shows the proper convergence towards zero. This seems like a good strategy, but it is tricky to automate and, again, it may be difficult to choose the necessary error tolerances in advance.

When the underlying simulation is a spectral one, Pfeiffer et al. [124121] report that in practice, spurious solutions can be avoided by a combination of two factors:

• The underlying spectral solution can inherently be “interpolated” (evaluated at arbitrary positions) to very high accuracy.
• Pfeiffer et al. use a large number of quadrature points (typically an order of magnitude larger than the number of coefficients in the expansion (5)) in numerically evaluating the integral (20).

#### 8.3.2 Performance

For convenience of exposition, suppose the spectral representation (5) of the horizon-shape function uses spherical harmonics . (Symmetric trace-free tensors or other basis sets do not change the argument in any important way.) If we keep harmonics up to some maximum degree , the number of coefficients is then . is set by the desired accuracy (angular resolution) of the algorithm and is typically on the order of 6 to 12.

To find a minimum in an -dimensional space (here the space of surface-shape coefficients ), a general-purpose function-minimization algorithm typically needs on the order of to iterations. Thus the number of iterations grows as .

Each iteration requires an evaluation of the norm (20) for some trial set of surface-shape coefficients , which requires work to compute the surface positions, together with work to interpolate the geometry fields to the surface points and compute the numerical quadrature of the integral (20).

Thus the total work for a single horizon finding is . Fortunately, the accuracy with which the horizon is found generally improves rapidly with , sometimes even exponentially. Thus, relatively modest values of (typically in the range 8 – 12) generally suffice for adequate accuracy. Even so, minimization horizon finders tend to be slower than other methods, particularly if high accuracy is required (large and ). The one exception is in axisymmetry, where only spherical harmonics with need be considered. In this case minimization algorithms are much faster, though probably still slower than shooting or elliptic-PDE algorithms.

#### 8.3.3 Anticipating the formation of a common apparent horizon

Consider the case where we want to find a common apparent horizon as soon as it appears in a binary black-hole (or neutron-star) simulation. In Section 8.6 I discuss “horizon pretracking” algorithms which can determine – before it appears – approximately where (in space) and when (in time) the common apparent horizon will appear.

Minimization algorithms can provide a similar functionality: Before the common apparent horizon forms, trying to find it via a minimization algorithm will (hopefully) find the (a) surface which minimizes the error norm (defined by Equation (20)). This surface can be viewed as the current slice’s closest approximation to a common apparent horizon, and as the evolution proceeds, it should converge to the actual common apparent horizon.

However, it is not clear whether minimization algorithms used in this way suffer from the problems discussed in Section 8.6.2. In particular, it is not clear whether, in a realistic binary-coalescence simulation, the minimum- surfaces would remain smooth enough to be represented accurately with a reasonable .

#### 8.3.4 Summary of minimization algorithms/codes

Minimization algorithms are fairly easy to program and have been used by many researchers, for example [43691028264]. However, at least when the underlying simulation uses finite differencing, minimization algorithms are susceptible to spurious local minima, have relatively poor accuracy, and tend to be quite slow. I believe that the other algorithms discussed in the following sections are generally preferable. If the underlying simulation uses spectral methods, then minimization algorithms may be (relatively) somewhat more efficient and robust.

Alcubierre’s apparent horizon finder AHFinder [4] includes a minimization algorithm based on the work of Anninos et al. [8]. It is implemented as a freely available module (“thorn”) in the Cactus computational toolkit (see Table 2).