Non-overlapping domain decomposition algorithm based on modified transmission conditions for the Helmholtz equation

A square-root based transmission conditions domain decomposition method was recently introduced for the Helmholtz equation. It produces an effective algorithm where the convergence is independent of the wavenumber and the mesh discretization. We modify here these conditions in order to guarantee well-posedness of local problems and further improve the efficiency of the whole method. Numerical results, in particular in the three dimensional case, show significant reduction of the computational time needed in the iterative procedure while preserving the iteration number when compared with the original algorithm.     

Domain decomposition preconditioners for the spectral collocation method

We propose and analyze several block iteration preconditioners for the solution of elliptic problems by spectral collocation methods in a region partitioned into several rectangles. It is shown that convergence is achieved with a rate that does not depend on the polynomial degree of the spectral solution. The iterative methods here presented can be effectively implemented on multiprocessor systems due to their high degree of parallelism.     

Helmholtz方程的楔形基区域分解法

基于楔形基函数和无网格配点法,提出了一种求解Helmholtz型方程区域分解法。该方法克服了在求解大规模问题时用一般的全域配点法所带来的配置矩阵为非对称满阵,且高度病态的问题。通过数值结果表明,该算法在求解Helmholtz型方程降低系数矩阵条件数的同时,也能够降低误差,并达到满意的收敛效果。     

A Parallel Grid Modification and Domain Decomposition Algorithm for Local Phenomena Capturing and Load Balancing

Lion's nonoverlapping Schwarz domain decomposition method based on a finite difference discretization is applied to problems with fronts or layers. For the purpose of getting accurate approximation of the solution by solving small linear systems, grid refinement is made on subdomains that contain fronts and layers and uniform coarse grids are applied on subdomains in which the solution changes slowly and smoothly. In order to balance loads among different processors, we employ small subdomains with fine grids for rapidly-changing-solution areas, and big subdomains with coarse grids for slowly-changing-solution areas. Numerical implementations in the SPMD mode on an nCUBE2 machine are conducted to show the efficiency and accuracy of the method.     

一种基于PETSc的热传导方程大规模并行求解策略

提出了一种大规模热传导方程并行求解的策略,采用了分布式内存和压缩矩阵技术解决超大规模稀疏矩阵的存储及其计算,整合了多种Krylov子空间方法和预条件子技术来并行求解大规模线性方程组,基于面向对象设计实现了具体应用与算法的低耦合.在Linux机群系统上进行了性能测试,程序具有良好的加速比和计算性能.     

Tuning the Schur complement computations for finite element partitions

The domain decomposition method (DDM) is an efficient algorithmic tool for the parallelization of finite element computer codes. A variant of the DDM with direct solution algorithm is based on computation of Schur complement matrices for finite element partitions. This paper describes a simple technique that considerably improves execution rate of computationally intensive routines of the Schur complement computations. The technique uses ‘block of columns’ matrix operations and loop unrolling to reduce load instructions from cache memory and to increase instruction-level parallelism. For superscalar RISC processors, experimental results show that it is possible to improve performance of the DDM solution procedure by several times.     

An integrated approach to solving mechanical problems on parallel computers

Possibilities of a programming environment that integrates the specificity of the different types of parallel computers are presented in the framework of computational structural mechanics. An extension of the development environment of the Finite Element code CASTEM 2000 has been realized to offer the user a global vision on all objects of the parallel application. To facilitate the implementation of parallel applications, this system hides data transfers between processors and allows a direct reuse of modules of the original sequential code. It is an object-based shared virtual memory system which allows a parallelism by data distribution (for non-structured data) or by control distribution; it is therefore well suited to “mechanic” parallelism. To validate this programming environment, domain decomposition techniques well suited to parallel computation have been used.     

Domain decomposition and discretization of continuous mathematical models

This paper deals with the development of decomposition of domains methods related to the discretization, by collocation-interpolation methods, of continuous models described by nonlinear partial differential equations. The objective of this paper is to show how generalized collocation and domain decomposition methods can be applied for problems where different models are used within the same domain.     

A decomposition method with minimum communication amount for parallelization of multi-dimensional FFTs

The fast Fourier transform (FFT) is undoubtedly an essential primitive that has been applied in various fields of science and engineering. In this paper, we present a decomposition method for the parallelization of multi-dimensional FFTs with the smallest communication amounts for all ranges of the number of processes compared to previously proposed methods. This is achieved by two distinguishing features: adaptive decomposition and transpose order awareness. In the proposed method, the FFT data is decomposed based on a row-wise basis that maps the multi-dimensional data into one-dimensional data, and translates the corresponding coordinates from multi-dimensions into one dimension so that the one-dimensional data can be divided and allocated equally to the processes using a block distribution. As a result and different from previous works that have the dimensions of decomposition pre-defined, our method can adaptively decompose the FFT data on the lowest possible dimensions depending on the number of processes. In addition, this row-wise decomposition provides plenty of alternatives in data transpose, and different transpose order results in different amounts of communication. We identify the best transpose orders with the smallest communication amounts for the 3-D, 4-D, and 5-D FFTs by analyzing all possible cases. We also develop a general parallel software package for the most popular 3-D FFT based on our method using the 2-D domain decomposition. Numerical results show good performance and scaling properties of our implementation in comparison with other parallel packages. Given both communication efficiency and scalability, our method is promising in the development of highly efficient parallel packages for the FFT.     

