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. Normally the mode
, with
*k*
real, is not included in the von Neumann analysis. However, if
there is a boundary to the right on the
*x*
-axis, one can legitimately prescribe such a mode (with
*k*
>0) as initial data, so that its stability must be checked. In
the case of an additional boundary to the left, the
Ryaben'kii-Godunov theory allows separate investigation of the
interior stability and the stability of each individual
boundary [128].

The correct physical formulation of any asymptotically flat,
radiative Cauchy problem also requires boundary conditions at
infinity. These conditions must ensure not only that the total
energy and the energy loss by radiation are both finite, but must
also ensure the proper 1/
*r*
asymptotic falloff of the radiation fields. However, when
treating radiative systems computationally, an outer boundary
must be established artificially at some large but finite
distance in the wave zone, i.e. many wavelengths from the source.
Imposing an accurate 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 a black hole. For multiple black holes, the inner boundary consists of disjoint pieces. W. Unruh (see [145]) initially suggested the commonly accepted strategy for Cauchy evolution of black holes. An inner boundary located at (or near) an apparent horizon is used to excise the singular interior region. Later (see Sec. 4.8) I discuss a variation of this strategy based upon matching to a characteristic evolution in the inner region.

First, consider the outer boundary problem, in which Cauchy-characteristic matching has a natural application. 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 [93]. Characteristic evolution avoids this problem by approaching infinity along 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, this missing Cauchy data are easy to state when dealing with a constraint free field, such as a scalar field where the 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 were known on a complete initial hypersurface extending to infinity, it would be a formidable nonlinear problem to correctly pose the associated data on the outer boundary. The only formulation of Einstein's equations whose Cauchy initial-boundary value problem has been shown to have a unique solution is a symmetric hyperbolic formulation due to Friedrich and Nagy [61]. However, their mathematical treatment does not suggest how to construct a consistent evolution algorithm.

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 [101, 93, 87, 118], 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 errors introduced by these problems are of an analytic origin, essentially independent of computational discretization. In general, a systematic reduction of this error can only be achieved by simultaneously refining the discretization and moving the computational boundary to larger and larger radii. This is computationally very expensive, especially for three-dimensional simulations.

A traditional outer boundary condition for the wave equation
is the Sommerfeld condition. For a 3D scalar field this takes the
form
, where
. This condition is
*exact*
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 successful implementations of ABC's have been reported for linear problems. See the recent articles [66, 118, 148, 120, 27] for a general discussion of ABC's.

Local ABC's have been extensively applied to linear problems with varying success [101, 56, 22, 147, 87, 33, 94]. Some of these conditions are local approximations to exact integral representations of the solution in the exterior of the computational domain [56], while others are based on approximating the dispersion relation of the so-called one-way wave equations [101, 147]. Higdon [87] 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 [22], which generalizes the Sommerfeld outgoing radiation condition. Although such ABC's are relatively simple to implement and have a low computational cost, their final accuracy is often limited because the assumptions made about the behavior of the waves are rarely met in practice [66, 148].

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 [146, 66, 148]. Even for problems where the Green's function is known and easily computed, such approaches were initially dismissed as impractical [56]; 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 [48, 78]. If properly implemented, this kind of method can yield numerical solutions which converge to the exact infinite domain problem in the continuum limit, 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 [66, 48, 148].

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 [148,
120]. 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, thereby contaminating both the interior and the
exterior evolutions. But the fields and their normal derivatives
constitute an overdetermined set of data for the linearized
exterior 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 [148].

To date there have been only a few applications of ABC's to strongly nonlinear problems [66]. Thompson [144] generalized a previous nonlinear ABC of Hedstrom [86] 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 [144, 66]. Hagstrom and Hariharan [82] 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 has not yet been implemented.

In order to reduce the level of approximation at the analytic level, an artificial boundary for an nonlinear problem must be placed sufficiently far from the strong-field region. This sharply increases the computational cost in multidimensional simulations [56]. 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 multidimensions, while keeping the artificial boundary fixed.

Cauchy-characteristic matching is a strategy that eliminates
this nonlinear source of error. In 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 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 regions
where caustics develop, it proves to be both accurate and
computationally efficient in the treatment of exterior
regions.

CCM evolves a mixed spacelike-null initial value problem in which Cauchy data is given in a spacelike region bounded by a spherical boundary and characteristic data is given on a null hypersurface emanating from . The general idea is not entirely new. An early mathematical investigation combining space-like and characteristic hypersurfaces appears in the work of Duff [55]. The three chief ingredients for computational implementation are: (i) a Cauchy evolution module, (ii) a characteristic evolution module and (iii) a module for matching the Cauchy and characteristic regions across an interface. The interface is the timelike worldtube which is traced out by the flow of along the worldlines of the Cauchy evolution, as determined by the choice of lapse and shift. Matching provides the exchange of data across the worldtube to allow evolution without any further boundary conditions, as would be necessary in either a purely Cauchy or a purely characteristic evolution.

CCM may be formulated as a purely analytic approach, but its advantages are paramount in the solution of nonlinear problems where analytic solutions would be impossible. One of the first applications of CCM was a hybrid numerical-analytical version, initiated by Anderson and Hobill for the 1D wave equation [5] (see below). There the characteristic region was restricted to the far field where it was handled analytically by a linear approximation.

The full potential of CCM lies in a purely numerical treatment of nonlinear systems where its error converges to zero in the continuum limit of infinite grid resolution [24, 25, 45]. For high accuracy, CCM is also by far the most efficient method. For small target error , it has been shown that the relative amount of computation required for CCM () compared to that required for a pure Cauchy calculation () goes to zero, as [31, 28]. An important factor here is the use of a compactified characteristic evolution, so that the whole spacetime is represented on a finite grid. From a numerical point of view this means that the only error made in a calculation of the radiation waveform at infinity is the controlled error due to the finite discretization. Accuracy of a Cauchy algorithm which uses an ABC requires a large grid domain in order to avoid error from nonlinear effects in the exterior. The computational demands of matching are small because the interface problem involves one less dimension than the evolution problem. Because characteristic evolution algorithms are more efficient than Cauchy algorithms, the efficiency can be further enhanced by making the matching radius as small as consistent with avoiding caustics.

At present, the purely computational version of CCM is exclusively the tool of general relativists who are used to dealing with novel coordinate systems. A discussion of its potential appears in [24]. Only recently [45, 46, 54, 26] has its practicability been carefully explored. Research on this topic has been stimulated by the requirements of the Binary Black Hole Grand Challenge Alliance, where CCM was one of the strategies being pursued to provide the boundary conditions and determine the radiation waveform. But I anticipate that its use will eventually spread throughout computational physics because of its inherent advantages in dealing with hyperbolic systems, particularly in three-dimensional problems where efficiency is desired. A detailed study of the stability and accuracy of CCM for linear and non-linear wave equations has been presented in Ref. [27], illustrating its potential for a wide range of problems.

Characteristic Evolution and Matching
Jeffrey Winicour
http://www.livingreviews.org/lrr-2001-3
© Max-Planck-Gesellschaft. ISSN 1433-8351 Problems/Comments to livrev@aei-potsdam.mpg.de |