Automatic local refinement for irregular rectangular meshes

The use of local mesh refinements for the generation of meshes for the finite element or finite difference methods is studied. A class of rectangular meshes which admit restricted local refinements, referred to as irregular rectangular meshes, is introduced and its representation discussed. Properties of algorithms for mesh refinements are discussed from the viewpoints of termination with a mesh in the specified class, memory utilization, symmetry and fragmentation of the mesh.     

Performance study of the domain decomposition method with direct equation solver for parallel finite element analysis

A parallel performance of the domain decomposition method with directLDU algorithm of condensation and solution is studied. Typical subdomains arising after division of a square domain are considered, and operation count equations for all steps of the numerical procedure are derived. The parallel efficiency model is developed using operation count equations and message passing estimates. It is shown how to achieve interprocessor load balancing by partitioning a domain into unequal subdomains. The evaluation of the parallel efficiency model and performance studies for a square finite element domain are performed on the IBM SP2 computer with 4, 6 and 8 processor nodes. It is found that proper load balancing of the domain decomposition algorithm with direct solution of equation systems provides acceptable parallel efficiency for multiprocessor computers: 95% for the 6-processor configuration and 85% for the 8-processor configuration.     

A neural network graph partitioning procedure for grid‐based domain decomposition

This paper describes a neural network graph partitioning algorithm which partitions unstructured finite element/volume meshes as a precursor to a parallel domain decomposition solution method. The algorithm works by first constructing a coarse graph approximation using an automatic graph coarsening method. The coarse graph is partitioned and the results are interpolated onto the original graph to initialize an optimization of the graph partition problem. In practice, a hierarchy of (usually more than two) graphs are used to help obtain the final graph partition. A mean field theorem neural network is used to perform all partition optimization. The partitioning method is applied to graphs derived from unstructured finite element meshes and in this context it can be viewed as a multi‐grid partitioning method. Copyright © 1999 John Wiley & Sons, Ltd.     

Optimized partitioning of unstructured finite element meshes

We address the problem of automatic partitioning of unstructured finite element meshes in the context of parallel numerical algorithms based on domain decomposition. A two-step approach is proposed, which combines a direct partitioning scheme with a non-deterministic procedure of combinatorial optimization. In contrast with previously published experiments with non-deterministic heuristics, the optimization step is shown to produce high-quality decompositions at a reasonable compute cost. We also show that the optimization approach can accommodate complex topological constraints and minimization objectives. This is illustrated by considering the particular case of topologically one-dimensional partitions, as well as load balancing of frontal subdomain solvers. Finally, the optimization procedure produces, in most cases, decompositions endowed with geometrically smooth interfaces. This contrasts with available partitioning schemes, and is crucial to some modern numerical techniques based on domain decomposition and a Lagrange multiplier treatment of the interface conditions.     

The domain composition method applied to Poisson's equation in two dimensions

Domain composition, a recently described method for formulating continuum field problems, removes certain restrictions on the construction of finite element models such that it is possible to solve a finite element problem without using a global compatible mesh. The domain composition method couples or otherwise constrains meshes in local regions to obtain a solution equivalent to that produced by conventional finite element methods. In particular, the domain composition method enables finite element models to be formulated with overlapping elements. Several advantages come from this, including an ability to automatically generate a finite element model from a solid geometric model, an ability to use a variety of element types in a single finite element model and an ability to exactly match element boundaries to the local geometry. This paper shows in detail a finite element formulation of Poisson's equation using domain composition and presents certain key algorithms that incorporate the domain composition method into well-established finite element procedures.     

Parallel/vector improvements of the frontal method

We present, discuss, and report on the performance of two combined parallel/vector frontal algorithms which have been incorporated in a production finite element code. Two parallelization strategies are described. The first approach is algebra driven and is recommended for the solution of problems with a large bandwidth on a coarse grain configuration. The second strategy is targeted for finer grain systems; it blends the first one with a substructuring technique that is based on a careful partitioning of the finite element mesh into a series of subdomains. Using only 4 IBM 3090/VF processors, the proposed algorithms are shown to deliver speed-ups as high as 17 with respect to a serial non-vectorized frontal solver.     

A parallel implicit/explicit hybrid time domain method for computational electromagnetics

