This algorithm begins by choosing the usual polar-spherical topology for the angular coordinates , and rewriting the apparent horizon equation (16) in the form

where is the flat-space angular Laplacian operator, and is a complicated nonlinear algebraic function of the arguments shown, which remains regular even at and .Next we expand in spherical harmonics (5). Because the left hand side of Equation (21) is just the flat-space angular Laplacian of , which has the as orthogonal eigenfunctions, multiplying both sides of Equation (21) by (the complex conjugate of ) and integrating over all solid angles gives

for each and except .Based on this, Nakamura, Kojima, and Oohara [113] proposed the following functional-iteration algorithm for solving Equation (21):

- Start with some (initial-guess) set of horizon-shape coefficients . These determine a surface shape via Equation (5).
- Interpolate the geometry variables to this surface shape (see Section 7.5).
- For each and except , evaluate the integral (22) by numerical quadrature to obtain a next-iteration coefficient .
- Determine a next-iteration coefficient by numerically solving (finding a root of) the equation This can be done using any of the 1-dimensional zero-finding algorithms discussed in Appendix A.
- Iterate until all the coefficients converge.

Gundlach [80] observed that the subtraction and inversion of the flat-space angular Laplacian operator in this algorithm is actually a standard technique for solving nonlinear elliptic PDEs by spectral methods. I discuss this observation and its implications further in Section 8.7.4.

Nakamura, Kojima, and Oohara [113] report that their algorithm works well, but Nakao (cited as personal communication in [146]) has argued that it tends to become inefficient (and possibly inaccurate) for large (high angular resolution) because the fail to be numerically orthogonal due to the finite resolution of the numerical grid. I know of no other published work addressing Nakao’s criticism.

Kemball and Bishop [93] investigated the behavior of the Nakamura–Kojima–Oohara algorithm and found that its (only) major weakness seems to be that the -update equation (23) “may have multiple roots or minima even in the presence of a single marginally outer trapped surface, and all should be tried for convergence”.

Kemball and Bishop [93] suggested and tested several modifications to improve the algorithm’s convergence behavior. They verified that (either in its original form or with their modifications) the algorithm’s rate of convergence (number of iterations to reach a given error level) is roughly independent of the degree of spherical-harmonic expansion used. They also give an analysis that the algorithm’s cost is , and its accuracy , i.e. the cost is . This accuracy is surprisingly low: Exponential convergence with is typical of spectral algorithms and would be expected here. I do not know of any published work which addresses this discrepancy.

Lin and Novak [104] have developed a variant of the Nakamura–Kojima–Oohara algorithm which avoids the need for a separate search for at each iteration: Write the apparent horizon equation (16) in the form

where is again the flat-space angular Laplacian operator and where is a nonzero scalar function on the horizon surface. Then choose as where is the flat metric of polar spherical coordinates, is the associated 3-covariant derivative operator, and is the level set function (7).Lin and Novak [104] showed that all the spherical-harmonic coefficients (including ) can then be found by iteratively solving the equation

Lin and Novak [104] find that this algorithm gives robust convergence and is quite fast, particularly at
modest accuracy levels. For example, running on a 2 GHz processor, their implementation takes ,
, , , and seconds to find the apparent horizon in a test slice to a relative error
(measured in the horizon area) of , , , , and
respectively^{37}.
This implementation is freely available as part of the Lorene toolkit for spectral computations in
numerical relativity (see Table 2).

Despite what appears to be fairly good numerical behavior and reasonable ease of implementation, the original Nakamura–Kojima–Oohara algorithm has not been widely used apart from later work by its original developers (see, for example, [115, 114]). Kemball and Bishop [93] have proposed and tested several modifications to the basic Nakamura–Kojima–Oohara algorithm. Lin and Novak [104] have develped a variant of the Nakamura–Kojima–Oohara algorithm which avoids the need for a separate search for the coefficient at each iteration. Their implementation of this variant is freely available as part of the Lorene toolkit for spectral computations in numerical relativity (see Table 2).

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 |