Parallel-multigrid computation of unsteady incompressible viscous flows using a matrix-free implicit method and high-resolution characteristics-based scheme

A three-dimensional parallel unstructured non-nested multigrid solver for solutions of unsteady incompressible viscous flow is developed and validated. The finite-volume Navier–Stokes solver is based on the artificial compressibility approach with a high-resolution method of characteristics-based scheme for handling convection terms. The unsteady flow is calculated with a matrix-free implicit dual time stepping scheme. The parallelization of the multigrid solver is achieved by multigrid domain decomposition approach (MG-DD), using single program multiple data (SPMD) and multiple instruction multiple data (MIMD) programming paradigm. There are two parallelization strategies proposed in this work, first strategy is a one-level parallelization strategy using geometric domain decomposition technique alone, second strategy is a two-level parallelization strategy that consists of a hybrid of both geometric domain decomposition and data decomposition techniques. Message-passing interface (MPI) and OpenMP standard are used to communicate data between processors and decompose loop iterations arrays, respectively. The parallel-multigrid code is used to simulate both steady and unsteady incompressible viscous flows over a circular cylinder and a lid-driven cavity flow. A maximum speedup of 22.5 could be achieved on 32 processors, for instance, the lid-driven cavity flow of Re = 1000. The results obtained agree well with numerical solutions obtained by other researchers as well as experimental measurements. A detailed study of the time step size and number of pseudo-sub-iterations per time step required for simulating unsteady flow are presented in this paper.     

A parallel fictitious domain multigrid preconditioner for the solution of Poisson’s equation in complex geometries

A parallel multilevel preconditioner based on domain decomposition and fictitious domain methods has been presented for the solution of the Poisson equation in complicated geometries. Rectangular blocks with matching grids on interfaces on a structured rectangular mesh have been used for the decomposition of the problem domain. Sloping sides or curved boundary surfaces are approximated using stepwise surfaces formed by the grid cells. A seven-point stencil based on the central difference scheme has been used for the discretization of the Laplacian for both interior and boundary grid points, and this results in a symmetric linear algebraic system for any type of boundary condition. The preconditioned conjugate gradient method has been used for the solution of this symmetric system. The multilevel preconditioner for the CG is based on a V-cycle multigrid applied to the Poisson equation on a fictitious domain formed by the union of the rectangular blocks used for the domain decomposition. Numerical results are presented for two typical Poisson problems in complicated geometries—one related to heat conduction, and the other one arising from the LES/DNS of incompressible turbulent flow over a packed array of spheres. These results clearly show the efficiency and robustness of the proposed approach.     

A comparison of some standard elliptic solvers: CM-5 vs. Cray C-90

The implementations of the domain decomposition, SOR, multigrid and conjugate gradient method on CM-5 and Cray C-90 are described for the Laplace's equation on the unit square and L-shaped region. Domain decomposition method uses the Schwarz alternating method. In each domain we take the one-dimensional FFT to convert the problem into the tridiagonal systems which are solved by the scientific libraries installed in the CM-5 and the Cray C-90. On the CM-5 the V-cycle multigrid with symmetric smoothings on P-1 finite element spaces is run with red/black Gauss-Seidel relaxation. Multigrid with natural order Gauss-Seidel relaxation is used on the Cray C-90. While natural order SOR is used in the Cray C-90, R/B SOR is performed on the CM-5. Multigrid is the fastest method on the CM-5 and three methods except SOR give similar performances on Cray C-90.This research was partially supported by the National Science Foundation under Grant No. CDA-9024618.     

求解半线性椭圆型方程组的并行算法

本文结合区域分裂技术、多重网格方法、加速Ｓｃｈｗａｒｚ收敛方法、高低解方法、非线性Ｊａｃｏｂｉ迭代方法和Ｎｅｗｔｏｎ线性化迭代方法,设计了三种求解半线性椭圆型方程（组）的并行算法：并行Ｎｅｗｔｏｎ多重网格算法、并行非线性多重网格算法和并行加速Ｓｃｈｗａｒｚ收敛算法。数值试验说明这三种算法的并行计算是可行的。     

PARALLEL PROCESSING FOR CHROMOSOME RECONSTRUCTION FROM PHYSICAL MAPS - A CASE STUDY OF MIMD PARALLELISM ON THE HYPERCUBE