The numerical solution of Maxwell's curl equations in the time domain is achieved by combining an unstructured mesh finite element algorithm with a cartesian finite difference method. The practical problem area selected to illustrate the application of the approach is the simulation of three‐dimensional electromagnetic wave scattering. The scattering obstacle and the free space region immediately adjacent to it are discretized using an unstructured mesh of linear tetrahedral elements. The remainder of the computational domain is filled with a regular cartesian mesh. These two meshes are overlapped to create a hybrid mesh for the numerical solution. On the cartesian mesh, an explicit finite difference method is adopted and an implicit/explicit finite element formulation is employed on the unstructured mesh. This approach ensures that computational efficiency is maintained if, for any reason, the generated unstructured mesh contains elements of a size much smaller than that required for accurate wave propagation. A perfectly matched layer is added at the artificial far field boundary, created by the truncation of the physical domain prior to the numerical solution. The complete solution approach is parallelized, to enable large‐scale simulations to be effectively performed. Examples are included to demonstrate the numerical performance that can be achieved. Copyright © 2009 John Wiley & Sons, Ltd.     

Mesh partitioning for implicit computations via iterative domain decomposition: Impact and optimization of the subdomain aspect ratio

Optimal domain decomposition methods have emerged as powerful iterative algorithms for parallel implicit computations. Their key preprocessing step is mesh partitioning, where research has focused so far on the automatic generation of load-balanced subdomains with minimum interface nodes. In this paper, we emphasize the importance of the subdomain aspect ratio as a mesh partitioning factor, and highlight its impact on the convergence rate of an optimal domain decomposition based iterative method. We also present a fast optimization algorithm for improving the aspect ratio of existing mesh partitions, and illustrate it with several examples from fluid dynamics and structural mechanics applications. For a stiffened shell problem decomposed by the optimal Recursive Spectral Bisection scheme and solved by the FETI method, this optimization algorithm is shown to improve the solution time by a factor equal to 1·54 and to restore numerical scalability.     

Exploiting semantics of temporal multi‐scale methods to optimize multi‐level mesh partitioning

Multi‐scale problems are often solved by decomposing the problem domain into multiple subdomains, solving them independently using different levels of spatial and temporal refinement, and coupling the subdomain solutions back to obtain the global solution. Most commonly, finite elements are used for spatial discretization, and finite difference time stepping is used for time integration. Given a finite element mesh for the global problem domain, the number of possible decompositions into subdomains and the possible choices for associated time steps is exponentially large, and the computational costs associated with different decompositions can vary by orders of magnitude. The problem of finding an optimal decomposition and the associated time discretization that minimizes computational costs while maintaining accuracy is nontrivial. Existing mesh partitioning tools, such as METIS, overlook the constraints posed by multi‐scale methods and lead to suboptimal partitions with a high performance penalty. We present a multi‐level mesh partitioning approach that exploits domain‐specific knowledge of multi‐scale methods to produce nearly optimal mesh partitions and associated time steps automatically. Results show that for multi‐scale problems, our approach produces decompositions that outperform those produced by state‐of‐the‐art partitioners like METIS and even those that are manually constructed by domain experts. Copyright © 2017 John Wiley & Sons, Ltd.     

A class of parallel multiple‐front algorithms on subdomains

A class of parallel multiple‐front solution algorithms is developed for solving linear systems arising from discretization of boundary value problems and evolution problems. The basic substructuring approach and frontal algorithm on each subdomain are first modified to ensure stable factorization in situations where ill‐conditioning may occur due to differing material properties or the use of high degree finite elements (p methods). Next, the method is implemented on distributed‐memory multiprocessor systems with the final reduced (small) Schur complement problem solved on a single processor. A novel algorithm that implements a recursive partitioning approach on the subdomain interfaces is then developed. Both algorithms are implemented and compared in a least‐squares finite‐element scheme for viscous incompressible flow computation using h‐ and p‐finite element schemes. Copyright © 2003 John Wiley & Sons, Ltd.     

A‐scalability and an integrated computational technology and framework for non‐linear structural dynamics. Part 2: Implementation aspects and parallel performance results

An integrated framework and computational technology is described that addresses the issues to foster absolute scalability (A‐scalability) of the entire transient duration of the simulations of implicit non‐linear structural dynamics of large scale practical applications on a large number of parallel processors. Whereas the theoretical developments and parallel formulations were presented in Part 1, the implementation, validation and parallel performance assessments and results are presented here in Part 2 of the paper. Relatively simple numerical examples involving large deformation and elastic and elastoplastic non‐linear dynamic behaviour are first presented via the proposed framework for demonstrating the comparative accuracy of methods in comparison to available experimental results and/or results available in the literature. For practical geometrically complex meshes, the A‐scalability of non‐linear implicit dynamic computations is then illustrated by employing scalable optimal dissipative zero‐order displacement and velocity overshoot behaviour time operators which are a subset of the generalized framework in conjunction with numerically scalable spatial domain decomposition methods and scalable graph partitioning techniques. The constant run times of the entire simulation of ‘fixed‐memory‐use‐per‐processor’ scaling of complex finite element mesh geometries is demonstrated for large scale problems and large processor counts on at least 1024 processors. Copyright © 2003 John Wiley & Sons, Ltd.     

