1 Introduction

This review discusses fundamental tools from the analytical and numerical theory underlying the Einstein field equations as an evolution problem on a finite computational domain. The process of reaching the current status of numerical relativity after decades of effort not only has driven the community to use state of the art techniques but also to extend and work out new approaches and methodologies of its own. This review discusses some of the theory involved in setting up the problem and numerical approaches for solving it. Its scope is rather broad: it ranges from analytical aspects related to the well-posedness of the Cauchy problem to numerical discretization schemes guaranteeing stability and convergence to the exact solution.

At the continuum, emphasis is placed on setting up the initial-boundary value problem (IBVP) for Einstein’s equations properly, by which we mean obtaining a well-posed formulation, which is flexible enough to incorporate coordinate conditions, which allow for long-term and accurate stable numerical evolutions. Here, the well-posedness property is essential, in that it guarantees the existence of a unique solution, which depends continuously on the initial and boundary data. In particular, this assures that small perturbations in the data do not get arbitrarily amplified. Since such small perturbations do appear in numerical simulations because of discretization errors or finite machine precision, if such unbounded growth were allowed, the numerical solution would not converge to the exact one as resolution is increased. This picture is at the core of Lax’ historical theorem, which implies that the consistency of the numerical scheme is not sufficient for its solution to converge to the exact one. Instead, the scheme also needs to be numerically stable, a property, which is the discrete counterpart of well-posedness of the continuum problem.

While the well-posedness of the Cauchy problem in general relativity in the absence of boundaries was established a long time ago, only relatively recently has the IBVP been addressed and well-posed problems formulated. This is mainly due to the fact that the IBVP presents several new challenges, related to constraint preservation, the minimization of spurious reflections, and well-posedness. In fact, it is only very recently that such a well-posed problem has been found for a metric based formulation used in numerical relativity, and there are still open issues that need to be sorted out. It is interesting to point out that the IBVP in general relativity has driven research, which has led to well-posedness results for second-order systems with a new large class of boundary conditions, which, in addition to Einstein’s equations, are also applicable to Maxwell’s equations in their potential formulation.

At the discrete level, the focus of this review is mainly on designing numerical schemes for which fast convergence to the exact solution is guaranteed. Unfortunately, no or very few general results are known for nonlinear equations and, therefore, we concentrate on schemes for which stability and convergence can be shown at the linear level, at least. If the exact solution is smooth, as expected for vacuum solutions of Einstein’s field equations with smooth initial data and appropriate gauge conditions, at least as long as no curvature singularities form, it is not unreasonable to expect that schemes guaranteeing stability at the linearized level, perhaps with some additional filtering, are also stable for the nonlinear problem. Furthermore, since the solutions are expected to be smooth, emphasis is placed here on using fast converging space discretizations, such as high-order finite-difference or spectral methods, especially those which can be applied to multi-domain implementations.

The organization of this review is at follows. Section 3 starts with a discussion of well-posedness for initial-value problems for evolution problems in general, with special emphasis on hyperbolic ones, including their algebraic characterization. Next, in Section 4 we review some formulations of Einstein’s equations, which yield a well-posed initial-value problem. Here, we mainly focus on the harmonic and BSSN formulations, which are the two most widely used ones in numerical relativity, as well as the ADM formulation with different gauge conditions. Actual numerical simulations always involve the presence of computational boundaries, which raises the need of analyzing well-posedness of the IBVP. For this reason, the theory of IBVP for hyperbolic problems is reviewed in Section 5, followed by a presentation of the state of the art of boundary conditions for the harmonic and BSSN formulations of Einstein’s equations in Section 6, where open problems related with gauge uniqueness are also described.

Section 7 reviews some of the numerical stability theory, including necessary eigenvalue conditions. These are quite useful in practice for analyzing complicated systems or discretizations. We also discuss necessary and sufficient conditions for stability within the method of lines, and Runge–Kutta methods. Sections 8 and 9 are devoted to two classes of spatial approximations: finite differences and spectral methods. Finite differences are rather standard and widespread, so in Section 8 we mostly focus on the construction of optimized operators of arbitrary high order satisfying the summation-by-parts property, which is useful in stability analyses. We also briefly mention classical polynomial interpolation and how to systematically construct finite-difference operators from it. In Section 9 we present the main elements and theory of spectral methods, including spectral convergence from solutions to Sturm–Liouville problems, expansions in orthogonal polynomials, Gauss quadratures, spectral differentiation, and spectral viscosity. We present several explicit formulae for the families of polynomials most widely used: Legendre and Chebyshev. Section 10 describes boundary closures. In the present context they refer to procedures for imposing boundary conditions leading to stability results. We emphasize the penalty technique, which applies to both finite-difference methods of arbitrary high-order and spectral ones, as well as outer and interface boundaries, such as those appearing when there are multiple grids as in complex geometries domain decompositions. We also discuss absorbing boundary conditions for Einstein’s equations. Finally, Section 11 presents a random sample of approaches in numerical relativity using multiple, semi-structured grids, and/or curvilinear coordinates. In particular, some of these examples illustrate many of the methods discussed in this review in realistic simulations.

There are many topics related to numerical relativity, which are not covered by this review. It does not include discussions of physical results in general relativity obtained through numerical simulations, such as critical phenomena or gravitational waveforms computed from binary black-hole mergers. For reviews on these topics we refer the reader to [223Jump To The Next Citation Point] and [337, 122], respectively. See also [9, 45] for recent books on numerical relativity. Next, we do not discuss setting up initial data and solving the Einstein constraints, and refer to [133]. For reviews on the characteristic and conformal approach, which are only briefly mentioned in Section 6.4, we refer the reader to [432Jump To The Next Citation Point] and [172Jump To The Next Citation Point], respectively. Most of the results specific to Einstein’s field equations in Sections 4 and 6 apply to four-dimensional gravity only, though it should be possible to generalize some of them to higher-dimensional theories. Also, as we have already mentioned, the results described here mostly apply to the vacuum field equations, in which case the solutions are expected to be smooth. For aspects involving the presence of shocks, such as those present in relativistic hydrodynamics we refer the reader to [165, 295]. Finally, see [352Jump To The Next Citation Point] for a more detailed review on hyperbolic formulations of Einstein’s equations, and [351] for one on global existence theorems in general relativity. Spectral methods in numerical relativity are discussed in detail in [215Jump To The Next Citation Point]. The 3+1 approach to general relativity is thoroughly reviewed in [214Jump To The Next Citation Point]. Finally, we refer the reader to [126] for a recent book on general relativity and the Einstein equations, which, among many other topics, discusses local and global aspects of the Cauchy problem, the constraint equations, and self-gravitating matter fields such as relativistic fluids and the relativistic kinetic theory of gases.

Except for a few historical remarks, this review does not discuss much of the historical path to the techniques and tools presented, but rather describes the state of the art of a subset of those which appear to be useful. Our choice of topics is mostly influenced by those for which some analysis is available or possible.

We have tried to make each section as self-consistent as possible within the scope of a manageable review, so that they can be read separately, though each of them builds from the previous ones. Numerous examples are included.

  Go to previous page Go up Go to next page