Ordering clones from a genomic library into physical maps of whole chromosomes presents a pivotal computational problem in genetics. Previous research has shown the physical mapping problem to be isomorphic to the NP-complete Optimal Linear Arrangement (OLA) problem for which no polynomial-time algorithm for determining the optimal solution is known. Serial implementations of stochastic global optimization techniques such as simulated annealing yielded very good results but proved computationally intensive. The design, analysis and implementation of coarse-grained parallel MIMD algorithms for simulated annealing on the Intel iPSC/860 hypercube is presented. Data decomposition and control decomposition strategies based on Markov chain decomposition, perturbation methods and problem-specific annealing heuristics are proposed and applied to the physical mapping problem. A suite of parallel algorithms are implemented on an 8-node Intel iPSC/860 hypercube, exploiting the nearest-neighbor communication pattern on the Boolean hypercube topology. Convergence, speedup and scalability characteristics of the various parallel algorithms are analyzed and discussed. Results indicate a deterioration of performance when a single Markov chain of solution states is distributed across multiple processing elements in the Intel iPSC/860 hypercube.     

Connected Component Labeling on Coarse Grain Parallel Computers: An Experimental Study

Connected component labeling is a fundamental task in computer vision. This paper presents parallel implementations of connected component labeling for grey level images on the iPSC/2 and iPSC/86O hypercubes, the CM-5, and on the shared memory Encore Multimax multiprocessor. Several partitioning and mapping strategies, including multidimensional divide and conquer, block decomposition, and scatter decomposition, for different multiprocessor sizes, are used. Implementation results, performance evaluation and comparison for all the mapping strategies are reported. The block and scatter decomposition methods are simple to implement given the sequential algorithm, but their performance is sensitive to the distribution of intensity values in the image. The multidimensional divide and conquer method is more difficult to implement, but it performs the best irrespective of the intensity value distribution.     

Parallel computation of unsteady three-dimensional incompressible viscous flow using an unstructured multigrid method

The development and validation of a parallel unstructured tetrahedral non-nested multigrid (MG) method for simulation of unsteady 3D incompressible viscous flow is presented. The Navier-Stokes solver is based on the artificial compressibility method (ACM) and a higher-order characteristics-based finite-volume scheme on unstructured MG. Unsteady flow is calculated with an implicit dual time stepping scheme. The parallelization of the solver is achieved by a MG domain decomposition approach (MG-DD), using the Single Program Multiple Data (SPMD) programming paradigm. The Message-Passing Interface (MPI) Library is used for communication of data and loop arrays are decomposed using the OpenMP standard. The parallel codes using single grid and MG are used to simulate steady and unsteady incompressible viscous flows for a 3D lid-driven cavity flow for validation and performance evaluation purposes. The speedups and efficiencies obtained by both the parallel single grid and MG solvers are reasonably good for all test cases, using up to 32 processors on the SGI Origin 3400. The parallel results obtained agree well with those of serial solvers and with numerical solutions obtained by other researchers, as well as experimental measurements.     

Hierarchical matrix techniques for a domain decomposition algorithm

Summary In this paper, we investigate the effectiveness of hierarchical matrix techniques when used as the linear solver in a certain domain decomposition algorithm. In particular, we provide a direct performance comparison between an algebraic multigrid solver and a hierarchical matrix solver which is based on nested dissection clustering within the software package PLTMG.      

An application of domain decomposition methods with non-conforming spectral element/Fourier expansions for the incompressible Navier–Stokes equations

An application of domain decomposition methods is presented for the incompressible Navier–Stokes equations. Non-conforming spectral element/Fourier expansions in the separate domains are employed, and a simple iterative algorithm is used, based on the Dirichlet/Neumann method at the domain interface. Thus, a new element in the present approach is that patching of mixed algebraic/trigonometric polynomial spaces is applied at the domain interface, whereas usually in domain decomposition methods finite-order polynomial spaces have been employed in the separate domains. By applying a coupled scheme for the velocity and pressure fields in each domain, a stable algorithm is obtained. New numerical results are presented on a 3-D model problem of flow in a channel, where both bounding surfaces have corrugations, but of different orientation. Smooth solutions across the domain interface are obtained. Steady flow and the onset of flow instability is simulated and discussed. The results demonstrate that spectral element/Fourier expansions, which have been previously used to study flows in geometries with one homogeneous dimension, may be employed to tackle flow problems in relatively more complex geometries. Furthermore, the results suggest that decomposition into domains with 3-D elements and domains with 2-D elements/Fourier expansions, or domains handled by spectral methods, may be an attractive possibility. The advantage is due to the orthogonality and decoupling of the Fourier modes, which leads to a computational load increasing only linearly with resolution. A related attractive feature is that a natural way for parallel implementation is offered.     

Parallel multilevel methods with adaptivity on unstructured grids

