A mapping algorithm for domain decomposition in massively parallel finite element analysis

A new mapping algorithm is presented for domain decomposition for the purpose of allowing researchers to conduct finite element analysis on massively parallel computers. Over the last few years, massively parallel MIMD machines such as the Intel Touchstone Delta and recently the Intel Touchstone Paragon have become increasingly popular for speeding up finite element computations. Most of these applications use domain decomposition as a first step towards conquering the problem. Many different algorithms have been developed by researchers to achieve an effective domain decomposition. Some of these methods use connectivity information only, some use coordinate information only, while others use both of them together. Some algorithms are based on assigning weights to nodes using a particular strategy while others are recursive in nature. As will be discussed in this paper, the logic employed in various algorithms works perfectly well for certain meshes to be decomposed, in certain numbers of subdomains; while it gives far from perfect results for other meshes or for same meshes to be decomposed in a different number of subdomains. The logic used in the proposed algorithm has been developed in a creative way such that it is closer to a human's natural thinking when making decisions. Fairly large meshes can be decomposed in a matter of seconds on a Sun Sparc station by the proposed algorithm. Its execution time remains almost the same for any number of subdomains.     

A new parallel domain decomposition method for the adaptive finite element solution of elliptic partial differential equations

We present a new domain decomposition algorithm for the parallel finite element solution of elliptic partial differential equations. As with most parallel domain decomposition methods each processor is assigned one or more subdomains and an iteration is devised which allows the processors to solve their own subproblem(s) concurrently. The novel feature of this algorithm however is that each of these subproblems is defined over the entire domain—although the vast majority of the degrees of freedom for each subproblem are associated with a single subdomain (owned by the corresponding processor). This ensures that a global mechanism is contained within each of the subproblems tackled and so no separate coarse grid solve is required in order to achieve rapid convergence of the overall iteration. Furthermore, by following the paradigm introduced in 15 , it is demonstrated that this domain decomposition solver may be coupled easily with a conventional mesh refinement code, thus allowing the accuracy, reliability and efficiency of mesh adaptivity to be utilized in a well load-balanced manner. Finally, numerical evidence is presented which suggests that this technique has significant potential, both in terms of the rapid convergence properties and the efficiency of the parallel implementation. Copyright © 2001 John Wiley & Sons, Ltd.     

Structural dynamic analysis on a parallel computer: The finite element machine

The development of general-purpose finite element computer software systems has provided the capability to analyze a wide range of linear and non-linear structural problems. However, these software systems are severely limited for non-linear response calculations because of the available speed on current sequential computers. Recent and projected advances in parallel multiple instruction multiple data (MIMD) computers provide an opportunity for significant gains in computing speed and for broadening the range of structural problems which may be solved. The key to these gains is the effective selection and implementation of algorithms which exploit parallel computing. This paper documents experiences solving transient response calculations on an experimental MIMD computer, termed the Finite Element Machine. The paper describes the algorithm used, its implementation for parallel computations, and results for representative one- and two-dimensional dynamic response test problems. The results show computation speedups of up to 7.83 for eight processors, and indicate that significant speedups of solution time are possible for non-linear dynamic response calculations through the use of many processors and appropriate parallel integration algorithms. The results are extremely encouraging and suggest that significant speedups in structural computations can be achieved through advances in parallel computers.     

A parallel finite element solution method

New parallel computer architectures have revolutionized the design of computer algorithms, and promise to have significant influence on algorithms for structural engineering computations. In this paper, a parallel finite element solution method is presented. The solution method proposed does not require the formation of global system equations, but computes directly the element distortions, as opposed to solving a system of nodal equations. An element or substructure is mapped on to a processor of an MIMD multiprocessing system. Each processor stores only the information relevant to the element or substructure for which the processor represents. The finite element computations can be performed in parallel, in that a processor generates the local stiffness, computes the element distortions and determines the stress-strain characteristics for the element or substructure associated with the processor.     

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.     

Large scale finite element analyses on a vector processor

Linear and nonlinear finite element software development considerations for vector processors are presented. Areas of discussion include performance measurement, data management, element level calculations and nonlinear problem solution. An example problem which demonstrates software performance is also presented.Incorporation of the methods presented in this paper can lead to finite element software which requires approximately one tenth the CPU time and as little as one-hundredth the I/O effort of conventional software.     

