Strategy Report of the Super-cognizant Scientists to the lead PI of the Binary Black Hole Grand Challenge

October 31, 1996

Preamble

At the request of the lead PI of the Binary Black Hole Grand Challenge Alliance, Richard Matzner, we, the Alliance Super-Cogs (Jim Browne, Pablo Laguna (Strategy Report Chair), Saul Teukolsky and Jeff Winicour), have developed the following proposal for the Alliance strategy. The need for a concrete strategy has been always apparent, more critically now that there are fewer than two years left to reach the goals set by the Alliance. In the preparation of this strategy proposal, we asked most of the Cognizant Scientist to submit brief statements addressing specifically the following main points: (1) current status of the project under their supervision, (2) identify efforts requiring a more focused direction, and (3) recommendations of enhancement of resources in high priority areas. We should point out that most of the input received did not include any significant proposals to narrow efforts. Due to time limitations for the preparation of this strategy report (approximately one week), it was not possible to fully address every single aspect within the Alliance.

The Codes

This section was prepared with input from Matt Choptuik, Greg Cook and Mark Scheel. The Alliance is currently developing two codes for evolving binary black hole spacetimes. One of the codes (the ADM code) is based on the traditional ADM (∂_{t}g, ∂_{t}K) equations. The second code (the Empire code) is written using a hyperbolic formulation of Einstein equations developed by Choquet-Bruhat and York.

Both codes have been capable of evolving static single black hole spacetimes for times of up to ∼ 10M. Second order convergence has been demonstrated in both codes. The main limitations for performing longer evolutions have been instability at the outer boundary, problems at the inner boundary, and not using AMR. (These issues are amplified below.) The Empire code effort has focussed on issues directly related to the implementation of the apparent horizon boundary condition and causal differencing. On the other hand, the work on the ADM code has recently concentrated on the translation of a single black hole using Eddington-Finkelstein (EF) coordinates. The ADM code was indeed able to translate a black hole for a coordinate distance of 0.5M with a boost velocity of 0.25 before an instability in the inner boundary caused the code to crash. This modest success was possible because of the nature of the EF coordinates (see below). Furthermore, the initial data slice crosses the horizon and ends at the singularity so it is easy to get initial data “just inside” the hole. This is perhaps not a critical advantage since in theory one should not need to use points inside the apparent horizon.

There are two real reasons why EF coordinates have worked as well as they have. First, when the hole is not translating, all of the variables are time-independent. The code is not really “stretched” in the way it is with other slicings. Second, there is an analytic solution for the lapse and shift, even for a translating hole. By using the analytic lapse and shift, we are guaranteed to preserve “good” coordinates. The tests performed so far hint that the method used is stable for short periods of time when there is no dynamics to the situation. As soon as the problem becomes truly dynamic, there is no guarantee that EF coordinates will help or that the ADM code will even be stable because of gauge effects. The gauge modes are suppressed in the EF evolution because of the simple time independent nature of the solution. Also, keep in mind that the reason that no long term evolutions have been performed with the Empire code is that there is no way to specify the shift at present. As soon as a shift solver is available, and it will be necessary for the ADM code to move beyond these simple tests, the Empire code will also be available to participate in these tests.

The Empire team sees that the real key issues at this time are

1. finding an algorithm for implementing apparent horizon boundary conditions that is sufficiently accurate and stable and

2. finding a shift condition that will lead to reasonable coordinates during the evolution.

Choptuik has pointed out that the bulk of the time which has been spent studying the EF coordinate system (i.e. Marsa’s thesis) was, of course, motivated by precisely the fact that they seem so suited for black hole evolutionwith-excision. Even if we do not know, at this time, how to generalize the coordinate system in a fashion which will allow in-spiral, it is clear from thinking about the nature of the in-spiral spacetime that, at least locally around each hole (which is where the dynamics will be most extreme), EFlike coordinates (systems based in a fundamental fashion on some appropriate class or classes of null observers) have as good a chance as any of being sound for generic evolutions. Furthermore, we have every reason to believe that if any coordinate system remains non-pathological, it will be possible to construct some stable difference scheme. Choptuik adds that as far as he knows, we have no counterexample to his previous statement. In particular, there is absolutely no evidence that solutions of Einstein’s equations in EF-like coordinates will display “gauge modes” or other instabilities which can be traced to the particular choice of coordinates. Finally, as it is emphasized at the end of this report, the choice of a coordinate system is absolutely crucial at this juncture. Experience in numerical relativity (as well as other sub-fields of computational physics) has shown that given a well-posed problem, many techniques, difference schemes etc., can be used to construct an acceptable (researcher-dependent criteria to be sure) solution. In our case “well-posedness” includes the prescription for a coordinate system, so our ultimate goal remains fundamentally “ill-posed”. Choptuik concludes that arguing that a duplicity of numerical efforts will increase our success of getting to the analytically well-posed stage seems optimistic in the extreme. However, the above is not the view of a number of others in the Alliance. They argue that no one has actually constructed EF-like coordinates for multiple holes yet, and cutting back on our code development to search for such coordinates also seems optimistic in the extreme.