We present two parallel multilevel methods for solving large-scale discretized partial differential equations on unstructured 2D/3D grids. The presented methods combine three powerful numerical algorithms: overlapping domain decomposition, multigrid method and adaptivity. As the foundation of the methods we propose an algorithm for generating and partitioning a hierarchy of adaptively refined unstructured grids, so that adaptivity can be incorporated up to a certain grid level. We ensure that the resulting subgrid hierarchies are well balanced and no inter-processor communication is needed across different grid levels, thus obtaining high parallel efficiency. Numerical experiments show that the parallel multilevel methods offer almost equally fast convergence as their sequential multigrid counterpart. And the resulting implementation has reasonably good scalability. Received: 4 December 1998 / Accepted: 12 January 2000     

Adaptive and fixed segmented domain decomposition multigrid procedures for internal viscous flows

A segmented domain decomposition multigrid procedure is reviewed. The methodology is outlined for both an adaptive formulation applied primarily to inlet, nozzle and duct flows, and for a fixed, predetermined, subdomain formulation applied for turbomachinery geometries. The procedure has been considered for both low and high speed flows in two- and three-dimensions, and for laminar and turbulent-model applications. With these procedures, the grids remain uniform in each subdomain; although the global grid appears to be highly stretched. This formulation allows for computations with a high degree of accuracy and grid independence at reasonable computer cost. This is generally not possible to replicate with full domain multigrid procedures on stretched grids with large cell aspect ratio.     

The Navier–Stokes-αβ equations as a platform for a spectral multigrid method to solve the Navier–Stokes equations

This paper describes a spectral multigrid method for spatially periodic homogeneous and isotropic turbulent flows. The method uses the Navier–Stokes-αβ equations to accelerate convergence toward solutions of the Navier–Stokes equations. The Navier–Stokes-αβ equations are solved on coarse grids at various levels and the Navier–Stokes equations are solved on the “nest grid”. The method uses Crank–Nicolson time-stepping for the viscous terms, explicit time-stepping for the remaining terms, and Richardson iteration to solve linear systems encountered at each time step and on each grid level. To explore the computational efficiency of the method, comparisons are made with results obtained from an analogous spectral multigrid method for the Navier–Stokes equations. These comparisons are based on computing work units and residuals for multigrid cycles. Most importantly, we examine how choosing different values of the length scales α and β entering the Navier–Stokes-αβ equations influence the efficiency and accuracy of these multigrid schemes.     

From multi- to single-grid CFD on massively parallel computers: Numerical experiments on lid-driven flow in a cube using pressure–velocity coupled formulation

A parallel implementation of a fully pressure–velocity coupled multigrid solver based on analytical solution accelerated coupled line Gauss Seidel (ASA-CLGS) smoother with grid partitioning is carried out. The parallelized algorithm is characterized by an enhanced scalability that results from a formulation enabling an intermediate analytical solution for the entire row (column) of control volumes. General strategies of applying single- or multigrid approach depending on flow characteristics are discussed. Performance of the parallelized algorithm is studied for up to 2048 processors. The developed approach is applied to analysis of a time-dependent three-dimensional incompressible lid-driven cavity flow. The steady state results of benchmark quality are reported for Re = 10³, 1.5 × 10³ and 1.9 × 10³. A new benchmark case of a fully 3D flow in a cubic cavity driven by the lid moving at 45° relatively to its lateral boundaries is proposed and the corresponding data is reported.     

Additive Schwarz with aggregation-based coarsening for elliptic problems with highly variable coefficients

Summary We develop a new coefficient-explicit theory for two-level overlapping domain decomposition preconditioners with non-standard coarse spaces in iterative solvers for finite element discretisations of second-order elliptic problems. We apply the theory to the case of smoothed aggregation coarse spaces introduced by Vanek, Mandel and Brezina in the context of algebraic multigrid (AMG) and are particularly interested in the situation where the diffusion coefficient (or the permeability) α is highly variable throughout the domain. Our motivating example is Monte Carlo simulation for flow in rock with permeability modelled by log–normal random fields. By using the concept of strong connections (suitably adapted from the AMG context) we design a two-level additive Schwarz preconditioner that is robust to strong variations in α as well as to mesh refinement. We give upper bounds on the condition number of the preconditioned system which do not depend on the size of the subdomains and make explicit the interplay between the coefficient function and the coarse space basis functions. In particular, we are able to show that the condition number can be bounded independent of the ratio of the two values of α in a binary medium even when the discontinuities in the coefficient function are not resolved by the coarse mesh. Our numerical results show that the bounds with respect to the mesh parameters are sharp and that the method is indeed robust to strong variations in α. We compare the method to other preconditioners and to a sparse direct solver.      

A multiblock multigrid grid generation method for complex simulations

