PARALLEL HIGH-ORDER INTEGRATORS

Journal article

In this work we discuss a class of defect correctio n methods which is easily adapted to create parallel time integrators for multicore architectures and is ideally suited for developing methods which can be order adaptive in time. The method is based on integral deferred correction (IDC), which was itself motivated by spectral deferred correction by Dutt, Greengard, and Rokhlin [BIT, 40 (2000), pp. 241-266]. The method presented here is a revised formulation of explicit IDC, dubbed revisionist IDC (RIDC), which can achieve pth-order accuracy in "wall-clock time" comparable to a single forward Euler simulation on problems where the time to evaluate the right-hand side of a system of differential equations is greater than latency costs of interprocessor communication, such as in the case of the N-body problem. The key idea is to rewrit e the defect correction framework so that, after initial start-up costs, each correction loop can be lagged behind the previous correction loop in a manner that facilitates running the predictor and M = p - 1 correctors in parallel on an interval which has K steps, where K p. We prove that given an rth-order Runge-Kutta method in both the prediction and M correction loops of RIDC, then the method is order r X (M +1). The parallelization in RIDC uses a small number of cores (the number of processors used is limited by the order one wants to achieve). Using a four-core CPU, it is natural to think about fourth-order RIDC built with forward Euler, or eighth-order RIDC construct ed with second-order Runge-Kutta. Numerical tests on an N-body simulation show that RIDC met hods can be significantly faster than popular Runge-Kutta methods such as the classical fourth-ord er Runge-Kutta scheme. In a PDE setting, one can imagine coupling RIDC time integrators with parallel spatial evaluators, thereby increasing the parallelization. The ideas behind RIDC extend to implicit and semi-implicit IDC and have high potential in this area. © 2010 Society for Industrial and Applied Mathematics.

Authors: Christlieb, A; Macdonald, C; Ong, B

• Publication status: Published
• Journal: SIAM JOURNAL ON SCIENTIFIC COMPUTING
• Volume: 32
• Issue: 2
• Pages: 818-835
• Publication date: 2010-01-01
• DOI: 10.1137/09075740X
• EISSN: 1095-7197
• ISSN: 1064-8275
• Language: English
• Keywords: initial value problems; multicore computing; parallel computation; integral deferred correction; N-body simulations