4.2 Perturbative CCM4 CCM4 CCM

4.1 Computational Boundaries

Boundary conditions are both the most important and the most difficult part of a theoretical treatment of most physical systems. Usually, that's where all the physics is. And, in computational approaches, that's usually where all the agony is. Computational boundaries for hyperbolic systems pose special difficulties. Even with an analytic form of the correct physical boundary condition in hand, there are seemingly infinitely more unstable numerical implementations than stable ones. In general, a well posed problem places more boundary requirements on the finite difference equations than on the corresponding partial differential equations. Furthermore, the methods of linear stability analysis are often more unwieldy to apply to the boundary than to the interior evolution algorithm.

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 tex2html_wrap_inline1865, 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 [66].

The correct physical formulation of any asymptotically flat, radiative Cauchy problem requires boundary conditions at infinity. These conditions ensure not only that the total energy and the energy loss by radiation are both finite, but 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 space-time by means of a pure Cauchy evolution involves both inner and 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 [67]) initially suggested what is now the accepted strategy for Cauchy evolution of black holes. An inner boundary located at (or near) an apparent horizon is used to excise the interior region. Below, we discuss an alternative version of this strategy, based upon matching to a characteristic evolution in the inner region.

First, consider the more universal 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 [68Jump To The Next Citation Point In The Article]. Characteristic evolution avoids this problem by approaching infinity along phase fronts.

Assuming that 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 shrinks 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 is easy to state when dealing with a constraint free field, such as a scalar field tex2html_wrap_inline1763 where the Cauchy data outside the boundary would be tex2html_wrap_inline1877 . 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 represent it by counterfeit data on the outer boundary.

Instead, in practice, some artificial boundary condition (ABC), such as an outgoing radiation condition, is imposed upon the boundary 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 [69Jump To The Next Citation Point In The Article, 68, 70Jump To The Next Citation Point In The Article, 71Jump To The Next Citation Point In The Article], 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 tex2html_wrap_inline1879, where tex2html_wrap_inline1551 . This condition is exact for a linear wave with spherically symmetric data and boundary. In that case, the exact solution is tex2html_wrap_inline1883 and the Sommerfeld condition eliminates the incoming wave tex2html_wrap_inline1885 .

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 [72Jump To The Next Citation Point In The Article, 71, 73Jump To The Next Citation Point In The Article, 74Jump To The Next Citation Point In The Article, 75Jump To The Next Citation Point In The Article] for a general discussion of ABC's.

Local ABC's have been extensively applied to linear problems with varying success [69Jump To The Next Citation Point In The Article, 76Jump To The Next Citation Point In The Article, 77Jump To The Next Citation Point In The Article, 78Jump To The Next Citation Point In The Article, 70Jump To The Next Citation Point In The Article, 79, 80]. Some of these conditions are local approximations to exact integral representations of the solution in the exterior of the computational domain [76Jump To The Next Citation Point In The Article], while others are based on approximating the dispersion relation of the so-called one-way wave equations [69, 78]. Higdon [70] 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 [77], 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 [72Jump To The Next Citation Point In The Article, 73Jump To The Next Citation Point In The Article]. In general, systematic improvement can only be achieved with local conditions by moving the computational boundary to a larger radius, which is computationally expensive - especially for three-dimensional simulations.

The disadvantages of local ABC's have led some workers to consider the exact nonlocal boundary conditions based on integral representations of the infinite domain problem [81, 72Jump To The Next Citation Point In The Article, 73Jump To The Next Citation Point In The Article]. Even for problems where the Green's function is known and easily computed, such approaches were initially dismissed as impractical [76Jump To The Next Citation Point In The Article]; however, the rapid increase in computer power has made it possible to implement exact nonlocal ABC's even for the 3D linear wave equation [82Jump To The Next Citation Point In The Article]. 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 of grid size (tex2html_wrap_inline1887 per time step in three dimensions) than in a local approach [72Jump To The Next Citation Point In The Article, 82, 73Jump To The Next Citation Point In The Article], which in multidimensional problems may be very demanding even for today's supercomputers.

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 [73Jump To The Next Citation Point In The Article, 74]. 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 have to be 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 [73].

To date there have been only a few applications of ABC's to strongly nonlinear problems [72Jump To The Next Citation Point In The Article]. Thompson [83Jump To The Next Citation Point In The Article] generalized a previous nonlinear ABC of Hedstrom [84] 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 [83, 72]. Hagstrom and Hariharan [85] 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 analytical 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 [76]. 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 of the space-time cuts the worldtube into spherical slices. 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 space-time at a finite distance from the sources, since compactification of the radial null coordinate makes it possible to cover the whole space-time 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 tex2html_wrap_inline1889 and characteristic data is given on a null hypersurface emanating from tex2html_wrap_inline1889 . The general idea is not entirely new. An early mathematical investigation combining space-like and characteristic hypersurfaces appears in [86]. 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 tex2html_wrap_inline1889 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 [87Jump To The Next Citation Point In The Article] (see below). There the characteristic region was restricted to the far field where it could be 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 [88Jump To The Next Citation Point In The Article, 89, 90Jump To The Next Citation Point In The Article]. For high accuracy, CCM is also by far the most efficient method. For small target target error tex2html_wrap_inline1895, it has been shown that the relative amount of computation required for CCM (tex2html_wrap_inline1897) compared to that required for a pure Cauchy calculation (tex2html_wrap_inline1899) goes to zero, tex2html_wrap_inline1901 as tex2html_wrap_inline1903 [59, 91Jump To The Next Citation Point In The Article]. An important factor here is the use of a compactified characteristic evolution, so that the whole space-time 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 possible 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 [88]. Only recently [90Jump To The Next Citation Point In The Article, 46Jump To The Next Citation Point In The Article, 47Jump To The Next Citation Point In The Article, 92Jump To The Next Citation Point In The Article] has its practicability been carefully explored. Research on this topic is currently being stimulated and guided by the requirements of the Binary Black Hole Grand Challenge Alliance. CCM is one of the strategies being pursued to provide the boundary conditions and determine the radiation waveforms for the binary black hole problem. But I anticipate that its use will eventually spread throughout computational physics because of its inherent advantages in dealing with hyperbolic systems, particularly in 3-dimensional problems where efficiency is necessary. A detailed study of the stability and accuracy of CCM for linear and non-linear wave equations has been presented in Ref. [75Jump To The Next Citation Point In The Article], illustrating its potential for a wide range of problems.



4.2 Perturbative CCM4 CCM4 CCM

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