Currently, there are two approaches being investigated for implementing apparent horizon boundary conditions. The principal approach can be referred to as ”causal differencing”. The key aspect of this approach is that it depends on interpolation to implement the advection phase of the Lie derivative along the shift. This method is implemented in both the ADM and Empire codes and both are second order convergent methods. The questions of accuracy and stability for this method must now be answered. Memory restrictions are currently limiting our ability to answer these questions in 3D.

Current estimates of the memory requirement for performing simple, single hole tests of stability and accuracy are somewhat discouraging and adequate tests may not be possible in the near future. The memory differences between the ADM and Empire codes are small (less than a factor of 2), and this statement applies equally to both codes. Using a 1D version of the Empire code with causal differencing, one can perform long runs. Using very high resolution, we find that the boundary condition, as currently implemented, is stable for at least about 70M, but the scheme is not very accurate. Preliminary indications are that the interpolation is quite dissipative, but while this is the likely candidate, there is no direct proof that interpolation is the cause of the dissipation. To test this, another approach must be used that does not depend on interpolation. The hyperbolic nature of the Empire code allows for such an approach based on the decomposition of the advective terms into advection equations for the characteristic variables of the hyperbolic system. Inner boundary schemes based on this approach are currently being investigated in the 1D Empire code, but a new set of problems must be dealt with in this case and no reliable results are available yet.

At present, there is no reason to abandon either the ADM or the Empire code. In fact, it would be unwise to abandon either of the codes. No test performed until now has shown yet that there is a clear superiority of one code over the other. From past experience, there is strong indication that porting modules (e.g. causal differencing schemes, apparent horizon trackers etc.) from one code to the other does not require a significant investment effort. The effort to maintain these two codes is considerably less than that involved in exploring inner-boundary issues. The bottom line is that the majority of progress made in with one code will be easily applicable to the other. The ADM code does provide a test bed for the causal differencing scheme so it would not be wise to eliminate the ADM code. Any advances made with causal differencing in the ADM code will be usable in the Empire code. (In fact, the causal differencing code was first implemented in the Empire code and then inserted in the ADM code very quickly.) Tests of the new characteristic inner boundary algorithm should continue, but there is no guarantee that this approach will prove fruitful. On the other hand, there are no guarantees that the causal differencing scheme will work and the new scheme may be the only approach.

Outer Boundary Module

This section was prepared based on input from Andrew Abrahams and Roberto Gomez. Progress on the Outer Boundary module is roughly on schedule with the timeline proposed at the Chapel Hill meeting. (Delays due to switching responsibilities at the interface from Code to Outer Boundary tasks have arisen but in a healthy way that has contributed to improvements at the technical level). The extraction module is reaching completion, except for calibration and scientific infrastructure (e.g. extraction of polarization, Bondi mass, frequency spectrum). This module is currently being molded into the evolution codes. The numerical analysis of the algorithm has also been completed to determine what orders of interpolation are necessary to match the accuracy of a second order interior code. It has been established that the CPU and memory requirements of the extraction module are a small fraction of the interior code requirements and adding the injection module will not essentially change this.

The major remaining tasks of implementation of the Outer Boundary module can be split in two categories: (1) Carrying out the algebra and the programming and (2) establishing a stable interface. Item (1) we know can be done but that will not be useful without item (2). Item (2) could be automatic but could also be a long range nightmare similar to the situation at the inner boundary. Only extensive experimentation with 3D evolution codes will determine this.