Implementation of an element-by-element solution algorithm for the finite element method on a coarse-grained parallel computer

An element-by-element solution algorithm for systems of equations arising in applying the finite element method in solid mechanics was implemented on the loosely coupled array of processors (lCAP) parallel computer located at IBM Kingston. The element-by-element algorithm has previously been shown to be advantageous over direct solution algorithms for large problems on sequential computers. It also has the advantage that it can be implemented in parallel on machines such as the lCAP in a relatively straightforward manner. The results show that solution speedup efficiencies of approximately 95% can be readily achieved with this method, with no indication that the speed-up efficiency drops off as more processors are added. The implementation used is applicable to other coarse-grained parallel architectures in addition to the lCAP computer.     

A parallel finite element method and its prototype implementation on a hypercube

This paper describes a parallel implementation of the finite element method on a multiprocessor computer. The proposed strategy does not require the formation of global system equations. An element or substructure is mapped onto each processor of the multiple-instruction, multiple-data multiprocessing system. Throughout the program, each processor stores only the information relevant to its element (substructure) and generates the local stiffness matrix. A parallel element (substructure) oriented conjugate gradient procedure is employed to compute the displacements. Each processor then determines the strains and stresses for its associated element (substructure). A prototype implementation of this parallel finite element program strategy on a hypercube computer is discussed. Examples for both linear and nonlinear analyses are presented.     

A parallel preconditioned conjugate gradient method using domain decomposition and inexact solvers on each subdomain

We describe a preconditioned conjugate gradient solution strategy for a multiprocessor system with message passing architecture. The preconditioner combines two techniques, a Schurcomplement preconditioning over “coupling boundaries” between the subdomains and an arbitrary choice of classic preconditioning for the inner degrees of freedom on each subdomain. All computational work on the single subdomains is carried out in parallel by distributing the subdomain data over the processor network before starting the finite element solution process (including generating the element matrices and assemblying the local subdomain stiffness matrix). The resulting spectral condition number of the entire preconditioner is estimated. For the important example of choosing MIC(0)-*-preconditioning on the subdomains, the condition number obtained is essentially the product of the two condition numbers involved.     

Large scale micro finite element analysis of 3D bone poroelasticity

In this paper, a solver for poroelasticity problems related to osteoporotic human bones is discussed. Osteoporosis is a major health problem that compromises the integrity of bones. A good understanding of the disease requires an accurate simulation of the physics. For that purpose, a finite element solver based on Biot’s consolidation equations has been developed. A mixed formulation is used to discretize the geometries taken from medical imaging. The resulting indefinite linear systems are solved by Krylov space methods supplemented by variants of Schur complement-based block preconditioners.     

基于龙格库塔法的弹塑性有限元并行计算

基于MPI集群环境对弹塑性区域分解有限元并行计算进行研究。提出了基于三阶和四阶的龙格库塔（Runge-Kutta）方法对应力-应变关系进行积分的算法。积分过程中自动调整子步大小来控制积分过程中的误差。研制了采用最小残余平滑法的子结构预处理共轭梯度并行求解算法。算法在基于工作站机群的并行环境下实现。计算结果表明：该算法具有良好的并行加速比和效率,是一种有效的并行求解算法。     

A new strategy for stress analysis using the finite element method

In this paper the authors examine the effectiveness of the Powell-Toint strategy for evaluating the Hessian of the potential energy surface of a finite element model that can be used for linear stress analysis and transient response predictions of structures. Cases for which the Powell-Toint strategy may be cost-effective with the conventional method of stress analysis are identified.     

Adaptive full domain covering meshes for parallel finite element computations

Summary  In this work, we present a new parallelization concept for adaptive finite element methods. Compared to classical domain decomposition approaches, the concept of adaptive full domain covering meshes reduces the parallel communication overhead. Furthermore, it provides an easy way to transform sequential codes into parallel software by changing only a few lines of source code.      

Buckling analysis of imperfect frames using a stochastic finite element method