Domain decomposition for wave propagation problems

The problem posed by domain decomposition methods is to find the correct modeling of physical phenomena across the interfaces separating the subdomains. The technique described here for wave propagation problems is based on physical grounds since it relies on the fact that the wave equation can be decomposed into incoming and outgoing wave modes at the boundaries of the subdomains. The inward propagating waves depend on the solution exterior to the subdomains and therefore are computed from the appropriate boundary conditions, while the behavior of the outward propagating waves is determined by the solution inside the subdomains. The technique is applied to the anisotropic-viscoelastic wave equation, which practically includes all the possible rheologies of one-phase media.     

Domain decomposition operator splitting for mimetic finite difference discretizations of non-stationary problems

In this paper, we propose reliable and efficient numerical methods for solving semilinear, time-dependent partial differential equations of reaction–diffusion type. The original problem is first integrated in time by using a linearly implicit fractional step Runge–Kutta method. This method takes advantage of a suitable partitioning of the diffusion operator based on domain decomposition techniques. The resulting semidiscrete problem is fully discretized by means of a mimetic finite difference method on quadrilateral meshes. Due to the previous splitting, the totally discrete scheme can be reduced to a set of uncoupled linear systems which can be solved in parallel. The overall algorithm is unconditionally stable and second-order convergent in both time and space. These properties are confirmed by numerical experiments.     

A finite difference non-matching domain decomposition algorithm for the parabolic equation

A finite difference domain decomposition algorithm on a non-overlapping non-matching grid for the parabolic equation is discussed. The basic procedure is to define the explicit scheme at the interface points with a larger mesh spacing H, then the implicit schemes with different mesh spacings are applied on the non-matching subdomains, respectively. The stability bound is released both for the one-dimensional and two-dimensional parabolic problem. Finally, numerical experiments are also presented.     

Strategies of domain decomposition for the design of parallel algorithms

This is a framework of the domain decomposition method (DDM) for solving PDEs on parallel computers. Three types of DDM: DDM with overlapping, DDM without overlapping and DDM with fictitious components are discussed in a uniform framework.     

A parallel block LU decomposition method for distributed finite element matrices

In this work we present a new parallel direct linear solver for matrices resulting from finite element problems. The algorithm follows the nested dissection approach, where the resulting Schur complements are also distributed in parallel. The sparsity structure of the finite element matrices is used to pre-compute an efficient block structure for the LU factors. We demonstrate the performance and the parallel scaling behavior by several test examples.     

A parallel finite element procedure for contact-impact problems

An efficient parallel finite element procedure for contact-impact problems is presented within the framework of explicit finite element analysis with thepenalty method. The procedure concerned includes a parallel Belytschko-Lin-Tsay shell element generation algorithm and a parallel contact-impact algorithm based on the master-slave slideline algorithm. An element-wise domain decomposition strategy and a communication minimization strategy are featured to achieve almost perfect load balancing among processors and to show scalability of the parallel performance. Throughout this work, a prototype code, named GT-PARADYN, is developed on the IBM SP2 to implement the procedure presented, under message-passing paradigm. Some examples are provided to demonstrate the timing results of the algorithms, discussing the accuracy and efficiency of the code.     

Domain decomposition method for unstructured meshes in an OpenMP computing environment

In this paper, an efficient unstructured mesh calculation method in an OpenMP parallel computation using multi-core processor is proposed. This is a new domain decomposition method with two characteristics. The first characteristic is to define the size of the sub-block in the computation domain by the size of the cache memory in each core. The second one is to reduce idle time by distributing a defined sub-block for each core appropriately. Using the proposed method, a computation on compressible flow around a plane was able to achieve speed-up more than about 20% in comparison with a conventional method.     

Topology optimization of 2D continua for minimum compliance using parallel computing

Topology optimization is often used in the conceptual design stage as a preprocessing tool to obtain overall material distribution in the solution domain. The resulting topology is then used as an initial guess for shape optimization. It is always desirable to use fine computational grids to obtain high-resolution layouts that minimize the need for shape optimization and postprocessing (Bendsoe and Sigmund, Topology optimization theory, methods and applications. Springer, Berlin Heidelberg New York 2003), but this approach results in high computation cost and is prohibitive for large structures. In the present work, parallel computing in combination with domain decomposition is proposed to reduce the computation time of such problems. The power law approach is used as the material distribution method, and an optimality criteria-based optimizer is used for locating the optimum solution [Sigmund (2001)21:120–127; Rozvany and Olhoff, Topology optimization of structures and composites continua. Kluwer, Norwell 2000]. The equilibrium equations are solved using a preconditioned conjugate gradient algorithm. These calculations have been done using a master–slave programming paradigm on a coarse-grain, multiple instruction multiple data, shared-memory architecture. In this study, by avoiding the assembly of the global stiffness matrix, the memory requirement and computation time has been reduced. The results of the current study show that the parallel computing technique is a valuable tool for solving computationally intensive topology optimization problems.