The von Neumann stability analysis of the interior algorithm linearizes the equations, while assuming a uniform infinite grid, and checks that the discrete Fourier modes do not grow exponentially. There is an additional stability condition that a boundary introduces into this analysis. Consider the one-dimensional case. The mode , with real, is not included in the von Neumann analysis for periodic boundary conditions. However, for the half plane problem with a boundary to the right on the -axis, one can legitimately prescribe such a mode as initial data as long as so that it has finite energy. Thus the stability of such boundary modes must be checked. In the case of an additional boundary to the left, the Godunov-Ryaben’kii theory gives as necessary conditions for stability the separate von Neumann stability of the interior and the stability of the allowed boundary modes [195]. The Kreiss condition [115] strengthens this result by providing a sufficient condition for stability.

The correct physical formulation of any asymptotically flat Cauchy problem also involves asymptotic conditions at infinity. These conditions must ensure not only that the total energy and the energy loss by radiation are both finite, but they must also ensure the proper asymptotic falloff of the radiation fields. However, when treating radiative systems computationally, an outer boundary is often established artificially at some large but finite distance in the wave zone, i.e. many wavelengths from the source. Imposing an appropriate radiation boundary condition at a finite distance is a difficult task even in the case of a simple radiative system evolving on a fixed geometric background. The problem is exacerbated when dealing with Einstein’s equation.

Nowhere is the boundary problem more acute than in the computation of gravitational radiation produced by black holes. The numerical study of a black hole spacetime by means of a pure Cauchy evolution involves inner as well as outer grid boundaries. The inner boundary is necessary to avoid the topological complications and singularities introduced by the black holes. For multiple black holes, the inner boundary consists of disjoint pieces. Unruh suggested the commonly accepted strategy for Cauchy evolution of black holes (see [213]). An inner boundary located at (or near) an apparent horizon is used to excise the singular interior region.

CCM has a natural application to this problem. In the Cauchy treatment of such a system, the outer grid boundary is located at some finite distance, normally many wavelengths from the source. Attempts to use compactified Cauchy hypersurfaces which extend to spatial infinity have failed because the phase of short wavelength radiation varies rapidly in spatial directions [138]. Characteristic evolution avoids this problem by approaching infinity along the phase fronts.

When the system is nonlinear and not amenable to an exact solution, a finite outer boundary condition must necessarily introduce spurious physical effects into a Cauchy evolution. The domain of dependence of the initial Cauchy data in the region spanned by the computational grid would shrink in time along ingoing characteristics unless data on a worldtube traced out by the outer grid boundary is included as part of the problem. In order to maintain a causally sensible evolution, this worldtube data must correctly substitute for the missing Cauchy data which would have been supplied if the Cauchy hypersurface had extended to infinity. In a scattering problem, this missing exterior Cauchy data might, for instance, correspond to an incoming pulse initially outside the outer boundary. In a problem where the initial radiation fields are confined to a compact region inside the boundary, these missing Cauchy data are easy to characterize when dealing with a constraint free field, such as a scalar field where the appropriate Cauchy data outside the boundary would be . However, the determination of Cauchy data for general relativity is a global elliptic constraint problem so that there is no well defined scheme to confine it to a compact region. Furthermore, even if the data for a given problem were known on a complete initial hypersurface extending to infinity, it would be a formidable nonlinear evolution problem to correctly assign the associated boundary data on a finite outer boundary.

Another important issue arising in general relativity is whether the boundary condition preserves the constraints. It is typical of hyperbolic reductions of the Einstein equations that the Hamiltonian and momentum constraints propagate in a domain of dependence dictated by the light rays. Unless the boundary conditions on the outer world tube enforce these constraints, they will be violated outside the domain of dependence of the initial Cauchy hypersurface. This issue of a constraint-preserving initial boundary value problem has only recently been addressed [204]. The first fully nonlinear treatment of a well-posed constraint preserving formulation of the Einstein initial-boundary value problem (IBVP) has only recently been given by Friedrich and Nagy [86]. Their treatment is based upon a frame formulation in which the evolution variables are the tetrad, connection coefficients, and Weyl curvature. Although this system has not yet been implemented computationally, it has spurred the investigation of simpler treatments of Einstein equations which give rise to a constraint preserving IBVP under various restrictions [55, 208, 54, 88, 112].

It is common practice in computational physics to impose some artificial boundary condition (ABC), such as an outgoing radiation condition, in an attempt to approximate the proper data for the exterior region. This ABC may cause partial reflection of an outgoing wave back into the system [146, 138, 121, 178], which contaminates the accuracy of the interior evolution and the calculation of the radiated waveform. Furthermore, nonlinear waves intrinsically backscatter, which makes it incorrect to try to entirely eliminate incoming radiation from the outer region. The resulting error is of an analytic origin, essentially independent of computational discretization. In general, a systematic reduction of this error can only be achieved by moving the computational boundary to larger and larger radii. This is computationally very expensive, especially for three-dimensional simulations.

