Richard Matzner, University of Texas at Austin
The Binary Black Hole Grand Challenge has completed more than four years of existence. A large fraction of that time has been devoted to developing a coherent infrastructure for assault on the two-black-hole problem. The Alliance approach involves a central Cauchy strong field region, a boundary (matching) module, and an outer module (perturbative, or strong-field characteristic) which carries the radiation to infinity. The interior module is an ADM (Arnowitt-Deser-Misner  ) ``'' code, with fundamental variables the 3-metric and extrinsic curvature ; the extrinsic curvature is the momentum of the 3-metric. An extensive investigation has been made of the Choquet-Bruhat/York  version of a ``hyperbolic'' Cauchy formulation, but the more traditional ADM form has the advantage of more mature development. Hence in 1996 the Alliance focused on the ADM version.
Important infrastructure features include DAGH, which allows a single-processor unigrid code to be distributed on a parallel machine, and supports adaptive mesh refinement. This system is now in use for the very largest of our black-hole runs. Another very important tool is RNPL, which takes a high-level description of the physics and the differencing scheme and generates C or FORTRAN code. Another tool, on the collaborative level, is SCIVIZ, which allows researchers to collaborate to manipulate and visualize computational results. A new file format, SDF, has been developed, which overcomes efficiency and size limitations of some other formats, for large parallel applications.
All of the Alliance codes are, and continue to be, demonstrated second order convergent. In all of our models, black holes are handled by excising the domain inside the apparent horizon. We have not yet begun (we are about to begin) carrying out multiple black hole evolutions. For single black holes (Schwarzschild or Kerr, and their strongly perturbed forms), where we expect a stationary final state, we use the analytic solution as an outer boundary condition.
Black Holes The characteristic module evolves the strong-field Einstein equations in a characteristic formation which has a very rigid coordinate gauge, and which therefore has a simpler equation set. Unfortunately it cannot be used alone for the binary black hole problem, since gravitational focusing causes caustics in the rays generating the null surfaces of the coordinatization. Thus the basic approach of the Alliance code is centered on a Cauchy strong field module. However, the characteristic code can handle single black hole spacetimes.
The characteristic module can exist in two forms based on either ingoing or outgoing characteristic surfaces. In its form based on ingoing null hypersurfaces it shows unlimited long-term stability for evolving single, isolated (distorted) black holes. In these cases data are set on an ingoing initial null hypersurface. The inner edge of the domain is set at a marginally trapped surface; no boundary condition is needed there since it is inside the horizon. The outer boundary is set analytically to the black hole solution. These problems evolve to the stationary black hole form. They have been evolved to times of 60,000 M, at which time differences are on order of machine precision, the operational definition of running forever. In some cases the coordinates are deliberately ``wobbled'' producing a time dependence in the description at late times, but producing a stationary geometry nonetheless . In the 1970s and 1980s, the difficulty of stably simulating even a single black hole in strictly spherical symmetry (one spatial dimension) led to the formulation of ``the Holy Grail of numerical relativity" - requirements for a hypothetical ``code that simultaneously:
Handles black holes
Maintains high accuracy
Runs forever.'' 
It is clear that the characteristic code has achieved the grail in the 3-dimensional single-black-hole case, a dramatic improvement over the state of the art only a few years ago. However, goals recede, and from the viewpoint of the Binary Black Hole Alliance, this is a step along the way, important because it validates the stability and accuracy of the characteristic code.
The interior code, the Cauchy code, has not yet shown the very long-term stability of the characteristic code. With fixed Dirichlet boundaries, the code runs for a maximum  of 100M for isolated Schwarzschild data written in Kerr-Schild  form. With blended outer boundary conditions, the code has been evolved beyond 500M. (The blended outer conditions are applied gradually by mixing the computed results with the analytic ones over a shell of a few computational zones' thickness; see also the discussion of this technique for perturbative matching below.) In this case there is still some influence from the outer boundary and there are additional modes (small oscillations in the supposedly static solution) which are not fully understood. What is apparent is that inaccurate outer boundary setting disturbs the code substantially (which is why the matching algorithm is so important), but the inner edge of the domain, handled with causal differencing (hence ``no boundary condition'') is well behaved, and this free evolution shows (at worst) controllable constraint drifting.
The Kerr-Schild data are represented by two fields on a background flat space: a scalar function ( for Schwarzschild), and a null vector (ingoing, unit for Schwarzschild). Because of this very simple structure, boosting these data is trivial, and we have used such boosted initial data to start evolutions of black holes moving across the computational domain. So far as we know, only the Alliance has achieved this. The characteristic code has demonstrated a linearly moving black hole . However (because of the caustic problem), the characteristic module cannot evolve a black hole moving farther than one diameter. The Cauchy module can do so, and has been demonstrated to do so for 60M in time at , hence a translation through 6M in distance . The boundary conditions for this moving case are analytical Dirichlet with no blending. (Since we know the analytic form for the boosted black hole as a function of time, we compute new outer boundaries as a function of time for the evolution.)
The black hole interior is excised in all our evolutions. At the resolutions we use (typically 60 to 100 grid zones in each direction), there is room for only a few () points interior to the black hole. We find the best behavior when the hole is excised with a buffer zone zones wide for both the moving and the stationary evolutions. Thus the excision of the interior occurs zones inside the apparent horizon location. This is probably relevant to the fact that we do not lock the horizon coordinate location. Rather, the excision is based on the analytically expected coordinate location of the horizon; and all our code crashes seem to be related to the excised, un-evolved, region eventually extending beyond the horizon. (This can happen because coordinate drift, which we do not attempt to control, changes the coordinate location of the horizon, while our excision domain has a fixed coordinate location.) To our knowledge only Daues  has demonstrated active horizon locking in 3-dimensional black holes. Daues achieved non-moving Schwarzschild black hole evolutions. Implementing this tracking in the Alliance code is a high priority and holds out the hope of even longer evolutions.
Exterior Modules and Matching
The perturbative exterior module is written in explicitly Cauchy form. The terms neglected in this perturbative module are wave-wave interactions, while the background is explicitly modeled (Kerr or Schwarzschild). The matching to the Cauchy interior works in this case; this matching has been demonstrated for linear waves with very long evolution ; some more recent results are at the Alliance web site (see below). The matching is accomplished in a way that correctly treats the outgoing nature of the solution; in fact, the Sommerfeld condition is modified on its right-hand side from 0, to a contribution arising from the perturbative outer evolution, so there is a strong similarity between the perturbative and the characteristic boundary application.
In practice, the perturbative outer boundary match is handled in a ``thick'' shell. At some radius , the inner solution is sampled. These data are used for a perturbative evolution to a very large radius . At a finite radius begins the boundary region . The computed inner solution is merged in this region with the value determined from the exterior module. This provides a merged boundary condition on the interior solution: that the Sommerfeld condition properly reflect the terms describing backscatter, derived from the perturbative evolution. For the weak wave case this is a successful complete expression of the inner-module/boundary/outer-module paradigm of the Alliance philosophy.
To match the characteristic module to the Cauchy inner module, the outgoing characteristic form must be used. (This match has not yet been achieved.) For outgoing radiation near the coordinate outgoing null surfaces, the wave variables have slow variation, and the system can be compactified so that infinity is a finite distance away while still maintaining finite derivatives. Hence, a characteristic code can compute the whole exterior spacetime in a finite domain. For nonlinear scalar radiation , for spherical general relativity , for cylindrically symmetric relativity , and as we saw, for the weak field problem in full 3-d general relativity, the match has been carried out. But so far a stable match between the full 3-d strong-field Cauchy and characteristic modules has not been achieved. We are now attempting such a match through blending, as in the successful perturbative case, and there is hope that such an approach will work to match the Cauchy and the characteristic codes.
Immediate future work involves setting data and beginning 2-hole evolutions. Because of the apparently better behavior of Kerr-Schild formulated single holes, the initial data is being recomputed for this case. (These slices differ macroscopically from the ``standard'' conformally flat data that were solved completely prior to the beginning of the Alliance .) This work will proceed while further runs for single holes continue. The Cauchy module requires standardization, validation against known behavior of distorted black holes, and an explicit demonstration of its ability to evolve rotating (Kerr) black holes.
Recent developments, including the points discussed here, are frequently posted to the Los Alamos preprint archive, and can also be found at the Alliance Web page:
Select ``New developments.''
Richard Matzner is the Lead PI of the Binary Back Hole Grand Challenge Alliance, NSF ASC/PHY 9318152 (arpa supplemented), which supported this work.
 R. Arnowitt, S. Deser, C. W. Misner, in
Gravitation, an Introduction to Current Research,
L. Witten, ed. (Wiley, New York, 1962).
 Y. Choquet-Bruhat and J.W. York, ``Geometrical Well Posed Systems for the Einstein Equations,'' C.R. Acad. Sci. Paris, 321 1089 (1995).
 The Binary Black Hole Grand Challenge Alliance, ``Stable characteristic evolution of generic
3-dimensional single-black-hole spacetimes", submitted to Physical Review Letters (1998). gr-qc/9801069
 S.L. Shapiro, S.A. Teukolsky, in Dynamical Spacetimes and Numerical Relativity, ed. J. Centrella (Cambridge UP, Cambridge, 1986) p. 74.
 The Binary Black Hole Grand Challenge Alliance ``Boosted three-dimensional black-hole evolutions with singularity excision", Physical Review Letters (in press, 1998). gr-qc/9711078
 R.P. Kerr and A. Schild, ``Some Algebraically Degenerate Solutions of Einstein's Gravitational Field Equations,'' Applications of Nonlinear Partial Differential Equations in Mathematical Physics, Proc. of Symposia B Applied Math., Vol. XV11 (1965). R.P. Kerr and A. Schild,``A New Class of Vacuum Solutions of the Einstein Field Equations,'' Atti del Convegno Sulla Relativita Generale: Problemi Dell'Energia E Onde Gravitazionale, G. Barbera, ed. (1965).
 R. Gomez, L. Lehner, R.L. Marsa, J. Winicour, ``Moving Black Holes in 3D", The Physical Review D56, 6310 (1997). gr-qc/9710138
 G. Daues, Ph.D. dissertation, Washington University, Saint Louis (1996).
 The Binary Black Hole Grand Challenge Alliance ``Gravitational wave extraction and outer boundary conditions by perturbative matching", Physical Review Letters (in press, 1998). gr-qc/9709082
 Nigel T. Bishop, Roberto Gomez, Paulo R. Holvorcem, Richard A. Matzner, Philippos Papadopoulos, and Jeffrey Winicour, ``Cauchy-characteristic matching: A new approach to radiation boundary conditions,'' Physical Review Letters 76 4303 (1996).
 R. Gomez, R. Marsa and J. Winicour, ``Black hole excision with matching,'' Physical Review D 56, (November 1997), gr-qc/9708002.
 C. Clarke, R. d'Inverno, and J. Vickers, Physical Review D 52, 6863 (1995).
M. Dubal, R. d'Inverno, and C. Clarke, Physical Review D 52, 6868 (1995).
 G.B. Cook, M. W. Choptuik, M. R. Dubal, S. Klasky, Richard A. Matzner and S.R. Oliveira, ``Three-Dimensional Initial Data for the Collision of Two Black Holes,'' Physical Review D 47 1471-1490 (February 1993).