Parallelizing implicit algorithms for time-dependent problems by parabolic domain decomposition

Applications of the multidomain Local Fourier Basis method [1], for the solution of PDEs on parallel computers are described. The present approach utilizes, in an explicit way, the rapid (exponential) decay of the fundamental solutions of elliptic operators resulting from semi-implicit discretizations of parabolic time-dependent problems. As a result, the global matching relations for the elemental solutions are decoupled into local interactions between pairs of solutions in neighboring domains. Such interactions require only local communications between processors with short communication links. Thus the present algorithm overcomes the global coupling, inherent both in the use of the spectral Fourier method and implicit time discretization scheme.This research is supported partly by a grant from the French-Israeli Binational Foundation for 1991–1992.     

Spectral multidomain technique with Local Fourier Basis II: Decomposition into cells

The spectral multidomain method for the solution of 2-D elliptic and parabolic PDE's is developed. The computational region is decomposed into rectangular cells. A Local Fourier Basis technique is implemented for the discretization in space. Such a technique enables the global (typically 10⁴–10⁵) matching relations for the interface unknows to be decoupled into a set of relations for only few interface points at a time.This research is supported partly by a grant from the French-Israeli Binational Foundation for 1991–1992.     

Spectral multidomain technique with Local Fourier Basis

A novel domain decomposition method for spectrally accurate solutions of PDEs is presented. A Local Fourier Basis technique is adapted for the construction of the elemental solutions in subdomains.C ¹ continuity is achieved on the interfaces by a matching procedure using the analytical homogeneous solutions of a one dimensional equation. The method can be applied to the solution of elliptic problems of the Poisson or Helmholtz type as well as to time discretized parabolic problems in one or more dimensions. The accuracy is tested for several stiff problems with steep solutions.The present domain decomposition approach is particularly suitable for parallel implementations, in particular, on MIMD type parallel machines.This research is supported partly by a grant from the French-Israeli Binational Foundation for 1991–1992.     

Highly Scalable Two- and Three-Dimensional Navier-Stokes Parallel Solvers on MIMD Multiprocessors

In this paper we present a new parallel algorithm for the solution of the incompressible two- and three-dimensional Navier-Stokes equations. The parallelization is achieved via domain decomposition. The computational region is considered in the form of a 2-D or 3-D periodic box decomposed into parallel strips (slabs). For time discretization we use a third order multistep method of [11]. The time discretization procedure results in solving global elliptic problems of (monotonic) Helmholtz and Poisson types in each time step. For the space discretization we employ the multidomain local Fourier (MDLF) method that was developed in [9, 10, 13]. The discretization in the periodic directions is performed by the standard Fourier method. In the direction across the strips we use the Local Fourier Basis technique which involves the overlapping of the neighboring subdomains and smoothing of local functions across the interior boundaries (interfaces). The matching of the local solutions is performed by adding properly weighted interface Green's functions. Their amplitudes are found in terms of the jumps of the solution and its first derivatives at the interfaces. The present paper extends the results of our previous works [1, 9, 10, 13] on parallel use of the MDLF method in three-fold aspects: 1. In [1] a model Navier-Stokes type system was considered which does not include the pressure term. Correspondingly, in each time step only the Helmholtx type equations were solved. It was shown that the parallel solution of this equation can be accomplished using only local (neighbor-to-neighbor) communication due to localization properties of the Helmholtz operator. We consider the complete Navier-Stokes system including the pressure term. The solution of the Poisson equation for pressure has the potential to degrade the performance and the achieved speedup of a parallel algorithm due to the global nature of this equation that necessitates global communication among the processors. However, we show that only a few lowest harmonics require for the global data transfer whereas the rest of harmonics can be treated locally. Therefore, most of the communication that is required for parallelization of the Navier-Stokes solver using the MDLF method is mainly local between adjacent subdomains (processors). Moreover, the percentage of the time spent in global communication reduces as the size of the problem increases. Thus, the present parallel algorithm is highly scalable. 2. In [l] we considered only 2-D equations. In this paper we extend the previous technique to 3-D problems. 3. Previously, the MDLF solver was implemented only on the MEIKO parallel machine. In this paper the 2-D and 3-D Navier-Stokes solvers are implemented on three MIMD message-passing multiprocessors (a 60-processors IBM SP2, a 20-processors MOSIX [3], and a network of 10 Alpha workstations) and achieve an efficiency of more than 70% to 95%. The same code written with the PVM (parallel virtual machine [7]) software package was executed on all the above distinct computational platforms. Detailed performance results, which include scalability analysis, are presented. This revised version was published online in June 2006 with corrections to the Cover Date.