An alternative pseudoperipheral node finder for resequencing schemes

Many resequencing algorithms for reducing the bandwidth, profile and wavefront of sparse symmetric matrices have been published. In finite element applications, the sparsity of a matrix is related to the nodal ordering of the finite element mesh. Some of the most successful algorithms, which are based on graph theory, require a pair of starting pseudoperipheral nodes. These nodes, located at nearly maximal distance apart, are determined using heuristic schemes. This paper presents an alternative pseadoperipheral node finder, which is based on the algorithm developed by Gibbs, Poole and Stockmeyer. This modified scheme is suitable for nodal reordering of finite meshes and provides more consistency in the effective selection of the starting nodes in problems where the selection becomes arbitrary due to the number of candidates for these starting nodes. This case arises, in particular, for square meshes. The modified scheme was implemented in Gibbs-Poole-Stockmeyer, Gibbs-King and Sloan algorithms. Test problems of these modified algorithms include: (1) Everstine's 30 benchmark problems; (2) sets of square, rectangular and annular (cylindrical) finite element meshes with quadrilateral and triangular elements; and (3) additional examples originating from mesh refinement schemes. The results demonstrate that the modifications to the original algorithms contribute to the improvement of the reliability of all the resequencing algorithms tested herein for the nodal reordering of finite element meshes.     

A parallel two‐level domain decomposition based one‐shot method for shape optimization problems

A two‐level domain decomposition method is introduced for general shape optimization problems constrained by the incompressible Navier–Stokes equations. The optimization problem is first discretized with a finite element method on an unstructured moving mesh that is implicitly defined without assuming that the computational domain is known and then solved by some one‐shot Lagrange–Newton–Krylov–Schwarz algorithms. In this approach, the shape of the domain, its corresponding finite element mesh, the flow fields and their corresponding Lagrange multipliers are all obtained computationally in a single solve of a nonlinear system of equations. Highly scalable parallel algorithms are absolutely necessary to solve such an expensive system. The one‐level domain decomposition method works reasonably well when the number of processors is not large. Aiming for machines with a large number of processors and robust nonlinear convergence, we introduce a two‐level inexact Newton method with a hybrid two‐level overlapping Schwarz preconditioner. As applications, we consider the shape optimization of a cannula problem and an artery bypass problem in 2D. Numerical experiments show that our algorithm performs well on a supercomputer with over 1000 processors for problems with millions of unknowns. Copyright © 2014 John Wiley & Sons, Ltd.     

Iterative mesh partitioning optimization for parallel nonlinear dynamic finite element analysis with direct substructuring

 This work presents a novel iterative approach for mesh partitioning optimization to promote the efficiency of parallel nonlinear dynamic finite element analysis with the direct substructure method, which involves static condensation of substructures' internal degrees of freedom. The proposed approach includes four major phases – initial partitioning, substructure workload prediction, element weights tuning, and partitioning results adjustment. The final three phases are performed iteratively until the workloads among the substructures are balanced reasonably. A substructure workload predictor that considers the sparsity and ordering of the substructure matrix is used in the proposed approach. Several numerical experiments conducted herein reveal that the proposed iterative mesh partitioning optimization often results in a superior workload balance among substructures and reduces the total elapsed time of the corresponding parallel nonlinear dynamic finite element analysis. Received 22 August 2001 / Accepted 20 January 2002     

The application of scalable distributed memory computers to the finite element modeling of electromagnetic scattering

Large-scale parallel computation can be an enabling resource in many areas of engineering and science if the parallel simulation algorithm attains an appreciable fraction of the machine peak performance, and if undue cost in porting the code or in developing the code for the parallel machine is not incurred. The issue of code parallelization is especially significant when considering unstructured mesh simulations. The unstructured mesh models considered in this paper result from a finite element simulation of electromagnetic fields scattered from geometrically complex objects (either penetrable or impenetrable.) The unstructured mesh must be distributed among the processors, as must the resultant sparse system of linear equations. Since a distributed memory architecture does not allow direct access to the irregularly distributed unstructured mesh and sparse matrix data, partitioning algorithms not needed in the sequential software have traditionally been used to efficiently spread the data among the processors. This paper presents a new method for simulating electromagnetic fields scattered from complex objects; namely, an unstructured finite element code that does not use traditional mesh partitioning algorithms. © 1998 This paper was produced under the auspices of the U.S. Government and it is therfore not subject to copyright in the U.S.     

