Numerical methods for the Einstein equations in null quasi-spherical coordinates

We describe algorithms used in our construction of a fourth-order in time evolution for the full Einstein equations and assess the accuracy of some representative solutions. The scheme employs several novel geometric and numerical techniques, including a geometrically invariant coordinate gauge, which leads to a characteristic-transport formulation of the underlying hyperbolic system, combined with a method of lines evolution; convolution splines for radial interpolation, regridding, differentiation, and noise suppression; representations using spin-weighted spherical harmonics; and a spectral preconditioner for solving a class of first-order elliptic systems on S-2. Initial data for the evolution is unconstrained, subject only to a mild size condition. For sample initial data of intermediate strength (19% of the total mass in gravitational energy), the code is accurate to 1 part in 10(5), until null time z = 55m when the coordinate condition breaks down.