DCPL: High Level Descriptor-driven Integration of Prototyping, Communication, and Large Parallel Linear Solvers for Learning and for Simulation of Physical Systems

Matthew Choptuik Robert van de Geijn Richard A. Matzner The University of Texas at Austin

Geoffrey Fox Scott Klasky NorthEast Parallel Architecture Center Syracuse University (subcontracted participation)

Project Description

Introduction:

The development of scientific and engineering computational models involves discretization of the differential equations, followed by evolution of the code and evaluation of results.

Each of these steps can involve very complicated procedures at the lowest, technical level. However, what the investigator wants to control is typically at a much higher, abstract level. For instance, repeated experiments may be run using different discretization prescriptions. The task of modifying such prescriptions at the level of manipulating matrices or loops is very tedious and error prone, and can be very profitably taken over by an automatic system driven by a high level language, enabling the scientist to concentrate on the fundamental features of the algorithm, rather than on the details of the algorithm. Similarly, study of graphical output is practically the only way to understand even one-dimensional situations and becomes essential in multi-dimensional simulations. Automatic, interactive and collaborative graphical presentations thus can dramatically improve the ease (and speed) with which computational methods are tried, analyzed, understood and, if necessary, modified.

In the current computational context, parallel approaches are required to achieve competitive performance. Thus, we require support for parallelization, for parallel I/O and for visualization of large parallel data sets, and we require large, parallel, linear solvers.

Precisely these same features are essential in the teaching of computational techniques to a new generation of scientists. It certainly is important that students understand discretization schemes at the lowest level, and they can be taught. But it is important to provide to the student rapid, reliable access to prototyping tools that can describe the fundamental features of the desired code without explicit low level rewriting, can handle parallelization and adaption, can efficiently run on today’s parallel machines, and can be viewed responsively, and typically in a collaborative setting. The integrated environment here will be called DCPL: Descriptor-driven Collaborative Prototyping and Learning. It will be demonstrated in computational science classes taught at The University of Texas, and at Syracuse University, and will include collaborative instruction, initially in a research environment, eventually in a classroom setting, between the Center for Relativity and The Department of Computer Science at The University of Texas, and at the NorthEast Parallel Architecture Center at Syracuse University. The remarkable point is that education and research have converged in this area. DCPL will simultaneously yield a very valuable tool for prototyping research and a valuable interactive colaborative learning tool.

The approach we propose here is to extend and integrate existing functional examples of these tools to parallel systems and to multi-dimensional problems, and existing examples of collaborative teaching methods, to the teaching of computational science for large systems on parallel machines.

The existing systems include:

RNPL (Rapid Prototyping Numerical Language), which supports high level description of discretization methods, and handles many “housekeeping” features of the coding, and can generate full update code if desired. [121]

DAGH (Distributed Adaptive Grid Hierarchy), which supports automatic parallelization, load balancing, and adaptivity. [5]

PLAPACK, a library supporting parallel solution of large linear systems and algebraic eigenvalue problems.[125]

SCIVIS, which is a collaborative visualization and data manipulation tool. [2]

TANGO, a powerful implementation of event sharing which supports general collaborative environments[9].

These tools will be developed and extended to handle development and analysis of large, parallel systems, and to provide responsive tools for direct and collaborative teaching of computational science concepts and techniques.

The instructional courses to be extended in this effort include computational courses PHY 329 and 381C, and a computational science course for advanced Relativity students (PHY 387N), which have all been taught at The University of Texas at Austin by Professor M. Choptuik; and the Syracuse University collaboration with Jackson State University (Jackson, Mississippi)[18], which was a “distant” course in computational methods taught from Syracuse to students at Jackson.

The integration of these components constitutes DCPL.

RNPL

The acronym RNPL stands for Rapid Numerical Prototyping Language[121]. It is a language for expressing time-dependent systems of partial differential equations and the information necessary for solving them using finite-difference techniques. It has advantages over traditional programming languages such as C and FORTRAN because it only requires the user to enter the essential structure of the program while it fills in the details [121].

RNPL can produce complete working programs, or a “skeleton” that the user can complete. The programs include facilities for reading parameters from a file, interactive control over output times and functions, memory management, and state dumping for calculation interruption and restart. The compilable code generated by RNPL is (at the user’s discretion) in C, C++, or FORTRAN.

Thus, RNPL provides the capability rapidly to generate C, C++, or FORTRAN code from high level specifications. The current implementation of RNPL introduces a number N of grid functions, ϕ^{A}[x^{μ}] A = 1 ⋯ N; μ = 1, μ = 1, 2, or μ = 1, 2, 3. on a Grid, G, labeled by i, j, k (or a superindex I, I = 1...(number of grid points)). The state of the system is then described by u^{ι}, ι = 1 ⋯ N×(number of grid points).

Notice that we consider the temporal integration separately. We discuss a finite-difference evolution of the temporal dependences. The finite representation of the system (finite difference, finite element ...) discretizes the system into a matrix acting on the state vector.

Existing RNPL implementation solves this system in the following way: The basic set of equations:

f_{ι}(u^{κ}) = 0

is iterated:

u_{i+1}^{κ} = u_{i}^{κ} − f_{i}(u_{i}^{κ})/ (\frac{∂f_{i}}{∂u_{i}^{κ}} )

This iterative update succeeds in many contexts, but in some contexts (particularly with strong inhomogeneities in the domain) may not converge. The solution is to supply a general linear solver for the problem.

Our approach is to use PLAPACK, which we will extend here to large sparse parallel systems.

PLAPACK

Coding parallel algorithms is generally regarded as a formidable task. To make this task manageable in the arena of linear algebra algorithms, the Parallel Linear Algebra Package (PLAPACK) [125] is an infrastructure for coding such algorithms at a high level of abstraction. It is often believed that by raising the level of abstraction in this fashion, performance is sacrificed. Indeed there is a performance penalty, but by coding at a higher level of abstraction, more sophisticated algorithms can be implemented, which allows high levels of performance to be regained. This has been shown to be the case for the parallel solver package implemented using PLAPACK, which includes Cholesky, LU, and QR factorization based solvers for symmetric positive definite, general, and overdetermined systems of equations, respectively. Performance comparisons with other such packages, in particular ScaLAPACK, shows there is no real performance penalty when coding at this high level of abstraction.

In a dissertation by Tim Collins (Ph.D. in CS, UT-Austin, 1995, co-supervised by J.C. Browne and R. van de Geijn), hierarchical specification of matrices was shown to be a highly effective way of storing and manipulating large sparse linear systems arising from regular and irregular meshes [124]. In that research, type information for submatrices in the hierarchy was also encoded and exploited, allowing for highly elegant and compact implementation of sparse iterative and direct linear solvers. In particular, type information allows a solver to take advantage of structure in subproblems. The hierarchical specification allows for pruning of the matrix where it has zero entries. In addition, it allows for natural detection of “supernodes” in sparse direct methods.

While PLAPACK was designed for dense linear systems, there are a number of reasons why PLAPACK is a natural candidate for integration with RNPL and DAGH, and systematic implementation of a hierarchical matrix infrastructure:

- The matrix distribution used by PLAPACK is physically based, by which we mean that the distribution of the matrix is induced by the distribution of the physical domain for which the linear system is to be solved.

- Such domains are frequently partitioned hierarchically, e.g. in nested dissection methods.

- It is uniquely appropriate for implementation of direct methods for solution of sparse linear systems since physically based matrix distribution implicitly specifies the distribution of dense interface matrices to distributed memory architectures.

- PLAPACK uses an object based programming paradigm, allowing hierarchical specification of matrices to be encoded using an elegant and simple interface.

