In this paper we present a survey and new parallel algorithms for the solution of the incompressible two- and three-dimensional Navier-Stokes equations. We present a high-order parallel algorithms which require only minimum inter-processor communication which is dictated by the physical nature of the problem at hand. The parallelization is achieved via domain decomposition. We consider computational regions in the form of a 2-D or 3-D periodic box which is decomposed into parallel strips (slabs) and cells. The time discretization is performed via the semi-implicit splitting scheme of [33]. The splitting procedure in time results in solving in each time step two global elliptic equations: the Poisson equation for the determination of the pressure field and the Helmholtz equation for the implicit viscous step. The discretization in space is performed using the Local Fourier Basis method [23] and the multidomain local Fourier (MDLF) method that was developed in [1-3, 7-9, 12, 13, 29, 30, 37, 40]. Therefore, in the direction across the strip or cells 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 discretization in the periodic directions is performed by the standard Fourier method. To avoid the Gibbs phenomenon, the global functions are decomposed into smooth local pieces. Then the Fourier method is applied on the extended local subdomains with spectral accuracy. The continuity conditions on the interfaces are enforced by adding homogeneous solutions. Therefore, 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 for the Helmholtz equation. Such solutions often have fast decay properties which can be utilized to minimize interprocessor communication. In effect, the predominant part of the computation is performed independently in the subdomains (processors) by using only local communication. We consider the complete Navier-Stokes system. 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, as we showed in [5, 15, 40] only a few lowest harmonics require 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. 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. We proposed a new algorithm for the parallel solution of two-dimensional Navier-Stokes type equation with constant and non-constant coefficients which is mapped onto cell topology. This is a further development in the application of the local Fourier methods to the solutions of PDE's in multidomain regions. The extension of the above solution to problems with non-constant coefficients is suggested via spectral multidomain preconditioner. In addition, an appropriate Alternate Direction Implicit (ADI) scheme was applied. It enables the reduction of a 2-D problem to a collection of uncoupled 1-D ODE's. In effect, the 1-D solver becomes the basic routine to solve a 2-D problem using splitting of differential operators by ADI. The Navier-Stokes solvers were implemented on four MIMD multiprocessors: 26-processors MEIKO, 60-processors IBM SP2, a all-processors MOSIX, and a network of 10 Alpha workstations. The implementation on the last three machines used the same code written with PVM (parallel virtual machine) software package.
