This algorithm begins by choosing the usual polar-spherical topology for the angular coordinates , and rewriting the apparent horizon equation (16) in the form
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
Based on this, Nakamura, Kojima, and Oohara  proposed the following functional-iteration algorithm for solving Equation (21):
Gundlach  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  report that their algorithm works well, but Nakao (cited as personal communication in ) 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  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  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  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
Lin and Novak  showed that all the spherical-harmonic coefficients (including ) can then be found by iteratively solving the equation
Lin and Novak  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 respectively37. 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  have proposed and tested several modifications to the basic Nakamura–Kojima–Oohara algorithm. Lin and Novak  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).
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 Germany License.