- PLAPACK shares a common communication layer with DAGH, the Managed Message-Passing Infrastructure developed at UT-Austin by Carter Edwards [126].

- PLAPACK allows elegant and efficient implementation of the orthogonalization of vectors that define Krylov subspaces as occur in iterative solvers like conjugate gradient and GMRES.

DAGH

DAGH (which stands for Distributed Adaptive Grid Hierarchy) [5] was developed as a computational toolkit for the Binary Black Hole NSF Grand Challenge Project. It provides the framework to solve systems of partial differential equations using adaptive finite difference methods. The computations can be executed sequentially or in parallel according to the specification of the user. DAGH also provides a programming interface so that these computations can be performed by traditional Fortran 77 and Fortran 90 or C and C++ kernels. DAGH uses a paradigm based on space filling curves to distribute effort across parallel processors, and provides automatic load balancing. DAGH will be used to provide the parallelism and adaption for the applications described here.

SCIVIS

SCIVIS is a client-server data visualization and analysis system. SCIVIS enables the user to visualize various type of data(1d, 2d, 3d, and vector)[2].

One of the key SCIVIS features is called filters. Filters are user definable actions, performed on data set(s) to create new data based on this action. (For instance a filter may create a norm over all the values in a dataset, or a filter may take a derivative in space and/or time, of the original data, to create a new dataset.) The SCIVIS system supplies APIs to enable users to design their own filters, and Wizards to provide a graphical interface to simplify this procedure. Filters in Scivis can be created on-the-fly so that a user can immediately apply these new filters to her/his dataset. Since the SCIVIS system is collaborative, it is possible to create a powerful platform where many different users can can evaluate the performance of collaboratively developed filters.

SCIVIS uses a client-server model for data visualization. Users can send the data to the server anywhere the socket is supported so that the SCIVIS system can be used as a front end to other applications that originally produce the data set. The application producing a data set can write the output data to a socket, which is connected to the SCIVIS server. SCIVIS then allows the user to analyze and visualize the data. The system is flexible and very responsive. The system allows visualization rendering on remote fast servers, and only polygon lists are transported for the interactive visualization of 3D objects. SCIVIS also allows for transfer of filter algorithms, to allow local modification of visualization parameters; a fallback mode will ship the data, if users do not wish to transfer filters. Besides the straightforward data viewing mode just described, SCIVIS also provides a collaborative framework. Using this framework, users can exchange their data and their own personalized filters. Users of the system collaboratively are identified as Masters, or Slaves. A Master can modify data, a Slave can only view data. Multiple Masters are allow in a collaborative session.

SCIVIS currently achieves collaboration via its own collboration system, but under this project will switch to one which takes advantage of the TANGO system[9]. Using TANGO, SCIVIS will become part of a very powerful collaboration system which will allow users access to the wide range of tools already introduced into TANGO. For example, TANGO has features such as shared web-browsers, whiteboards, audio-visual communications, etc. TANGO has been incorporated with Web Wisdom[10]to create a new virtual University.[18]

TANGO

TANGOInteractive is a powerful implementation of event sharing for distributed shared objects which supports general collaborative environments. Its notable features include full integration with browsers and support of shared objects in essentially all forms with in particular Java, JavaScript, C++, VRML, Lisp and HTML being used existing applications. TANGO can be used over the Internet or, of course, internally to a group. It supports a suite of general and special purpose applications. TANGO will be used in this project in conjunction with SCIVIS. Firstly we will generate a shared RNPL application to allow collaboration in the problem specification stage. Secondly we can use TANGO to implement collaborative computing and visualization by sharing the invocation control screen, RNPL, the simulations themselves (generated code) and outputs (typically SCIVIS simulations).

TANGO implements what we loosely call the “MIMD SPMD” mode of collaboration. Each participant runs a separate application (separate instance of the distributed object). The TANGO core infrastructure (largely written in Java) on client and server ensures consistency by multicasting any change of state – represented by an “event” signifying this change. TANGO has a rich set of general tools – Whiteboard, Chatrooms, shared browsers and audio-video conferencing – but allows very general specialized shared objects. We have experience with a wide variety of objects including Java applets, C++ (for a custom 3D geographical information system), Lisp (emacs), VRML (3D visible human)[6] and JavaScript(web pages).

TANGO provides overall user and application linkage and control for these suite of shareable applications. Thus you choose TANGO if you need a rich set of subsidiary tools but if you just want shared visualization SCIVIS’s built in capabilities would be more appropriate.

DCPL Proposal:

Working collaboratively, and using the tools we are developing, Choptuik, Fox, van de Geijn, Matzner and Klasky will develop and extend the components of this effort into a unified coherent development and pedagogical tool for large scale scientific computational development and for collaborative education and collaborative computational simulation. The pedagogical approach will be to extend the Syracuse expertise with distant learning [18] to a more technical computational science orientation, like the computational science courses described above, taught at Texas.

Extensions include:

RNPL extension to include automatic solution of the generated equations by linearization and full solution of the equivalent linear-system (matrix) problem.

DAGH extension to inclusion of large linear system solvers such as PLAPACK, and PLAPACK extensions.

PLAPACK extensions to parallel algorithms for the solution of sparse systems of linear and nonlinear equations arising on structured and unstructured meshes, as well as for gridless methods, through extensions to PLAPACK that express sparse matrices as hierarchical matrices. This will include routines which recognize the sparsity structure of the matrices, and adapt the algorithm accordingly.

SCIVIS extension to large parallel dataset manipulation, and to user manipulation and visualization of extremely large parallel datasets.

TANGO integration into SCIVIS, to extend SCIVIS functionality.

Integration:

The components described above will be integrated into a coherent environment. RNPL will be extended to directly produce DAGH code, and will be modified to interface the sparse-solver development of PLAPACK. RNPL and DAGH will be extended to incorporate large parallel solvers through PLAPACK. SCIVIS extended with TANGO will provide the collaborative user interface element to the students or developers; we emphasize the collaborative class/professor, or multiuser, aspect of DCPL.

SCIVIS and TANGO will be integrated during the summer of 1998 and we only expect to need a modest amount of customization in this project. RNPL will be shared using TANGO’s native C interface. In TANGO you can choose to share events or leave them distinct. Here changes in the RNPL text will be shared but not say, moving the scroll bar. TANGO has a general but somewhat clumsy master-slave model built in and we will experiment with the various ways of sharing document control. Computational steering involves linking shared RNPL, visualization (SCIVIS), general documents (shared browser) with a special shared program invocation applet. The latter will be written in Java and provide an interface to the user allowing choice of execution mode, machines on which application is to run. Here sharing is implemented using TANGO’s Java (applet or application) interface. This collaborative computational steering version of TANGO can easily be integrated with the existing distance education uses (called WebWisdom) of TANGO. WebWisdom allows composite presentations built from sequences of objects which can include RNPL supplied simulations, HTML pages, PowerPoint foils etc.

We see that rather a modest effort is needed to link TANGO to our simulation tools but nevertheless we have gotten support for the different phases of research and computational science education. The major tasks are linking RNPL and the invocation applet to TANGO.

DCPL Applications:

The environment as conceived will have broad applicability in the development of simulation codea, and to the pedogogy of this art. The 1D description currently in RNPL will be extended to full 2- and 3- dimensional support. Applications currently include: One- and two- dimensional simulations of the behavior of matter in strong gravitational fields, and in particular the appearance of critical phenomena in gravitational collapse, and simulations of 3-dimensional strong-field gravitating systems (at Texas)[11, 12, 13, 14], and statistical physics and optimization and the solution of partial differential equations: computational fluid dynamics, and numerical relativity, at Syracuse [15]. These are areas whose instruction requires the high-end development support the DCPL can supply.