In order to optimize our chances of licking the stability problem, the Outer Boundary Cogs (Abrahams and Gomez) propose continuing the present strategy of leaving open the option between a perturbative and characteristic matching approach at the outer boundary. In accord with the present cooperative tactics, they argue that this does not present a major delay or misuse of manpower in carrying out item (1) because submodules are being shared and the available personnel are working with formalisms with which they are expert. For example, the surface integration module using stereographic coordinates produced at Pittsburgh is being used to compute multipole moments for the perturbative exterior. They add that any shift of the personnel expertise at this time would be counterproductive and would diminish the probability of attaining a successful outer boundary module on the time scale it is needed. It is important at this stage that the perturbative and characteristic matching approach both remain as options, while continuing to develop them efficiently in the context of a common worldtube infrastructure.

Although the development of the Outer Boundary module seems to proceed at a healthy pace, the Cogs recognize the importance of completing some initial version of the module which will facilitate Code and Inner Boundary module progress. They propose to pursue all possible ways to do this without derailing the progress toward the final goal. This can be accomplished by slackening the accuracy requirements in item (1) (e.g. dropping second order accuracy when expedient, developing a unigrid module) so that the unpredictable issues of item (2) can be faced earlier. It may also be possible to provide exterior modules tailored to particular test problems under exploration with the interior codes. When stability at some reasonable level of accuracy has been established it would then be appropriate to reassess the strategy and manpower requirements of the Outer Boundary module

Inner Boundary and Coordinate Conditions

The following material is based on a summary of a mini-meeting on inner boundaries held at NCSA (Oct. 19, 1996) prepared by Chuck Evans. The focus of the meeting was to determine how close we are to being able to excise black holes from simulations by treating their surfaces as inner boundaries of a computational domain. This problem is so central that it overlaps with the issues of mathematical formalism, coordinate choices, computational impacts of shift vector choices, etc. The discussions in this meeting included:

1. the state of development of the 3D and 1D (hyperbolic) Empire codes

2. the state of development of the 3D ADM code

3. the state of incorporation of DAGH in the Empire and ADM codes

4. summary of implementation of shift vector capability in Empire

5. successful and failed tests with shift vectors in 1D Empire code

6. summary of recent tests of advecting a black hole with the ADM code

7. discussion of need for dynamic & more general shift and lapse conditions

8. the issue of coordinate shocks in simulations & methods of avoidance

9. discussion of causal differencing versus characteristic differencing

10. problem of ‘upwind’ direction change in characteristic differencing

11. use of buffer points inside black hole surface or not 12. inclusion of apparent horizon finders in evolution codes

13. new estimates of computational demands of test problems & full inspiral

14. discussion of presently available machines: processor numbers & memory

The shift vector terms have been added to the Empire code. Experiments with various shift vectors have been tried with the 1D Empire code with mixed success, but it seems clear that effort in 1D experiment should be kept because of the long term evolutions that one has access in this case.

Experiments with analytically known coordinates, e.g. Eddington-Finkelstein, are highly useful but insufficient. One of the most important outstanding theoretical issues for this year is how to specify dynamic lapse and shift conditions that, when coupled at the apparent horizon, lead to regular coordinates that maintain adequately resolved holes and exterior regions.

Elliptic shift conditions may be crucial to maintaining smooth spatial coordinates (avoiding coordinate shocks). Elliptic conditions, if solved exactly, will be very expensive computationally. However, it may be feasible to use inexpensive approximate solutions to the elliptic conditions and obtain adequate coordinate smoothness. Approximate solutions to any specific elliptic condition will not introduce inconsistencies as long as the conditions are not also incorporated elsewhere in the form of the evolution equations (as many of us used to do). Experiments in 1D can be important demonstrations of feasibility.

Lapse conditions or evolutions of the lapse (in the hyperbolic scheme) may also lead to time slice irregularities. These were discussed and a suggested solution is to ‘restart’ the lapse if irregularities begin to develop (more difficult may be knowing when time slice irregularities are developing). Again, experiments in 1D can be very useful in testing this idea. Experiments in 1D seem also to indicate that because of diffusion alternatives to causal differencing need consideration. The Empire team are considering characteristic variable differencing schemes which have different dissipative behaviors. The issue of whether to use buffer zone points inside the apparent horizon or not requires also careful attention. There is not clear resolution of the issue. Restricting the calculations to only those points in the black hole exterior seems to be philosophically the ‘royal road’ but the alternative may allow less complicated differencing and interpolation. For locating the apparent horizon these buffer points might be useful but their use in updating advection terms may lead to instabilities or acausal behavior depending on resolution and coordinate conditions.

