### 8.4 Spectral integral-iteration algorithms

Nakamura, Kojima, and Oohara [113] developed a functional-iteration spectral algorithm for solving the apparent horizon equation (16).

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):

1. Start with some (initial-guess) set of horizon-shape coefficients . These determine a surface shape via Equation (5).
2. Interpolate the geometry variables to this surface shape (see Section 7.5).
3. For each and except , evaluate the integral (22) by numerical quadrature to obtain a next-iteration coefficient .
4. 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.
5. 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.

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

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.

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

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. This implementation is freely available as part of the Lorene toolkit for spectral computations in numerical relativity (see Table 2).

#### 8.4.3 Summary of spectral integral-iteration algorithms

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, [115114]). 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).