The topics described in this proposal address the KDI topics listed in the announcement:

• Learning and Intelligent Systems:

- To enhance the ability of students and researchers to learn and to create by developing a comprehensive set of learning and research tools, methods and technologies ...

- To further basic research designed to develop fundamental knowledge concerning the nature of learning and ... to apply such knowledge in a variety of situations such as education, learning technologies, ..., and networks of computer systems.

In particular the development of DCPL will focus on interactive and collaborative tools for pedagogic use by students, who will be enable to carry out rapid development and analysis of multi-dimensional structured adaptive partial differential equation codes. With the collaborative features of the SCIVIS plus TANGO structure coupled to the rapid prototyping offered by RNPL, and the ability to handle large and parallel problems as supported by the other components of the proposal, we have an ideal tool for teaching of computational science techniques. In addition, the high level abstractions used by PLAPACK make it possible for relative novices to the area of high performance parallel computing to develop and customize the solvers that operate under the covers. Thus, the tools form an “open environment” which allow students to quickly implement and test new approaches, and in turn contribute to the to be developed infrastructure. Experience in implementing DCPL will directly address questions of pedagogy and “distant” learning.

• Knowledge Networking:

- Focus on attaining new levels of knowledge integration, information flow, and interactivity among people, organizations, and communities.

- Enhance communication across disciplines, languages, and cultures.

- Improve the processing and integration of knowledge from different sources, domains, and non-text media types.

- Increase the effectiveness of teams, organizations, classrooms, or communities that work together across distances or over time.

- Deepen understanding of the ethical, legal, and social implications of new developments in connectivity.

In particular the development of DCPL will focus on interactive and collaborative tools which can access a very broad resource base for rapid development and analysis of multi-dimensional structured adaptive partial differential equation codes. This constitutes Knowledge Networking Foundational Research in:

- Computational aspects of distributed intelligence: dynamic task allocation, interaction, coordination, process and organization representation, collective learning, consistency management, protocol, negotiation.

- Managing heterogeneity and interoperability in dimensions such as syntax, semantics, scale, and structure.

- Large-scale remote data acquisition, distributed data analysis, experiment and sensor control, and simulation, especially interactive and real-time aspects.

- Distributed knowledge: sharable ontologies, processes for distributed classification and taxonomy, collaborative knowledge construction, representation and filtering tools, digital libraries and repositories across disciplines and application domains, and translation of representations.

• In The New Computational Challenges, these topics contribute to:

- Interplay Between Computations and Data.

Personnel:

Matzner is the PI for this project. Choptuik and van de Geijn are coPIs at Texas. Fox is the PI for the Syracuse subcontract effort. Klasky is a research scientist at The NorthEast Parallel Architecture Center at Syracuse. Each of the collaborators involved is expert in large scale computational problems, and has participated in teaching or distant teaching. Fox is the Director of The NorthEast Parallel Architecture Center and established the collaboration with Jackson State. Klasky participated in this collaboration, and is expert in collaborative visualization. van de Geijn has extensive teaching background, and is expert in large parallel linear solvers. Matzner is the Director of the Center for Relativity at The University of Texas. He has taught computational physics for advanced Relativity students, and leads the effort for the NSF Binary Black Hole Grand Challenge Alliance. Choptuik has taught undergraduate and graduate computational physics, and computational physics for advanced Relativity students, and is expert in adaptive schemes and visualiztion techniques.

Summary of Previous Results

Note: The Syracuse University “distant” learning project with Jackson State University was supported by the U.S. Army Corps of Engineers Waterways Experiment Station (CEWES) Major Shared Resource Center (MSRC) at Vicksburg, Mississippi under the DoD HPC Modernization Program, Programming Environment Training (PET). Program partners include the Information Technology Laboratory at WES and the Nichols Research Corporation[18].

0.1 Binary Black Holes: Coalescence and Gravitational Radiation, ASC/PHY 9318152 (ARPA Supplemented)

Matthew Choptuik, Geoffrey Fox, and Richard A. Matzner