The following is a list of a series of numerical experiments and code development goals that appear to be important in gaining understanding of how to treat black hole inner boundaries and in assessing which approach to the Einstein equations is numerically preferable.

1. Numerical experiments in shift choices using the 1D Empire code

2. Numerical experiments with lapse restarts in the 1D Empire code

3. Rapid development of a general 1D ADM code

4. Lapse and shift choice experiments with 1D ADM code

5. Continued experiments translating BH with EF coordinates with ADM code

6. Experiments translating BH with dynamic lapse and shift (ADM)

7. Experiments translating BH with dynamic lapse and shift (Empire)

8. Evolution of Kerr hole with analytic lapse and shift with 3D ADM code 9. Generalize evolution of Kerr hole using dynamical lapse and shift (ADM)

10. Generalize evolution of Kerr hole using dynamical lapse and shift (Empire)

11. Incorporate DAGH in 3D ADM code

12. Experiments with characteristic variables & differencing in 1D & 3D Empire

13. Stabilization of the outer boundary During that meeting the following recommendations were made:

1. There is insufficient basis for judging the numerical superiority of either the Empire code or ADM code at present. Development of both should be pressed, with the earliest possible demonstration of results on key 1D and 3D experiments.

2. Experiments in 1D are particularly important at this stage since much needs to be learned about viable coordinate choices and differencing schemes and the turn-around time on 3D experiments is very long at present. Experiments in 1D can rapidly determine which shift choices lead to irregular coordinates (shocks) and which do not. Experiments in 1D can test lapse restarts as a means of avoiding the development of irregular time slices. A general 1D ADM code should be quickly written for these purposes and for side-by-side tests (where possible) with the 1D Empire code.

3. Using analytic coordinates (lapse and shift) in experiments in 3D with known solutions for a translating black hole or a Kerr hole is a very useful means of breaking the problem down and testing black hole excision and whether causality is maintained numerically at the inner boundary. The black hole translation experiment needs to be pressed further and it is important to begin a parallel set of experiments trying to evolve a Kerr hole for many crossing times.

4. While experiments in 3D with translating a black hole or evolving a Kerr hole with analytic coordinates are useful in many ways, such as testing black hole excision and numerical causality, these coordinates are of no use in the general case of a translating, rotating, and accelerating hole. Careful thought needs to be given to what coupled choice of the lapse and shift at the apparent horizon will captures the key properties of, for example, Eddington-Finkelstein coordinates for a non-rotating hole. This is a major outstanding theoretical issue that now must be tackled.

5. We need to focus on the core elements of the problem and assemble teams to tackle some or all of the numerical experiments and theoretical issues listed above. Test (beta) versions of 1D and 3D codes are available and can be used for experimentation while further development proceeds simultaneously. The Syracuse meeting is an opportunity

to try to assemble teams interested in this area.

DAGH

The following material was prepared by Browne and Manish Parashar regarding the future work in the BBH project on DAGH.

1. There are a number of enhancements which are generally needed. These include extraction of matrices, checkpointing, better I/O, better interface with visualization and display and extension of grid formulations. These are mostly underway.

2. There are a number of specific requests for small features and bug fixes from the Alliance users which are specific to the Alliance applications. These need to be taken care but are not currently receiving the effort they need. This is an issue for the Alliance.

3. There is need for a Tutorial on how to use DAGH and better documentation.

4. DAGH will be maintained at Texas and at Syracuse in mirror sites.

5. Priorities for DAGH Support - Browne proposes that we survey the DAGH users in the Alliance and get their priorities for enhancements and bug fixes.

6. We need to build up a cadre of expertise at several institutions. Perhaps a workshop on DAGH structure and organization is needed.