A two-scale approach for the analysis of propagating three-dimensional fractures

This paper presents a generalized finite element method (GFEM) for crack growth simulations based on a two-scale decomposition of the solution—a smooth coarse-scale component and a singular fine-scale component. The smooth component is approximated by discretizations defined on coarse finite element meshes. The fine-scale component is approximated by the solution of local problems defined in neighborhoods of cracks. Boundary conditions for the local problems are provided by the available solution at a crack growth step. The methodology enables accurate modeling of 3-D propagating cracks on meshes with elements that are orders of magnitude larger than those required by the FEM. The coarse-scale mesh remains unchanged during the simulation. This, combined with the hierarchical nature of GFEM shape functions, allows the recycling of the factorization of the global stiffness matrix during a crack growth simulation. Numerical examples demonstrating the approximating properties of the proposed enrichment functions and the computational performance of the methodology are presented.     

Parallel implementation of the finite element method using compressed data structures

This paper presents a parallel implementation of the finite element method designed for coarse-grain distributed memory architectures. The MPI standard is used for message passing and tests are run on a PC cluster and on an SGI Altix 350. Compressed data structures are employed to store the coefficient matrix and obtain iterative solutions, based on Krylov methods, in a subdomain-by-subdomain approach. Two mesh partitioning schemes are compared: non-overlapping and overlapping. The pros and cons of these partitioning methods are discussed. Numerical examples of symmetric and non-symmetric problems in two and three dimensions are presented.     

Shape design sensitivities improvement using convected unstructured meshes

This paper focuses on various forms of direct differentiation methods for design sensitivity computation in the shape optimisation of continuum structures and the role of convected meshes on the accuracy of the sensitivities. A Pseudo-Analytical Sensitivity Analysis (P-ASA) method is presented and tested. In this method the response analysis component uses unstructured finite element meshes and the sensitivity algorithm entails shape-perturbation for each design variable. A material point is convected during a change of shape and the design sensitivities are therefore intrinsically associated with the mesh-sensitivities of the finite element discretization. Such mesh sensitivities are obtained using a very efficient boundary element point-tracking analysis of an affine notional underlying elastic domain. All of the differentiation, with respect to shape variables, is done exactly except for the case of mesh-sensitivities: hence the method is almost analytical. In contrast to many other competing methods, the P-ASA method is, by definition, independent of perturbation step-size, making it particularly robust. Furthermore, the sensitivity accuracy improves with mesh refinement. The boundary element point-tracking method is also combined with two popular methods of sensitivity computation, namely the global finite difference method and the semi-analytical method. Increases in accuracy and perturbation range are observed for both methods.     

Parallel asynchronous variational integrators

This paper presents a scalable parallel variational time integration algorithm for nonlinear elastodynamics with the distinguishing feature of allowing each element in the mesh to have a possibly different time step. Furthermore, the algorithm is obtained from a discrete variational principle, and hence it is termed parallel asynchronous variational integrator (PAVI). The underlying variational structure grants it outstanding conservation properties. Based on a domain decomposition strategy, PAVI combines a careful scheduling of computations with fully asynchronous communications to provide a very efficient methodology for finite element models with even mild distributions of time step sizes. Numerical tests are shown to illustrate PAVI's performance on both slow and fast networks, showing scalability properties similar to the best parallel explicit synchronous algorithms, with lower execution time. Finally, a numerical example in which PAVI needs ≈100 times less computing than an explicit synchronous algorithm is shown. Copyright © 2006 John Wiley & Sons, Ltd.     

The generation of hexahedral meshes for assembly geometry: survey and progress

The finite element method is being used today to model component assemblies in a wide variety of application areas, including structural mechanics, fluid simulations, and others. Generating hexahedral meshes for these assemblies usually requires the use of geometry decomposition, with different meshing algorithms applied to different regions. While the primary motivation for this approach remains the lack of an automatic, reliable all‐hexahedral meshing algorithm, requirements in mesh quality and mesh configuration for typical analyses are also factors. For these reasons, this approach is also sometimes required when producing other types of unstructured meshes. This paper will review progress to date in automating many parts of the hex meshing process, which has halved the time to produce all‐hex meshes for large assemblies. Particular issues which have been exposed due to this progress will also be discussed, along with their applicability to the general unstructured meshing problem. Published in 2001 by John Wiley & Sons, Ltd.