This paper deals with the aim of coupling multigrid generation of boundary-fitted grids with an effective domain decomposition technique. We present multiblock grid generation algorithms for efficient solutions of domain discretization problems. We propose the generation of structured grids by multiblock transformation of the domains, the choice of specific elliptic systems and the application of multigrid cycling. We assume the Laplacians of the curvilinear coordinates to be equal to appropriate functions of the curvilinear coordinates in the physical domain and, by interchanging the independent and the dependent variable, we obtain the transformed systems in the multiblock transformed computational domain. We adopt standard central differencing for the approximation of the nonlinear generating 2D and 3D systems and full approximation storage algorithms to solve the resulting discrete equations. We use block matching with two-surface overlapping and block by block iterations along with multigrid cycling in each block. We present computed multiblock grids by Figures and evaluation results of method performance by Tables.     

An incomplete nested dissection algorithm for parallel direct solution of finite element discretizations of partial differential equations

A multilevel algorithm is presented for direct, parallel factorization of the large sparse matrices that arise from finite element and spectral element discretization of elliptic partial differential equations. Incomplete nested dissection and domain decomposition are used to distribute the domain among the processors and to organize the matrix into sections in which pivoting is applied to stabilize the factorization of indefinite equation sets. The algorithm is highly parallel and memory efficient; the efficient use of sparsity in the matrix allows the solution of larger problems as the number of processors is increased, and minimizes computations as well as the number and volume of communications among the processors. The number of messages and the total volume of messages passed during factorization, which are used as measures of algorithm efficiency, are reduced significantly compared to other algorithms. Factorization times are low and speedups high for implementation on an Intel iPSC/860 hypercube computer. Furthermore, the timings for forward and back substitutions are more than an order-of-magnitude smaller than the matrix decomposition times.     

Degenerate Two-Phase Incompressible Flow IV: Local Refinement and Domain Decomposition

This is the fourth paper of a series in which we analyze mathematical properties and develop numerical methods for a degenerate elliptic-parabolic partial differential system which describes the flow of two incompressible, immiscible fluids in porous media. In this paper we describe a finite element approximation for this system on locally refined grids. This adaptive approximation is based on a mixed finite element method for the elliptic pressure equation and a Galerkin finite element method for the degenerate parabolic saturation equation. Both discrete stability and sharp a priori error estimates are established for this approximation. Iterative techniques of domain decomposition type for solving it are discussed, and numerical results are presented.     

On the numerical modeling of convection-diffusion problems by finite element multigrid preconditioning methods

During the last decades, multigrid methods have been extensively used in order to solve large scale linear systems derived from the discretization of partial differential equations using the finite difference method. The effectiveness of the multigrid method can be also exploited by using the finite element method. Finite Element Approximate Inverses in conjunction with Richardon’s iterative method could be used as smoothers in the multigrid method. Thus, a new class of smoothers based on approximate inverses can be derived. Effectiveness of explicit approximate inverses relies in the fact that they are close approximants to the inverse of the coefficient matrix and are fast to compute in parallel. Furthermore, the proposed class of finite element approximate inverses in conjunction with the explicit preconditioned Richardson method yield improved results against the classic smoothers such as Jacobi method. Moreover, a dynamic relaxation scheme is proposed based on the Dynamic Over/Under Relaxation (DOUR) algorithm. Furthermore, results for multigrid preconditioned Krylov subspace methods, such as GMRES(res), IDR(s) and BiCGSTAB based on approximate inverse smoothing and a dynamic relaxation technique are presented for the steady-state convection-diffusion equation.     

Distributed finite element calculations on transputer arrays and the DAP

An equation solver based on the preconditioned conjugate gradient method for the sparse system arising from finite element analysis is presented. The preconditioning matrix has been designed to take advantage of the domain decomposition approach used on local memory multiprocessor computers. The method has been implemented on a transputer array and on the DAP; results are given for these computers. A simple domain decomposition algorithm is also presented. This method is suitable for the decomposition of finite element meshes for the transputer based analysis program.     

基于FEM／SBFEM的无穷域势流问题重叠型区域分解计算

提出了一种将有限元和比例边界有限元相结合求解无穷域势流问题的算法．用两条封闭曲线将求解域划分为存在重叠的有限和无限两个区域,在有限域和无限域上分别用有限元和比例边界有限元方法求解原问题,通过重叠区域交换数据迭代计算,直至收敛．分析了重叠区域面积的大小对计算收敛速度的影响,发现随着重叠区域面积的增大迭代次数减少,收敛速度加快．数值算例显示了算法的正确性和收敛性．本算法为求解无穷域势流问题提供了一个方法．