The ASC/PHY 9318152 Grand Challenge Project was initiated in September 1993. Richard Matzner is the Principal Investigator and M. Choptuik is a co-Investigator on this grant. More than 100 publications have so far resulted from the Binary Black Hole Grand Challenge Alliance. (see: http://www.npac.syr.edu/projects/bh/) Three of the technical components to be extended here (RNPL, SCIVIS, and DAGH) were developed in the context of the Binary Black Hole Grand Challenge Alliance. Further the research of that Grand Challenge presented and presents a suite of pedagogical and research applications for the integrated environment proposed here.

The purpose of the Alliance is to compute the interaction of black holes and the gravitational radiation produced. The Alliance developed a parallel adaptive structure to take advantage of the fast, large computers being promised. Computer science structures, such as data structures definitions, and interface definitions, to direct the construction of the “toolbox” (which has become the “problem solving environment”) were immediately addressed. One feature was adaptive mesh refinement, which was immediately demonstrated in 1-d by Choptuik^{[16]}, and developed within the Alliance^{[17, 19]}.

Initial effort concentrated on High Performance Fortran, which is an extension of FORTRAN90^{[7]}. The Alliance began with a collection of legacy codes, and these codes were successfully expressed in HPF (High Performance Computing)^{[7]}. This work was carried out by computational scientists (especially Masso, Seidel , Cook, …) and computer scientists (especially Haupt, …). Further, the “toolkit” effort produced early results^{[20]}. However, we were aware of the need to accommodate parallel computing, and immediately undertook efforts to do so.^{[21]}. It became clear that the limitations of HPF inhibited easy implementation of adaptive parallel structures such as would become necessary in the Alliance codes. Thus, an effort was begun to develop DAGH (Distributed Adaptive Grid Hierarchy)[5] which was written in C and built on an underlying structure called SDDA (Symmetric Distributed Data Array).

In early 1996 the HPF efforts were concluded, and concentration centered exclusively on DAGH development. DAGH consists of a C++ driver which handles parallelization (it uses space-filling curves to convert from the conceptually 3-d computational space to a linear layout of processors). It also handles adaptive refinement, given routines to define an error measure and threshold^{[22, 23, 24, 25, 26, 27]}. It contains standard clustering routines, as well as injection and restriction routines, to communicate at the boundaries between different levels of refinement. In most applications as intricate as computational relativity, however, specially-tuned programs have to be supplied by the computational scientist. DAGH is written so that this C++ structure calls application science modules which can be written in C or in FORTRAN^{[5]}. In the Alliance, the practice has been to write these codes in FORTRAN90. Codes are typically written in a unigrid context by the developer, following certain rules: no global variables, array bounds passed in at call, etc., that guarantee parallelizability, and with a FORTRAN90 driver which calls the various science modules. We have written a script which reads the F90 driver and constructs a DAGH driver to run the program in parallel (adaptive refinement is being debugged). This means that we have a fast and efficient development process which can be translated immediately into production-style DAGH code for large-scale development or production runs. DAGH has been adopted into other research applications^{[28, 29]} and has been extended in other research directions^{[30]}. Relativity, i.e. applications-science use of the computational resources, began with the set of legacy codes referred to above. A period of testing and evaluation ensued. A number of systems were studied: spherical systems, typically with scalar radiation to provide a dynamical field;^{[32, 33, 34]} initial studies of axisymmetric vacuum collapse;^{[35]} and collapse to black holes with matter sources^{[36]}. Fully 3-dimensional data setting and initial computation was carried out by Matzner and Laguna in cosmology^{[37]} using an ADM (g-dot, K-dot) code developed by Kurki -Suonio, and a similar code was used at NCSA^{[119]}.Additionally, we had expertise on 2+1-d characteristic codes, which allow integration all the way to radiative infinity[38]. Work soon began on a 3-dimensional characteristic code. A number of technical approaches were studied to expand the computational science resources available to the Alliance^{[39]}. Some of these took the form of internal reports^{[41, 42, 43]}.

Validation of codes proceeded in the 1-d case in work by Evans and Coleman^{[44]}, who studied gravitational collapse of a radiation fluid, and found critical phenomena related to the Choptuik^{[45]} effect. Development proceeded on broad paths with a number of test and example cases used to develop technique for the Einstein equations and for the important problem of radiation extraction^{[111, 46]}. Critical Phenomena remain a topic of current interest, and code development, especially in the spherical case, has continued to touch on this problem^{[47, 48, 49, 50]}.

There are a number of ways that data can be set for multiple black hole configurations. Cook et al^{[51]} had, prior to the initiation of the Alliance, shown computationally convergent methods of preparing data, based on the “classic” approach of using the York technique on conformally flat backgrounds. Cook extended this to a study of quasi-circular black hole orbits^{[52]}.

Early 2-dimensional black hole collision simulations were done using maximal lapse (a singularity-avoiding coordinate system)^{[53]}. A number of these studies were carried out, and laid the groundwork for the considerably more demanding 3-d simulations: These included studies of distorted and rotating black holes,^{[54, 55, 56, 68]} both vacuum and from collapse ^{[111]}, and a thorough development of the dynamics of the collision^{[57, 58, 59]}. These studies (based also on previous work by Shapiro and Teukolsky^{[36]}) culminated in a thorough description of the surface of merging black holes, explicating many previously unclear aspects of the process^{[60]}. A fuller exposition subsequently was given in^{[61, 62, 63]}.

An important aspect of computational physics is to compare with other (perhaps approximate) methods^{[116, 97, 96, 99, 98]}. Perturbation theory of distorted black holes surely describes the late evolution of a black hole merger. A number of studies have been carried out predicting radiation in situations that can be treated by close (standard perturbative) or other approximate methods. For axisymmetric problems, these results are in often surprising agreement with computation^{[64, 65, 66, 67, 69]}. See also work on perturbative fields on fixed backgrounds^{[98]}. Three-dimensional black hole work has progressed with maximal slicing in 3-d^{[40, 110]}. However, it became clear that an Eddington-Finkelstein adapted coordinate system is preferable because the representation of a single black hole is static in that case.

At present we have succeeded in long-term single black hole evolution for both nonrotating (Schwarschild) and rotating (Kerr) black holes. By imposing blending boundary conditions to analytically known solutions, we can in some situations run the code forever. Norms of changes of field variables across the grid decrease to, and remain at, machine round-off levels[31]. We are investigating the range of parameters that allows this result. We have also demonstrated a black hole moving across the grid for periods up to 60M^{[70]}, and shorter times for moving spinning black holes [31]. Further, we have been able to demonstrate brief evolutions of interacting spinning black holes moving through the computational grid [31]. Apparent horizon “locking” is necessary for better performance. This means that we will actively track the apparent horizon (an estimate of the location of the black hole surface) and fix coordinates to it. We have developed three separate approaches: expansion in spherical harmonics;^{[71, 72, 73, 74, 75]} direct solution of the apparent horizon elliptic equation,^{[76]} and curvature flow methods^{[77]} to the tracking problem, and we are enabling horizon tracking for new runs.

Essential to simulations of gravitational waveforms is the ability to extract waves at infinity. We have developed a method based on matching to a perturbative outer module,^{[69, 78, 79]} and a matching to characteristic evolution^{[80, 81, 82, 83, 85, 86, 87]}. Various technical aspects of the matching approaches require computation or integration on the matching sphere, and these have been developed^{[88, 89, 90]}.

A substantial effort was made to rewrite the Einstein system in a way that more closely presented its hyperbolic nature. This work proceeded on two fronts. A scheme which is based on the Arnowitt-Deser-Misner formalism, but which introduces additional spatial variables, was introduced by Bona and Masso,^{[91]} and developed substantially^{[92],[93, 94]}. A new formulation, which deals with one higher time derivative of the metric, and demonstrated explicit hyperbolicity, was also developed^{[8, 95, 78, 100, 101, 102]}. This latter formalism has had significant impact outside relativity, in more general field theory.

A number of more or less general reports have been given describing the Binary Black Hole Grand Challenge Alliance^{[103, 104, 105, 106, 107, 108, 109, 40]} and other work supported/stimulated by the Alliance^{[39]}.

Cray Research used figures from Grand Challenge Alliance research on the cover of its 1997 University Research and Development Grant Report.

Human Resource Development

Our group has a large and growing number of graduate students who share our enthusiasm regarding the future of computational science. These students receive an outstanding grounding in computational physics, numerical analysis and systems-development skills, and a continued high level of graduate training is a primary goal of our overall research program. They contribute substantially to the research program.

A very large number of students and postdocs were involved in the Binary Black Hole Grand Challenge. Those from Texas supported by the Alliance or by other NSF funding to Matzner and Choptuik were:

Matthew Choptuik (postdoc, now Associate professor of Physics), Robert Marsa (PhD 1995, now a post-doctoral fellow in the Center), Dale Choi (PhD expected 1997), Steven Liebling (PhD expected 1997), Randall Correll (PhD expected in 1999), Mark Dubal (postdoc), Tim Galavan (graduate student), Reid Guenther (PhD 1995), Eric Hirschman (postdoc), Paulo Holvorcem (postdoc), Mijan Huq (PhD 1996, now a postdoc in the Center), Scott Klasky (PhD 1994, now a postdoc at Syracuse), John LaChapelle (postdoc), Juan Lara (graduate student), Manish Parashar (postdoc), Premana Premadi (PhD 1996), Jonathan Thornburg (postdoc), Robin Tuluie (PhD 1993), David Neilsen (graduate student), Scott Hawley (graduate student), Chun-Yen Wang (graduate student), Carmen Molina-Paris (graduate student), Jodie Martin (undergraduate student), Mike Hicks (undergraduate student), Johnathan Thornburg (postdoc).

0.2 Application of High Performance Computing to Micromechanical Characteristics of Composite Materials

Robert van de Geijn

Grant: CMS-9522964

Principal Investigators: Greg Rodin (PI), J.C. Browne (Co-PI), J. Tinsley Oden (Co-PI), Robert van de Geijn (Co-PI)

Period: April 1, 1995 - March 31, 1998

Amount: $1,200,000

This grant has supported four Ph.D. students (one has completed his Ph.D., one will defend in August 1998, and two will finish within the next two years), one MS student, and three post-doctoral students. In addition, the project supported a visiting scientist from the People’s Republic of China.

The principal results obtained during the project are as follows:

Fast Boundary Element Methods: We have developed FLEMS, a 3-D boundary element code for rapid solution of many-particle problems in linear elasticity.[127, 128] This code allows the integration of any boundary element method with any iterative strategy that includes a fast summation method. The present version includes the standard collocation boundary element method and a GMRES solver in which matrix-vector multiplication is performed with the fast multipole method. FLEMS is the first code of its kind for solving multiscale materials problems.

Fast Dislocation Dynamics Methods: Following theoretical ideas developed in connection with FLEMS, we have developed a similar approach and code for dislocation dynamics simulations.[129, 128] This code is being adapted by researchers at LLNL, ALCOA and in France.

Modeling Error Estimates: We have introduced and analyzed the concept of modeling errors. These errors are associated with replacing a fine-scale model with a coarse-scale model. Clearly this displacement procedure is central to multiscale problems. Main results have been published by Zohdi et al. [130] and Oden and Zohdi [131].

Domain Decomposition Methods: We have developed two complementary domain decomposition methods for multiscale problems. The first method [130, 131] is based on hierarchical partitioning of the domain. The second [132] allows one to represent complex microstructures as a combination of problems that involve individual microstructural features whose interactions are computed using a structured mesh.

Plans for Dissemination of results, and Institutional committment to Space and Equipment:

The results of these developments will be disseminated in refereed technical journals and conference proceedings, and in addition our success at teaching, and interactive/collaborative teaching, will be documented in broader journals of interest to the educational community. We will also maintain an open WEB site documenting the progress of these efforts.

The computational equipment, and space resources available to this effort are documented in the NSF Facilities, Equipment And Other Resources Form. It is repeated here:

Computer Resources: This is a proposal for computational research. The Center for Relativity is equipped with medium- and high-end graphics workstations, which however are becoming obsolescent. This equipment has been, and will continue to be, absolutely vital to the success of our research. Our current facilities include four Silicon Graphics (SGI) R10000 Impact machines with a total of nearly 1.5 Gbyte main memory and 32 Gbyte of disk storage, as well as two older SGI Crimson R4000 VGXT machines. The six R10000/Crimson machines provide platforms for scientific visualization, code development, and medium-scale production runs for the PIs, our postdocs, and (at most) two graduate students. We also have two entry-level SGI Indigo and two SGI Indy machines which are used heavily by graduate students, but which are obsolescent and need to be replaced. We have very good access to campus networks, and adequate access to national networks and national supercomputer centers. We have space available in the Center for Relativity and in the Computer Science Department for the anticipated researchers; with the new computer support requested in this proposal, we will be able adequately to handle the computational demand of this research. We also have access to The NSF Centers (NPACI and NCSA), and are frequent users of those machines. The Computer Science Department has adequate computer resources and available space to support this proposed effort. NPAC at Syracuse has adequate computer resources to support the effort at Syracuse.

Office Space: The Center for Relativity and the Department of Computer Sciences have adequate office space to house this project at the University of Texas. NPAC at Syracuse has adequate office space to house the effort at Syracuse.

Performance Goals:

• Year 1:

- Demonstration of heierarchical decomposition of sparse matrices and linear system solution via PLAPACK

- DAGH code output (parallel adaptive) via RNPL specifications and compilation.

- SCIVIS extension to TANGO collaboration suite.

• Year 2: - SCIVIS/TANGO demonstration with large scale parallel-produced datasets

- Scientific computation instruction based on RNPL, with SCIVIS/TANGO collaborative visualiza-

tion.

• Year 3:

- Very large scale scientific computations via RNPL/DAGH, with integrated PLAPACK solution and SCIVIS/TANGO visualization

- Collaborative teaching (graduate level computational science) via SCIVIS/TANGO between Syracuse University and The University of Texas at Austin

Management Plan:

Richard Matzner is the Lead PI, responsible for maintaining communication and collaboration. This will be accomplished through biweekly conference calls, and by yearly meetings of the collaborators (including the NorthEast Parallel Architecture Center, which participates in this research via subcontract). The meetings will serve to promulgate results and will present opportunities to plan research efforts for the subsequent year. They will also provide input for the required annual report to the National Science Foundation, and new results obtained will also be prepared for publication at these meetings. A similar structure is in place for the Binary Black Hole Grand Challenge Alliance, and proves very effective.

References

[1] http://www.npac.syr.edu/projects/bh/ Click on “New Developments”. Multiple interacting black holes are an active research project, and funding for the continuation of this work is requested under this proposal. Results will be posted to this web site as they are developed.

[2] http://kopernik.npac.syr.edu:8888/scivis/

[3] http://godel.ph.utexas.edu/)(link GC Toolkit).

[4] B. Ki, S. Klasky, “Collaborative Scientific Visualization” Concurrency: Practice and Experience, (Nov, 1997).

[5] http://www.ticam.utexas.edu/parashar/public html /DAGH/ http://www.npac.syr.edu/projects/bbh/DAGH/ M. Parashar and J.C. Browne, “System Engineering for High Performance Computing Software: The HDDA/DAGH Infrastructure for Implementation of Parallel Structured Adaptive Mesh Refinement,” to be published in the Structured Adaptive Mesh Refinement Grid Methods, IMA Volumes in Mathematics and its Applications, Springer-Verlag. M. Parashar and J.C. Browne,“Systems Engineering Issues in the Implementation of an Infrastructure for Parallel Structure Adaptive Meshes,” Invited paper, Workshop of Structured Adaptive Mesh Refinement Grid Methods, SIAM Conference on Parallel Processing for Scientific Computing, March, 1997. M. Parashar and J.C. Browne,“Object-Oriented Programming Abstractions for Parallel Adaptive Mesh-Refinement,” Parallel Object-Oriented Methods and Applications (POOMA), February, 1996. M. Parashar and J.C. Browne, “On Partitioning Dynamic Adaptive Grid Hierarchies,” Proceedings of the 29^{th} Annual Hawaii International Conference on System Sciences, January,1996. M. Parashar and J.C. Browne,“Distributed Dynamic Data-Structures for Parallel Adaptive Mesh-Refinement,” Proceedings of the International Conference for High Performance Computing, December,1995.

[6] http://www.npac.syr.edu/projects/3Dvisiblehuman/VRML/VRML2.0/MEDVIS/

[7] http://www.npac.syr.edu/ T. Haupt, ”Fortran 90 Implementation of the Berger-Oliger Algorithm for Adaptive Mesh Refinement,” Status Report-02. N. Chrisochoides, G. Fox, T. Haupt, ”A Computational Toolkit for Colliding Black Holes and CFD,” SCCS-626, in proceedings of AAIA Conference, (June, 1994). T. Haupt, M. Choptuik, “Definition of Fortran90 data structures and an example program that uses them.” T. Haupt, “Fortran 90 Implementation of the Adaptive Mesh Refinement Algorithm,” http://www.npac.syr.edu/project/bbh/AMR/AMR-02.ps M. Miller, T. Haupt,“Gravitational Wave Extraction - A Benchmark?” SCCS-681.

[8] Y.Choquet-Bruhat and J.W. York, “Geometrical Well Posed Systems for the Einstein Equations,” C.R. Acad. Sci. Paris, 321 1089 (1995).

[9] http://www.npac.syr.edu/tango

[10] http://www.webwisdom.org/papers/sc97/webwisdom3.html

[11] http://godel.ph.utexas.edu/Members/matt/Teaching/97Spring/Phy381C/Syllabus.html

[12] http://godel.ph.utexas.edu/Members/matt/Teaching/98Fall/Phy329/Syllabus.html

[13] http://godel.ph.utexas.edu/Members/matt/Teaching/98Spring/Phy387N/Syllabus.html

[14] http://godel.ph.utexas.edu/Members/richard/class/phy387n.html

[15] http://www.npac.syr.edu/users/gcf/topicareas/cps713-96Page.html

[16] “An Implementation of the Berger-Oliger Mesh Refinement Algorithm for the Wave Equation in Spherical Symmetry,” Matthew W. Choptuik, technical report (March 1994).

[17] “Adaptive Mesh Refinement in Numerical Relativity,” J. Masso, E. Seidel, and P. Walker, in General Relativity (MG7 proceedings), R. Ruffini and M. Keiser (eds.), World Scientific (1995).

[18] http://www.npac.syr.edu/users/trscavo/jsufall97/

[19] “Fortran 90 Implementation of the Berger-Oliger Algorithm for Adaptive Mesh Refinement,” Tomasz Haupt (1995).

[20] “A Computational Toolkit for Colliding Black Holes and CFD,” N.P. Chrisochoides, G.C. Fox, and T. Haupt (1994).

[21] “Multithread model for dynamic load balancing parallel adaptive PDE computations,” Nikos Chrisochoides, to appear in Applied Numerical Mathematics Journal (1995).

[22] “Distributed Dynamic Data-Structures for Parallel Adaptive Mesh-Refinement,” M. Parashar and J.C. Browne, in Proceedings of the International Conference for High Performance Computing (December 1995).

[23] “Object-Oriented Programming Abstractions for Parallel Adaptive Mesh-Refinement,” M. Parashar and J.C. Browne, in Parallel Object-Oriented Methods and Applications (POOMA) (February 1996).

[24] “On Partitioning Dynamic Adaptive Grid Hierarchies,” M. Parashar and J.C. Browne, in Proceedings of the 29th Annual Hawaii International Conference on System Sciences (January 1996) (IEEE).

[25] “System Engineering for High Performance Computing Software: The HDDA/DAGH Infrastructure for Implementation of Parallel Structured Adaptive Mesh Refinement,” M. Parashar and J.C. Browne, to be published in the Structured Adaptive Mesh Refinement Grid Methods, IMA Volumes in Mathematics and its Applications, Springer-Verlag.

[26] “Systems Engineering Issues in the Implementation of an Infrastructure for Parallel Structured Adaptive Meshes,” M. Parashar and J.C. Browne, invited paper, Workshop in Structured Adaptive Mesh Refinement Grid Methods, SIAM Conference on Parallel Processing for Scientific Computing (March 1997).

[27] “A Common Data Management Infrastructure for Parallel Adaptive Algorithms for PDE Solutions,” M. Parashar, J.C. Browne, C. Edwards, and K. Klimkowski, accepted for presentation at Supercomputing 97 (November 1997).

[28] “A New Generation EOS Compositional Reservoir Simulator: Formulation and Discretization,” P. Wang, I. Yotov, M. Wheeler, T. Arbogast, C. Dawson, M. Parashar, and K. Sepehrnoori, in Proceedings of the Society of Petroleum Engineers, Reservoir Simulation Symposium (June 1997).

[29] “A New Generation EOS Compositional Reservoir Simulator: Framework and Multiprocessing,” M. Parashar, J.A. Wheeler, G. Pope, K. Wang, and P. Wang, in Proceedings of the Society of Petroleum Engineers, Reservoir Simulation Symposium (June 1997).

[30] “Integrated Data-Management for Computational Steering,” M. Parashar and J.C. Browne, submitted for publication to the 31st Annual Hawaii International Conference on System Sciences (January 1998).

[31] “Computational Evolution of Binary Black Hole Spacetimes” R. Correll, PhD dissertation, The university of Texas at Austin (1998)

[32] R.L. Marsa and M.W. Choptuik, “Black Hole-Scalar Field Interactions in Spherical Symmetry,” Physical Review D, 54 4929-4943 (1996)

[33] “Collapse to Black Holes in Brans-Dicke Theory: I. Horizon Boundary Conditions for Dynamical Spacetimes,” Mark A. Scheel, Stuart L. Shapiro, and Saul A. Teukolsky, Physical Review D51 4208 (April 1995).

[34] “Collapse to Black Holes in Brans-Dicke Theory: II. Comparison with General Relativity,” Mark A. Scheel, Stuart L. Shapiro, and Saul A. Teukolsky, Physical Review D51Physical Review D51 4236 (April 1995).

[35] A.M. Abrahams and C.R. Evans,“Universality in Axisymmetric Vacuum Collapse”, Physical Review D51 3998-4003 (1994)

[36] S.L. Shapiro and S. Teukolsky, Physical Review 45 2739 (1992).

[37] H. Kurki-Suonio, P. Laguna and Richard A. Matzner, “Inhomogeneous Inflation: Numerical Evolution”, Physical Review D47 3611 (1993).

[38] “Null Cone Evolution of Axisymmetric Vacuum Spacetimes,” R. Gomez, P. Papadopoulos, and J. Winicour, J. Math. Phys. 35 4184 (1994).

[39] P. Laguna,“Alternatives to Finite Difference Methods in Numerical Relativity,” in Relativity and Scientific Computing, eds. F.W. Hehl, R.A. Puntigam, and H. Ruder (Springer/Verlag Berlin, 1996).

[40] “3-D Numerical Relativity at NCSA,” P. Anninos, K. Camarda, J. Masso, E. Seidel, W-M Suen, M. Tobias, and J. Towns, to appear in General Relativity (MG7 proceedings), eds. R. Ruffini and M. Keiser, World Scientific (1995).

[41] “Steps in the construction of an extraction module,” Nigel T. Bishop, Roberto Gomez, Philippos Papadopoulos, and Jeffrey Winicour, Pitt-Penn State-UniSA BBH Report (1996).

[42] “Stereographic Coordinate Patches,” R. Gomez, P. Papadopoulos, and J. Winicour, BBH working paper – program listing also available (1997).

[43] “Computational application of the eth formalism,” R. Gomez, P. Papadopoulos, and J. Winicour, in preparation (1997).

[44] “Observation of Critical Phenomena and Self-Similarity in the Gravitational Collapse of Radiation Fluid,” C.R. Evans and J.S. Coleman, in Phys. Rev. Lett. 72, 1782 (1994).

[45] Matthew W. Choptuik, “Universality and Scaling in Gravitational Collapse of a Massless Scalar Field,” Physical Review Letters 70 9-12 (1993).

[46] “Calculation of Gravitational Wave Forms From Black Hole Collisions and Disk Collapse: Applying Perturbation Theory to Numerical Spacetimes,” Andrew M. Abrahams, Stuart L. Shapiro, and Saul Teukolsky, Physical Review D51 4295 (April 15, 1995).

[47] “Critical Behaviour in Scalar Field Collapse,” Matthew W. Choptuik, in Deterministic Chaos in General Relativity, eds. D. Hobill et al, Plenum Press, New York (January 1994).

[48] “Critical Phenomena in Gravitational Collapse,” Matthew W. Choptuik, to appear in Proc. XI Congress Mathematical Physics, D. Iagolnitzer (ed.) (1995).

[49] “Black Hole-Scalar Field Interactions in Spherical Symmetry,” Robert L. Marsa and Matthew W. Choptuik, gr-qc/9607034 (1996).

[50] “Critical Behaviour in Gravitational Collapse of a Yang-Mills Field,” Matthew W. Choptuik, Tadeusz Chmaj, and Piotr Bizon, gr-qc/9603051 (1996).

[51] G.B. Cook, M. W. Choptuik, M. R. Dubal, S. Klasky, Richard A. Matzner and S.R. Oiveira, “Three-Dimensional Initial Data for the Collision of Two Black Holes,” Phys.Rev. D47 1471 (Feb.1993).

[52] “Three-dimensional initial data for the collision of two black holes II: Quasi-circular orbits for equalmass black holes,” Gregory B. Cook (submitted for publication).

[53] “Singularity Avoidance in Numerical Black Hole Spacetimes,” Peter Anninos, Greg Daues, Joan Masso, Edward Seidel, Wai-Mo Suen, General Relativity (MG7 Proceedings) Ruffini and Keiser (eds.), World Scientific (1995).

[54] “The Evolution of Distorted Rotating Black Holes I: Methods and Tests,” Steven R. Brandt and Edward Seidel, Physical Review D52 856 (July 15, 1995).

[55] “The Evolution of Distorted Rotating Black Holes II: Dynamics and Analysis,” Steven R. Brandt and Edward Seidel, Physical Review D52 856 (July 15, 1995).

[56] “Rotating Black Hole Spacetimes,” S. Brandt and E. Seidel, to appear in General Relativity (MG7 Proceedings), R. Ruffini and M. Keiser (eds.), World Scientific (1995).

[57] “The collision of Two Black Holes,” Peter Anninos, David Hobill, Edward Seidel, Larry Smarr, and Wai-Mo Suen, Physical Review Letters 71 2851 (1993).

[58] “The Head-On Collision of Two Equal Mass Black Holes,” Peter Anninos, David Hobill, Edward Seidel, Larry Smarr, and Wai-Mo Suen, D52 2044 (1995).

[59] “The Head-On Collision of Two Equal Mass Black Holes: Numerical Methods,” Peter Anninos, David Hobill, Edward Seidel, Larry Smarr, and Wai-Mo Suen, NCSA Technical Report 24 (1994).

[60] “Geometry of a Black Hole Collision,” Richard A. Matzner, H.E. Seidel, S.L. Shapiro, L. Smarr, W-M Suen, Saul A. Teukolsky, and J. Winicour, Science 270 941 (1995) (cover article).

[61] “Numerical Relativity and Black Hole Horizons,” Joan Masso, in Inhomogeneous Models and other topics (ERE94), A. Molina and J.M. Senovilla (eds.), World Scientific (1995).

[62] “Event Horizons of Numerical Black Holes,” P. Anninos, D. Bernstein, S. Brandt, J. Libson, J. Masso, E. Seidel, L. Smarr, W-M Suen, and P. Walker, to appear in General Relativity (MG7 proceedings), R. Ruffini and M. Keiser (eds.), World Scientific (1995).

[63] “Event Horizons in Numerical Relativity: Methods and Tests,” J. Libson, J. Masso, E. Seidel, W-M Suen, and P. Walker, Physical Review D53 4335-4350 (1996).

[64] “Collisions of Boosted Black Holes: Perturbation Theory Prediction of Gravitational Radiation,” Andrew M. Abrahams and Gregory B. Cook, Physical Review D50 R2364 (August 15, 1994).

[65] “Black-hole collisions from Brill-Lindquist initial data: Predictions of perturbation theory,”, A. Abrahams, R.H. Price, Physical Review D53-4 1972 (1996).

[66] “Analysis of ‘Gauge Modes’ in Linearized Relativity,” Richard A. Matzner, Mijan Huq, Alonso Botero, Dae Il Choi, Ullar Kask, Juan Lara, Steven Liebling, David Neilsen, Premana Premadi, and Deirdre Shoemaker, Classical and Quantum Gravity 14 L21 (1997).

[67] “Head-On Collision of Two Black Holes: Comparison of Different Approaches,” P. Anninos, R. Price, J. Pullin, E. Seidel, and W-M Suen (June 1995).

[68] E. Seidel, ”New developments in Numerical Relativity,” in Helvetica Physica Acta, to apppear, (1996).

[69] “Applying black hole perturbation theory to numerically generated space-times,” A. Abrahams, Physical Review D53-4 1963 (1996).

[70] “Boosted Black Hole Evolutions with Singularity Excision,” The Binary Black Hole Grand Challenge Alliance, Phys. Rev. Lett. (submitted 1997).

[71] “Dynamics of Apparent and Event Horizons,” Peter Anninos, David Bernstein, Steven Brandt, Joseph Libson, Joan Masso, Edward Seidel, Larry Smarr, Wai-Mo Suen, and Paul Walker, Physical Review Letters 74 630 (January 1995).

[72] “Horizon Boundary Condition for Black Hole Spacetimes,” Peter Anninos, Greg Daues, Joan Masso, Edward Seidel, and Wai-Mo Suen, Physical Review D51 5562 (May 15, 1995).

[73] “Finding Apparent Horizons in Dynamic 3D Numerical Spacetimes,” submitted to Physical Review D (1996).

[74] “A 3-D Apparent Horizon Finder,” J. Libson, J. Masso, E. Seidel, and W-M Suen, in General Relativity (MG7 proceedings), R. Ruffini and M. Keiser (eds.), World Scientific (1995).

[75] “Implementing an apparent-horizon finder in three dimensions,” T.W. Baumgarte, G.B. Cook, M.A. Scheel, S.L. Shapiro, S.A. Teukolsky, gr-qc/9606010 (June 6, 1996).

[76] “Apparent Horizon Location in Numerical Spacetimes,” Mijan Huq, PhD dissertation, University of Texas at Austin (1996).

[77] “Curvature Flow Methods and Apparent Horizons”, Deirdre Shoemaker, Mijan F. Huq, and Richard A. Matzner, in preparation (1997).

[78] “Gravitational waveform extraction and outer boundary conditions for hyperbolic numerical relativity simulations,” A. Abrahams, A. Anderson, and C.R. Evans, Preprint (June 28, 1996).

[79] “Schwarzschild-perturbative gravitational wave extraction and outer boundary conditions,” The Binary Black Hole Grand Challenge Alliance, submitted to Physical Review Letters (1997).

[80] “Cauchy-Characteristic evolution of scalar waves in curved spacetime. I. Static, spherically symmetric spacetimes,” P. Papadopoulos, P. Laguna (1995).

[81] “Pittsburgh Group Code: Gravitational Wave Extraction – A Benchmark” (evolution of scalar fields from characteristic data,” Tomasz Haupt and Mark Miller (October 1994).l

[82] “Cauchy-characteristic Evolution of Einstein-Klein-Gordon Systems,” R. Gomez, P. Laguna, P. Papadopoulos, J. Winicour.

[83] “Cauchy-characteristic matching: A new approach to radiation boundary conditions,” Nigel T. Bishop, Roberto Gomez, Paulo R. Holvorcem, Richard A. Matzner, Philippos Papadopoulos, and Jeffrey Winicour, Physical Review Letters 76 4303 (1996).

[84] R. Gómez, R. Marsa and J. Winicour, “Black hole excision with matching”, Phys. Rev. D 56, (Nov. 1997), gr-qc/9708002.

[85] “Cauchy-Characteristic Evolution and Waveforms,” N.T. Bishop, R. Gomez, P.R. Holvorcem, R.A. Matzner, P. Papadopoulos, J. Winicour, J. Comp. Phys. 136 140 (1997).

[86] Nigel T. Bishop,Roberto Gomez,Luis Lehner, Jeffrey Winicour, “ Cauchy-characteristic extraction in numerical relativity,” to appear in Phys. Rev. D (1997).

[87] “Cauchy-characteristic evolution of Einstein-Klein-Gordon Systems,” Roberto Gomez, Pablo Laguna, Philippos Papadopoulos, and Jeffrey Winicour, to appear in Physical Review D.

[88] “Finite Differencing on the Sphere,” R. Gomez, P. Papadopoulos, and J. Winicour, Proceedings of the Seventh Marcel Grossman meeting (1995).

[89] “Computational Application of the eth formalism,” Roberto Gomez, Philip Papadoupolos, J. Winicour, to appear in Proceedings of the VII Marcel Grossman meeting, R. Ruffini and M. Reiser (eds.), World Scientific (1995).

[90] “Gravitational Instability of a Kink,” Williams Barreto, Roberto Gomez, Luis Lehner, and Jeffrey Winicour, to appear in Physical Review D (1998).

[91] C.Bona and J. Masso, Phys. Rev. Lett. 68 1097 (1992).

[92] “A Class of Hyperbolic Gauge Conditions,” C. Bona, J. Stela, J. Masso, and E. Seidel, in General Relativity (MG7 proceedings), R. Ruffini and M. Keiser (eds.), World Scientific (1995).

[93] “New Formalism for Numerical Relativity,” Carles Bona, Joan Masso, Edward Seidel, and Joan Stela, Physical Review Letters 75 600 (July 1995).

[94] “Invariant Algebraic Slicing of the Spacetime,” C. Bona, J. Stela, J. Masso, and E. Seidel, in Inhomogeneous Models and other topics (ERE94), A. Molina and J.M. Senovilla (eds.), World Scientific (1995).

[95] “Einstein and Yang-Mills theories in hyperbolic form without gauge-fixing,” A. Abrahams, A. Anderson, Y. Choquet-Bruhat, and J.W. York Phys. Rev. Lett. 75 3377 (1995).

[96] “Dynamics of perturbations of rotating black holes”, w. Krivan, P. Laguna, P. Papadopoulos, and Nils Andersson, Phys. Rev. D56, 3395 (1997)

[97] P.Brady, C. Chambers, W. Krivan and P. Laguna, ‘Telling Tails in the Presence of a Cosmological Constant,” submitted to Phys. Rev. D (1996).

[98] W. Krivan, P. Laguna and P. Papadopoulos, ‘Dynamics of Scalar Fields in the Background of Rotating Black Holes,” Phys. Rev.D56 (Sept.1997).

[99] W. Krivan, P. Laguna and P. Papadopoulos, “Dynamics of Spin-2 Fields in Kerr Backgroundgeometries,” to appear Proceedings Texas Symposium for Relativistic Astrophysics (1997).

[100] “Geometrical Hyperbolic Systems for General Relativity and Gauge Theories,” A. Abrahams, A. Anderson, Y. Choquet-Bruhat, and J. York, Jr. submitted to Classical and Quantum Gravity (1995).

[101] “A non-strictly hyperbolic system for the Einstein equations with arbitrary lapse and shift,” A. Abrahams, A. Anderson, Y. Choquet-Bruhat, and J. York, Jr., gr-qc/9607006 (1996).

[102] “3+1 general relativity in hyperbolic form,” A. Abrahams, J.W. York, Jr., paper to appear in Proceedings of Les Houches conference (1995).

[103] “Computing Gravitational Radiation from the Collision of Black Holes: Status Report,” Richard Matzner in Phenomenology of Unification from Present to Future, G. Diambrini-Palazzi et al (eds.), World Scientific (1994).

[104] “Solving Einstein’s Equations on Supercomputers,” Edward Seidel (1994).

[105] “Numerical Relativity,” E. Seidel, in proceedings of ICGC 95, Kluwer Press, to appear (1995).

[106] ”New Developments in Numerical Relativity,” E. Seidel, in Helvetica Physica Acta, to appear (1996).

[107] “A Numerical Approach to Binary Black Hole Coalescence,” L.S. Finn, to appear in proceedings of the GR14 conference, gr-qc/9603004 (1996).

[108] “Calculating Gravitational Waveforms – By Any Means Necessary!,” S.L. Shapiro, invited talk to appear in Proceedings of International Conference on Gravitational Waves: Sources and Detectors, Cascina (Pisa), Italy (March 19-23, 1996).

[109] “Black Hole Collisions: A Computational Grand Challenge,” P. Laguna, in Gravitational Waves: Sources and Detectors, eds. I. Ciufolini and Francesco Fidecaro, World Scientific-Singapore (1997).

[110] P. Anninos, J. Baker, S. Brandt, Hans-P. Nollert,R. Price,J. Pullin, and E. Seidel, ”The head-on collision of close counter-rotating black holes,” submitted to Phys. Rev. D (1996).

[111] A.M. Abrahams, S.L. Shapiro and S. A. Teukolsky, “Disk Collapse in General Relativity,” Physical Review D50 7282 (Dec.1994).

[112] J. Bowen and J.W. York Jr., “Two Black Holes with Axisymmetric parallel spins: Initial data,” Class. Quantum Grav., 1,591-610, (1984).

[113] G.B. Cook, M.W. Choptuik, M. Dubal, S. Klasky, R. Matzner and S.R. Oliveira, Phys. Rev. D, 1471-1490 (1993).

[114] Steven Brandt and Bernd Brügmann, ” A simple construction of initial data for multiple black holes,” Phys.Rev.Lett., 78 3606-3609 (1997). (http://xxx.lanl.gov/find/gr-qc/9703066).

[115] G. Daues, Ph.D. Dissertation, Washington University, (1996).

[116] “Testing a Simplified Version of Einstein’s Equations for Numerical Relativity,” G.B. Cook, S.L. Shapiro and S.A. Teukolsky, Preprint. (1995)

[117] N. T. Bishop, R. Gómez, L. Lehner, M. Maharaj and J. Winicour, “High-powered Gravitational News”, Phys. Rev. D, 56, (Nov. 1997), gr-qc/9708065.

[118] 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 condition”, Phys. Rev. Letters 76, 4303 (1996).

[119] P. Anninos et al, Phys. Rev. D50 3801 (1994).

[120] http://www.npac.syr.edu/projects/bbh/dagh.html

[121] http://godel.ph.utexas.edu/Members/marsa/rnpl/refman/refman.html

[122] M. Choptuik and W. G. Unruh, “An Introduction to the Multi-Grid Method for Numerical Relativists”, General Relativity and Gravitation, 18, 813–843 (1986)

[123] M. W. Choptuik, S. Klasky and M. Parashar, “Parallel Multigrid with the DAGH package: Specifications and Applications” (1995) http://godel.ph.utexas.edu/Members/matt/Doc/mgspecs.ps

[124] Tim Collins, Efficient Matrix Computations through Hierarchical Type Specifications, Ph.D. dissertation, The University of Texas at Austin, 1995 [125] (van de Geijn, 1997) Robert A. van de Geijn, Using PLAPACK: Parallel Linear Algebra Package,

The MIT Press, 1997.

[126] (Edwards, 1996) H. C. Edwards, MMPI: Asynchronous message management for the message-passing interface. TICAM Report 96-44, Texas Institute for Computational and Applied Mathematics, The University of Texas at Austin, 1996.

[127] Y. Fu, K. Klimkowski, J. Rodin, G. Berger, J.C. Browne, J.C. Singer, R. van de Geijn, and K.S. Vemaganti, ”A Fast Solution Method for Three Dimensional Many-Particle Problems of Linear Elasticity,” Int. J. Num. Meth. Engrg., to appear.

[128] Y. Fu, ”Application of the Fast Multipole Method to Micromechanics,” Ph.D. Dissertation, The University of Texas at Austin.

[129] G.J. Rodin, ”Toward Rapid Evaluation of the Elastic Interactions among Three-Dimensional Dislocations,” Phil. Mag. Letters, Vol 77, No. 4, pp. 187-190, 1998

[130] T.I. Zohdi, J.T. Oden, and G.J. Rodin, ”Hierarchical Modeling of Heterogeneous Bodies,” Computer Methods in Applied Mechanics and Engineering, 138 (1996), pp. 273–298.

[131] J.T. Oden and T. Zohdi, ”Analysis and Adaptive Modeling of Highly Heterogeneous Elastic Structures,” Computer Methods in Applied Mechanics and Engineering, 148 (1997), pp. 267–381.

[132] E.G. Podnos, I. Babuska, and G. J. Rodin, ”Application of Fictitious Domain Method to Micromechanics of Non-Linear Composite Materials,” submitted to Comp. Mech. in Appl. Mech. Engrg., 1998.