Full checkpoint capability: DAGH can dump state at any time. The checkpoint file is currently a binary file (Manish will be looking at using XDR rep in the future) that is indexed for random access. DAGH can then be either restarted or can rollback to the state in the file. The checkpoint/restart is general enough so that it can be restarted on a different number of procs (smaller or larger). Also, DAGH can be restated with a subset of the original GridFunctions. The state-file can be indexed by GridFunction name. The idea here is that an Viz program can read the state of the GridHierarchy and the data associated with only a small number of GF’s that it wants to Viz. The user can select which GF’s to dump by appropriately setting the GF’s checkpoint attribute. Note that the state of the GridHierarhy is written at the HDDA storage level and Manish thinks that the checkpoint approach should extend to other abstractions built on the HDDA. GridFunctions to UCD (Unstructed Cell Data) format conversion: DAGH can now return the global UCD data structure for a composite grid given a minimum level/maximum level pair. UCD is a very general format for representing grid connectivity information and is used by a large number of available Viz packages (AVS, Explorer, pV3, etc). Connectivity information for a dynamically adaptive grid (where the number and extents are not always known globally) can be a little tricky to generate. The minlevel/maxlevel pair allows one to select the resolution at which the data is to be visualized. DAGH can also stream this data directly to an AVS/Explorer/etc client using TCP/IP sockets.

Using these two components we have simple interactive Viz. The system consists of two units. The computation unit is a regular DAGH application that performs multi-resolution computations. The compute unit also checkpoints at regular intervals and pings the Interactive Viz unit. The viz unit reads the state from the checkpoint file and displays the state using AVS. The user can interact with the Viz unit and can selective query which GF’s to viz, what resolutions to viz (using minlev/maxlev) and what region to viz using BBoxes. The user also has access to the full set of AVS modules to slice, find isosurfaces, add colormaps, etc. The user can then tell the Interactive Viz unit to step to the next state at which point it will read the next checkpoint file, set its state accordingly, refresh the display. The user can also instruct the Viz unit to automatically read successive checkpoint files and update the display (this can be though of as a play mode and the previous one a single-step mode).

All this works. The next step is to pass information back from the Viz unit to the compute unit. The way Manish proposes to do this is to move the Viz unit to the DAGH IO node. The IO node already interacts with the compute nodes. What Manish is planning to do is to defined a small command language that the IO node and compute nodes use to talk to each other. This language will provide commands to set/query pre-registered variables, to initiate a checkpoint, to request a UCD stream, to rollback using a previous checkpoint, etc.

Paul Walker, at Potsdam, is building a Java interface for this command language which is what the user will use to steer the computation. The new setup will have the following:

1. DAGH compute nodes that do the multi-resolution computation

2. DAGH IO node that, when in interactive mode, listens for input from the Java and passes them to the compute nodes.

3. Interactive Viz process that accepts DAGH state and UCD streams and uses AVS to provide interactive Viz.

Finally, Manish has overloaded the C++ new & delete operators to implement 2 level ”virtual” storage using a file. The idea here is simply that on each node, we mirror the core memory transparently go to disk. On an AFS system this also gives us two means of communication - using MPI messages and using files & offsets. The latter can be useful for communications with IO/Viz nodes etc where there is large amounts of data and latency is not critical. Again this just a hack but demonstrate the idea that HDDA can be easily extended to out-of-core.

AMR

The following material was prepared by Matt Choptuik. AMR development within the GC project is proceeding at a satisfactory pace. The lower-level infrastructure needed to implement Berger and Oliger type AMR on massively parallel systems is essentially complete and fairly well tested (see DAGH report). A prototype high-level driver for wave equations in two space dimensions has been coded and is currently being exhaustively tested. This driver should be able to serve as a template for a generic AMR code such as that ultimately planned by the Alliance.

Recommendations for near-term Alliance AMR work include the following, roughly in order of perceived urgency (note the considerable overlap with the DAGH suggestions)

1. Completion of the 2d wave-equation example, (comprehensive testing) and full documentation of that example to be included as an integral part of the updated DAGH Users manual.

2. Continued work on I/O, checkpointing and visualization issues.

3. Implementation of the initial-data problem for two black holes in a 3D AMR set-up (compatible with the generic AMR driver alluded to above). This should be relatively straightforward to do using excising ”components” (such as the various 3D Hamiltonian constraint solver), but is still a non-trivial exercise which could also give us concrete indications re resolution requirements for collision problems and how effectively Berger and Oliger AMR will handle them.

