Go to previous page Go up Go to next page

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
∫ ∥Θ ∥ ≡ Θ2 dΩ, (20 )
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 (5View Equation) for the horizon surface, we can view the norm (20View Equation) as being defined on the space of spectral coefficients {a ℓm }.

This norm clearly has a global minimum ∥Θ ∥ = 0 for each solution of the apparent horizon equation (16View Equation). 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 algorithm32.

Evaluating the norm (20View Equation) requires a numerical integration over the horizon surface: We choose some grid of Nang points on the surface, interpolate the slice geometry fields (gij, ∂kgij, and Kij) 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. [8Jump To The Next Citation Point] and Baumgarte et al. [26Jump To The Next Citation Point] 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 (20View Equation) clearly has a single global minimum ∥Θ ∥ = 0 for each MOTS Θ = 0, it typically also has a large number of other local minima with Θ ⁄= 0, which are “spurious” in the sense that they do not correspond (even approximately) to MOTSs33. Unfortunately, general-purpose “function-minimization” routines only locate local minima and, thus, may easily converge to one of the spurious Θ ⁄= 0 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 Θ = 0 rather than to one of the spurious Θ ⁄= 0 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, Θ = 0, or a spurious one, Θ ⁄= 0. Due to numerical errors in the geometry interpolation and the evaluation of the integral (20View Equation), ∥Θ ∥ 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. [8Jump To The Next Citation Point] and Baumgarte et al. [26Jump To The Next Citation Point] 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. [124Jump To The Next Citation Point121Jump To The Next Citation Point] report that in practice, spurious solutions can be avoided by a combination of two factors:

8.3.2 Performance

For convenience of exposition, suppose the spectral representation (5View Equation) of the horizon-shape function h uses spherical harmonics Yℓm. (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 ℓmax, the number of coefficients is then N = (ℓ +1 )2 coeff max. ℓ max 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 Ncoeff-dimensional space (here the space of surface-shape coefficients {aℓm}), a general-purpose function-minimization algorithm typically needs on the order of 5N 2coeff to 10N c2oeff iterations34. Thus the number of iterations grows as ℓ4max.

Each iteration requires an evaluation of the norm (20View Equation) for some trial set of surface-shape coefficients {a ℓm }, which requires 2 𝒪 (Ncoeff) = 𝒪 (ℓmax) work to compute the surface positions, together with 𝒪 (Nang) work to interpolate the geometry fields to the surface points and compute the numerical quadrature of the integral (20View Equation).

Thus the total work for a single horizon finding is 𝒪(ℓ6max + Nang ℓ4max). Fortunately, the accuracy with which the horizon is found generally improves rapidly with ℓ max, sometimes even exponentially35. Thus, relatively modest values of ℓmax (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 ℓmax and Nang). The one exception is in axisymmetry, where only spherical harmonics Yℓm with m=0 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 (20View Equation)). 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 ℓmax.

8.3.4 Summary of minimization algorithms/codes

Minimization algorithms are fairly easy to program and have been used by many researchers, for example [43691028Jump To The Next Citation Point264Jump To The Next Citation Point]. 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 [4Jump To The Next Citation Point] includes a minimization algorithm based on the work of Anninos et al. [8]36. It is implemented as a freely available module (“thorn”) in the External LinkCactus computational toolkit (see Table 2).


  Go to previous page Go up Go to next page