A stochastic finite element method is developed for the buckling analysis of frames with random initial imperfections, uncertain sectional and material properties. The random geometrical imperfections of the frames are described by member initial crookednesses which are modeled as given initial displacement functions with amplitudes treated as random variables. The effects of the random initial geometric imperfections are formulated as a set of equivalent random nodal coordinates in the finite element discretization of the members. The mean-centered second-order perturbation technique is used to formulate the stochastic finite element method for the buckling analysis of the imperfect frames. Use of the present method is illustrated by several examples of buckling analysis of random frames. Results derived from the Monte Carlo method are also obtained for comparison.     

An explicit asynchronous step parallel computing method for finite element analysis on multi-core clusters

Engineering with Computers - The finite element analysis of complex structure often requires a refine mesh in some local domain. To reduce the computation time, an explicit asynchronous step...     

A parallel,multiscale domain decomposition method for the transient dynamic analysis of assemblies with friction

The objective of this work is to develop an efficient strategy for dynamic problems with multiple contacts. Our approach is based on the multiscale LATIN method with domain decomposition. This is a mixed method which deals simultaneously with the forces and velocities at the interfaces of the different subdomains. This strategy has already been applied successfully to a variety of static problems; here, it is extended to dynamics. First, we show how the multiscale strategy can be extended to dynamics. Then, we illustrate the capabilities of the method through a 3D academic example and the simulation of a heterogeneous material.     

Structural scale modelling by finite element method approach

The structural scale modelling by the finite element method approach is explained. This approach not only has the advantages of the finite element method but also gives insight and ready utility to the modeller. According to the scaling laws obtained by this work, a theoretical example is illustrated to show the workability of the laws. Some practical considerations/limitations of this work are also mentioned. Further extensions to this work, under progress, are also stated.     

Optimization techniques for parallel molecular dynamics using domain decomposition

In this paper we describe the implementation of a new parallelized Molecular Dynamics code for many-particle problems with short-ranged interactions. While the basic algorithms have their foundation in the fairly standard methods of domain decomposition, linked-cell pair search and Verlet pair list, we have developed some refined techniques for optimizing them. The rewards of these optimizations are a up to 45% overall improvement in the scalar performance and very good scaling behavior in the number of processors even down to a few hundred particles per processor on a CRAY T3E.The best speedup can be obtained for systems with pair forces only since then the data structures can be organized in a very simple manner. To deal with more complex situations as well, we have developed a partial replicated data scheme which is suitable to simulate many molecules consisting of many simple particles (e.g. polymer chains) for many types of short-range interactions.     

Concepts and implementation of parallel finite element analysis

The design of complex engineering systems such as advanced aircraft structures and offshore platforms requires continually increasing levels of detail in supporting analysis. The finite element method is widely used as a computational method with which to model physical systems in various engineering problems. For detailed analyses of complex designs, structural models composed of several thousands of degrees of freedom are no longer uncommon. Such design activities require large order finite element and/or finite difference models and excessive computation demands in both calculation speed and information management. The computer simulation of the nonlinear dynamic response of structures and the implementation of parallel FEM systems on a high speed multiprocessor have received considerable attention in recent years. The driving forces of these activities included the reliable simulation of automotive and aircraft crash phenomena, and the increased performance of computers. Most existing major structural analysis software systems were designed 10–20 years ago and have been optimized for current sequential computers. Such systems often are not well structured to take maximum advantage of the recent and continuing revolution in parallel vector computing capabilities. These parallel vector computer architectures not only occur in the form of large supercomputers, but are now also occurring for minicomputers and even engineering workstations. To benefit from advances in parallel computers, software must be developed which takes maximum advantage of the parallel processing feature.     

Optimum structural design with parallel finite element analysis

Structural analysis is an important part of the optimum structural design process. Therefore, extra effort should be devoted to make this part as efficient as possible. Since finite element analysis is the most powerful and widely used tool in the structural analysis field, in this paper a new method for structural optimization by parallel finite element method is presented. This method divides the original structure into several substructures and assigns each substructure to one processor. Each processor handles its finite element calculation independently with limited communication between processors. Some numerical examples on the Cray X-MP multiprocessor system with their obtained speedups are presented.