4. Incorporation of one of the ”Codes” into the AMR structure. Ideally, this should wait until issues of coordinate choice, boundary conditions and stability have been sorted out. Some argument can be made that AMR will allow us to circumvent some of the outer boundary issues, but the relatively primitive state of analysis facilities for AMR computations may mean that such work would proceed significantly slower than might be anticipated.

Collaborative Infrastructure

One of the goals of the Alliance was to develop a collaborative model among numerical relativists and computer scientists. An infrastructure was set up to facilitate and promote the onset of collaborations. In addition to bi-yearly meetings, the Alliance has currently the following tools for this purpose:

1. Home Page

2. Newsletter

3. Baseline Library

4. Preprint Library

5. Mail Reflector

6. Code Repository

All of the above have been partially successful. The number of contributions to the newsletter has been declining but still serves as the main source of information on the Alliance’s progress. There are, however, several issues that need to be addressed. The Baseline Library has not had a new code submitted for over a year, and, for a significant number of codes mentioned in this Library, the source is not available. That is, to some extent the Library is becoming more an index that provides information of existing codes than a source depository. Another attempt for improving the collaboration was to have a Code Repository of codes under development The goal here was to keep versions of codes that have achieved certain benchmarks. This has also fallen short of what it was expected. With the exception of the group in Cornell, very few attempts have been made to regularly produce snapshots of the codes. The mail reflector as a tools to communicate and carry on discussion has clearly failed. There are only 66 email, 85% from Scott Klasky and Tom Haup!

The bottom line is that the Alliance is not using all the resources available. Before insisting that people must use them, we need to find out why they are not being used and, what is more important, which tools are indeed needed. The collaborative infrastructure should provide help to the people in the Alliance, without becoming a burden. We are a large collaboration for theoretical gravitation standards, but perhaps not large enough to justify investing in creating an infrastructure of this magnitude. For instance, the system of Cognizant Scientists (Cogs) could be used as an example that more does not necessarily means better. The Cogs, as quoted from our mission plan, are “directly responsible for the scientific progress of a particular aspect of the Alliance effort.” In theory, this is an effective approach to manage the different effort within the Alliance; except for the fact that presently there are 18 Cogs for 50 people directly involved in Alliance according to our home page directory. If we agree that a change in the management structure of the Alliance is needed, certainly the move should be towards a more vertical approach.

Conclusions and Recommendations

There has been, without any doubt, significant progress within the Alliance and definitely a stronger sense of collaboration has emerged. In particular, the organization of one day meetings (Pitt, Syracuse, NCSA) has played a fundamental role. They provide a perfect forum to learn specific details of the work in the project and help identifying areas where enhancement of effort is needed. Weekly conference calls (e.g. Outer Boundary) have also paid important dividends. On the other hand, people are not utilizing all their resources available (mail reflectors, code repositories, manuscript circulation etc.). In summary, we need to re-define our collaborative scheme to fit people’s needs. Furthermore, the general mood within the Alliance is that, in spite of the progress, the odds of reaching all the goals are not completely in our side. We recommend to also re-examine and prioritize both, the CS and Physics goals. However, it is imperative that this task includes direct input from the people that are actually performing the bulk of the effort.

In developing this strategy proposal, the major conclusion drawn regarding narrowing the effort of the Alliance is that such strategy is difficult to implement with the current decision-making structure. Fortunately, our preliminary conclusion is that it does not seem advisable to narrow the effort significantly at present. The only significant narrowing of effort in the past has come in the number of codes under development, from 4 codes (Empire, H, G and ADM) to two (Empire and ADM), and this was not thanks to general consensus but by external factors (the move of Seidel’s group to Potsdam). There are currently two areas in which, in principle, it would seem that narrowing direction is required: the codes and the outer boundary. The input received by this committee strongly argues in favor of keeping the present approach: two codes + two outer boundary modules. There is NOT clear evidence at this point about which approach is significantly superior. Moreover, even if indeed an approach is superior, a specific procedure to identify and rule in favor of a given effort does not exist.

Finally, we want to emphasize that one of the highest priority areas in the physics part of this project at this point is the choice of coordinate conditions (lapse and shift) that allow excising and moving the holes. This problem touches upon all the aspects of the Alliance (theory, causal differencing, AMR, elliptic solvers, etc.) and requires significant enhancement.