TIME-SYMMETRICAL ADI AND CAUSAL RECONNECTION - STABLE NUMERICAL TECHNIQUES FOR HYPERBOLIC SYSTEMS ON MOVING GRIDS

Moving grids are of interest in the numerical solution of hydrodynamic al problems and in numerical relativity. We show that conventional int egration methods for the simple wave equation in one and more than one dimension exhibit a number of instabilities on moving grids. We intro duce two techniques, which we call causal reconnection and time-symmet ric ADI, which together allow integration of the wave equation with ab solute local stability in any number of dimensions on grids that may m ove very much faster than the wave speed and that can even accelerate. These methods allow very long time-steps, are fully second-order accu rate, and offer the computational efficiency of operator-splitting. We develop causal reconnection first in the one-dimensional case; we fin d that a conventional implicit integration scheme that is unconditiona lly stable as long as the speed of the grid is smaller than that of th e waves nevertheless turns unstable whenever the grid speed increases beyond this value. We introduce a notion of local stability for differ ence equations with variable coefficients. We show that, by ''reconnec ting'' the computational molecule at each time-step in such a way as t o ensure that its members at different time-steps are within one anoth er's causal domains, one eliminates the instability, even if the grid accelerates. This permits very long time-steps on rapidly moving grids . The method extends in a straightforward and efficient way to more th an one dimension. However, in more than one dimension, it is very desi rable to use operator-splitting techniques to reduce the computational demands of implicit methods, and we find that standard schemes for in tegrating the wave equation-Lees' first and second alternating directi on implicit (ADI) methods-go unstable for quite small grid velocities. Lees' first method, which is only first-order accurate on a shifting grid, has mild but nevertheless significant instabilities. Lees' secon d method, which is second-order accurate, is very unstable. By adoptin g a systematic approach to the design of ADI schemes, we develop a new ADI method that cures the instability for all velocities in any direc tion up to the wave speed. This scheme is uniquely defined by a simple physical principle: the ADI difference equations should be invariant under time-inversion. (The wave equation itself and the fully implicit difference equations satisfy this criterion, but neither of Lees' met hods do.) This new time-symmetric ADI scheme is, as a bonus, second-or der accurate. It is thus far more efficient than a fully implicit sche me, just as stable, and just as accurate. By implementing causal recon nection of the computational molecules, we extend the time-symmetric A DI scheme to arrive at a scheme that is second-order accurate, computa tionally efficient, and unconditionally locally stable for all grid sp eeds and long time-steps. We have tested the method by integrating the wave equation on a rotating grid, where it remains stable even when t he grid speed at the edge is 15 times the wave speed. Because our meth ods are based on simple physical principles, they should generalize in a straightforward way to many other hyperbolic systems. We discuss br iefly their application to general relativity and their potential gene ralization to fluid dynamics. (C) 1994 Academic Press, Inc.