Many researchers have studied the apparent horizon finding problem, and there are a large number of different apparent horizon finding algorithms and codes. Almost all of these require (assume) that any apparent horizon to be found is a Strahlkörper (Section 2) about some local coordinate origin; both finite-difference and spectral parameterizations of the Strahlkörper are common.

For slices with continuous symmetries, special algorithms are sometimes used:

- Zero-Finding in Spherical Symmetry
- (Section 8.1)

In spherical symmetry the apparent horizon equation (16) becomes a 1-dimensional nonlinear algebraic equation, which can be solved by zero-finding. - The Shooting Algorithm in Axisymmetry
- (Section 8.2)

In axisymmetry the apparent horizon equation (16) becomes a nonlinear 2-point boundary value ODE, which can be solved by a shooting algorithm.

Alternatively, all the algorithms described below for generic slices are also applicable to axisymmetric slices and can take advantage of the axisymmetry to simplify the implementation and boost performance.

For fully generic slices, there are several broad categories of apparent horizon finding algorithms and codes:

- Minimization Algorithms
- (Section 8.3)

These algorithms define a scalar norm on over the space of possible trial surfaces. A general-purpose scalar-function-minimization routine is then used to search trial-surface-shape space for a minimum of this norm (which should give ). - Spectral Integral-Iteration Algorithms
- (Section 8.4)

These algorithms expand the (Strahlkörper) apparent horizon shape function in a spherical-harmonic basis, use the orthogonality of spherical harmonics to write the apparent horizon equation as a set of integral equations for the spectral coefficients, and solve these equations using a functional-iteration algorithm. - Elliptic-PDE Algorithms
- (Section 8.5)

These algorithms write the apparent horizon equation (16) as a nonlinear elliptic (boundary-value) PDE for the horizon shape and solve this PDE using (typically) standard elliptic-PDE numerical algorithms. - Horizon Pretracking
- (Section 8.6)

Horizon pretracking solves a slightly more general problem than apparent horizon finding: Roughly speaking, the determination of the smallest such that the equation has a solution, and the determination of that solution. By monitoring the time evolution of and of the surfaces satisfying this condition, we can determine – before it appears – approximately where (in space) and when (in time) a new MOTS will appear in a dynamic numerically-evolving spacetime. Horizon pretracking is implemented as a 1-dimensional (binary) search using a slightly-modified elliptic-PDE apparent horizon finding algorithm as a “subroutine”. - Flow Algorithms
- (Section 8.7)

These algorithms start with a large 2-surface (larger than any possible apparent horizon in the slice) and shrink it inwards using an algorithm which ensures that the surface will stop shrinking when it coincides with the apparent horizon.

I describe the major algorithms and codes in these categories in detail in the following.

8.1 Zero-finding in spherical symmetry

8.2 The shooting algorithm in axisymmetry

8.3 Minimization algorithms

8.3.1 Spurious local minima

8.3.2 Performance

8.3.3 Anticipating the formation of a common apparent horizon

8.3.4 Summary of minimization algorithms/codes

8.4 Spectral integral-iteration algorithms

8.4.1 Kemball and Bishop’s modifications of the Nakamura–Kojima–Oohara algorithm

8.4.2 Lin and Novak’s variant of the Nakamura–Kojima–Oohara algorithm

8.4.3 Summary of spectral integral-iteration algorithms

8.5 Elliptic-PDE algorithms

8.5.1 Angular coordinates, grid, and boundary conditions

8.5.2 Evaluating the expansion

8.5.3 Solving the nonlinear elliptic PDE

8.5.4 The Jacobian matrix

8.5.5 Solving the linear equations

8.5.6 Sample results

8.5.7 Summary of elliptic-PDE algorithms/codes

8.6 Horizon pretracking

8.6.1 Constant-expansion surfaces

8.6.2 Generalized constant-expansion surfaces

8.6.3 Goal functions

8.6.4 The pretracking search

8.6.5 Sample results

8.6.6 Summary of horizon pretracking

8.7 Flow algorithms

8.7.1 Implicit pseudo-time stepping

8.7.2 Varying the flow speed

8.7.3 Surface representation and the handling of bifurcations

8.7.4 Gundlach’s “fast flow”

8.7.5 Summary of flow algorithms/codes

8.2 The shooting algorithm in axisymmetry

8.3 Minimization algorithms

8.3.1 Spurious local minima

8.3.2 Performance

8.3.3 Anticipating the formation of a common apparent horizon

8.3.4 Summary of minimization algorithms/codes

8.4 Spectral integral-iteration algorithms

8.4.1 Kemball and Bishop’s modifications of the Nakamura–Kojima–Oohara algorithm

8.4.2 Lin and Novak’s variant of the Nakamura–Kojima–Oohara algorithm

8.4.3 Summary of spectral integral-iteration algorithms

8.5 Elliptic-PDE algorithms

8.5.1 Angular coordinates, grid, and boundary conditions

8.5.2 Evaluating the expansion

8.5.3 Solving the nonlinear elliptic PDE

8.5.4 The Jacobian matrix

8.5.5 Solving the linear equations

8.5.6 Sample results

8.5.7 Summary of elliptic-PDE algorithms/codes

8.6 Horizon pretracking

8.6.1 Constant-expansion surfaces

8.6.2 Generalized constant-expansion surfaces

8.6.3 Goal functions

8.6.4 The pretracking search

8.6.5 Sample results

8.6.6 Summary of horizon pretracking

8.7 Flow algorithms

8.7.1 Implicit pseudo-time stepping

8.7.2 Varying the flow speed

8.7.3 Surface representation and the handling of bifurcations

8.7.4 Gundlach’s “fast flow”

8.7.5 Summary of flow algorithms/codes

http://www.livingreviews.org/lrr-2007-3 |
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 Germany License. Problems/comments to |