A traditional ABC for the wave equation is the Sommerfeld condition. For a 3D scalar field this takes the form , where . This condition is exact only for a linear wave with spherically symmetric data and boundary. In that case, the exact solution is and the Sommerfeld condition eliminates the incoming wave .

Much work has been done on formulating boundary conditions, both exact and approximate, for linear problems in situations that are not spherically symmetric and in which the Sommerfeld condition would be inaccurate. These boundary conditions are given various names in the literature, e.g., absorbing or non-reflecting. A variety of ABC’s have been reported for linear problems. See the articles [93, 178, 216, 182, 37] for general discussions.

Local ABC’s have been extensively applied to linear problems with varying success [146, 78, 28, 215, 121, 44, 139]. Some of these conditions are local approximations to exact integral representations of the solution in the exterior of the computational domain [78], while others are based on approximating the dispersion relation of the so-called one-way wave equations [146, 215]. Higdon [121] showed that this last approach is essentially equivalent to specifying a finite number of angles of incidence for which the ABC’s yield perfect transmission. Local ABC’s have also been derived for the linear wave equation by considering the asymptotic behavior of outgoing solutions [28], which generalizes the Sommerfeld outgoing radiation condition. Although this type of ABC is relatively simple to implement and has a low computational cost, the final accuracy is often limited because the assumptions made about the behavior of the waves are rarely met in practice [93, 216].

The disadvantages of local ABC’s have led some workers to consider exact nonlocal boundary conditions based on integral representations of the infinite domain problem [214, 93, 216]. Even for problems where the Green’s function is known and easily computed, such approaches were initially dismissed as impractical [78]; however, the rapid increase in computer power has made it possible to implement exact nonlocal ABC’s for the linear wave equation and Maxwell’s equations in 3D [70, 110]. If properly implemented, this kind of method can yield numerical solutions which converge to the exact infinite domain problem in the continuum limit, while keeping the artificial boundary at a fixed distance. However, due to nonlocality, the computational cost per time step usually grows at a higher power with grid size ( per time step in three dimensions) than in a local approach [93, 70, 216].

The extension of ABC’s to nonlinear problems is much more difficult. The problem is normally treated by linearizing the region between the outer boundary and infinity, using either local or nonlocal linear ABC’s [216, 182]. The neglect of the nonlinear terms in this region introduces an unavoidable error at the analytic level. But even larger errors are typically introduced in prescribing the outer boundary data. This is a subtle global problem because the correct boundary data must correspond to the continuity of fields and their normal derivatives when extended across the boundary into the linearized exterior. This is a clear requirement for any consistent boundary algorithm, since discontinuities in the field or its derivatives would otherwise act as spurious sheet source on the boundary, which contaminates both the interior and the exterior evolutions. But the fields and their normal derivatives constitute an overdetermined set of data for the boundary problem. So it is necessary to solve a global linearized problem, not just an exterior one, in order to find the proper data. The designation “exact ABC” is given to an ABC for a nonlinear system whose only error is due to linearization of the exterior. An exact ABC requires the use of global techniques, such as the difference potential method, to eliminate back reflection at the boundary [216].

To date there have been only a few applications of ABC’s to strongly nonlinear problems [93]. Thompson [212] generalized a previous nonlinear ABC of Hedstrom [120] to treat 1D and 2D problems in gas dynamics. These boundary conditions performed poorly in some situations because of their difficulty in adequately modeling the field outside the computational domain [212, 93]. Hagstrom and Hariharan [116] have overcome these difficulties in 1D gas dynamics by a clever use of Riemann invariants. They proposed a heuristic generalization of their local ABC to 3D, but this approach has not yet been validated.

In order to reduce the level of approximation at the analytic level, an artificial boundary for a nonlinear problem must be placed sufficiently far from the strong-field region. This sharply increases the computational cost in multi-dimensional simulations [78]. There seems to be no numerical method which converges (as the discretization is refined) to the infinite domain exact solution of a strongly nonlinear wave problem in multi-dimensions, while keeping the artificial boundary fixed.

CCM is a strategy that eliminates this nonlinear source of error. In the simplest version of CCM, Cauchy and characteristic evolution algorithms are pasted together in the neighborhood of a worldtube to form a global evolution algorithm. The characteristic algorithm provides an outer boundary condition for the interior Cauchy evolution, while the Cauchy algorithm supplies an inner boundary condition for the characteristic evolution. The matching worldtube provides the geometric framework necessary to relate the two evolutions. The Cauchy foliation slices the worldtube into spherical cross-sections. The characteristic evolution is based upon the outgoing null hypersurfaces emanating from these slices, with the evolution proceeding from one hypersurface to the next by the outward radial march described earlier. There is no need to truncate spacetime at a finite distance from the sources, since compactification of the radial null coordinate used in the characteristic evolution makes it possible to cover the infinite space with a finite computational grid. In this way, the true waveform may be directly computed by a finite difference algorithm. Although characteristic evolution has limitations in the interior region where caustics develop, it proves to be both accurate and computationally efficient in the treatment of exterior regions.

http://www.livingreviews.org/lrr-2005-10 |
© Max Planck Society and the author(s)
Problems/comments to |