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.     

Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics

Most of the recently proposed computational methods for solving partial differential equations on multiprocessor architectures stem from the 'divide and conquer' paradigm and involve some form of domain decomposition. For those methods which also require grids of points or patches of elements, it is often necessary to explicitly partition the underlying mesh, especially when working with local memory parallel processors. In this paper, a family of cost-effective algorithms for the automatic partitioning of arbitrary two- and three-dimensional finite element and finite difference meshes is presented and discussed in view of a domain decomposed solution procedure and parallel processing. The influence of the algorithmic aspects of a solution method (implicit/explicit computations), and the architectural specifics of a multiprocessor (SIMD/MIMD, startup/transmission time), on the design of a mesh partitioning algorithm are discussed. The impact of the partitioning strategy on load balancing, operation count, operator conditioning, rate of convergence and processor mapping is also addressed. Finally, the proposed mesh decomposition algorithms are demonstrated with realistic examples of finite element, finite volume, and finite difference meshes associated with the parallel solution of solid and fluid mechanics problems on the iPSC/2 and iPSC/860 multiprocessors.     

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.     

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.     

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     

A scalable Lagrange multiplier based domain decomposition method for time-dependent problems

We present a new efficient and scalable domain decomposition method for solving implicitly linear and non-linear time-dependent problems in computational mechanics. The method is derived by adding a coarse problem to the recently proposed transient FETI substructuring algorithm in order to propagate the error globally and accelerate convergence. It is proved that in the limit for large time steps, the new method converges toward the FETI algorithm for time-independent problems. Computational results confirm that the optimal convergence properties of the time-independent FETI method are preserved in the time-dependent case. We employ an iterative scheme for solving efficiently the coarse problem on massively parallel processors, and demonstrate the effective scalability of the new transient FETI method with the large-scale finite element dynamic analysis on the Paragon XP/S and IBM SP2 systems of several diffraction grating finite element structural models. We also show that this new domain decomposition method outperforms the popular direct skyline solver. The coarse problem presented herein is applicable and beneficial to a large class of Lagrange multiplier based substructuring algorithms for time-dependent problems, including the fictitious domain decomposition method.     

Coarse/fine mesh preconditioners for the iterative solution of finite element problems

A class of preconditioners built around a coarse/fine mesh framework is presented. The proposed method involves the reconstruction of the stiffness equations using a coarse/fine mesh idealization with relative degrees-of-freedom derived from the element shape functions. This approach leads naturally to effective preconditioners for iterative solvers which only require a factorization involving coarse mesh variables. A further extension is the application of the proposed method to super-elements in conjunction with substructuring (domain decomposition) techniques. The derivation of the coarse/fine mesh discretization via the use of transformation matrices, allows a straightforward implementation of the proposed techniques (as well as multigrid type procedures) within an existing finite element system.     

Simultaneous FETI and block FETI: Robust domain decomposition with multiple search directions

Domain decomposition methods often exhibit very poor performance when applied to engineering problems with large heterogeneities. In particular, for heterogeneities along domain interfaces, the iterative techniques to solve the interface problem are lacking an efficient preconditioner. Recently, a robust approach, named finite element tearing and interconnection (FETI)–generalized eigenvalues in the overlaps (Geneo), was proposed where troublesome modes are precomputed and deflated from the interface problem. The cost of the FETI–Geneo is, however, high. We propose in this paper techniques that share similar ideas with FETI–Geneo but where no preprocessing is needed and that can be easily and efficiently implemented as an alternative to standard domain decomposition methods. In the block iterative approaches presented in this paper, the search space at every iteration on the interface problem contains as many directions as there are domains in the decomposition. Those search directions originate either from the domain‐wise preconditioner (in the simultaneous FETI method) or from the block structure of the right‐hand side of the interface problem (block FETI). We show on two‐dimensional structural examples that both methods are robust and provide good convergence in the presence of high heterogeneities, even when the interface is jagged or when the domains have a bad aspect ratio. The simultaneous FETI was also efficiently implemented in an optimized parallel code and exhibited excellent performance compared with the regular FETI method. Copyright © 2015 John Wiley & Sons, Ltd.     

A coupling strategy for adaptive local refinement in space and time with a fixed global model in explicit dynamics

In dynamics, domain decomposition methods (DDMs) enable one to use different spatial and temporal discretizations depending on the physical phenomenon being taken into account. Thus, DDMs provide the analyst with key tools for dealing with problems in which phenomena occur on different temporal and spatial scales. This paper focuses on a less intrusive variation of this type of method which enables the global (industrial) mesh to remain unchanged while the local problem is being refined in space and in time where needed. This property is particularly useful in the case of a local problem whose localization evolves rapidly with time, as is the case for delamination. The downside is that the technique is iterative. The method is presented in the context of linear explicit dynamics, but, as with domain decomposition, its extension to other integration schemes and to nonlinear problems should be possible.     

Adaptive sparse grid based HOPGD: Toward a nonintrusive strategy for constructing space‐time welding computational vademecum

Simulation‐based engineering usually needs the construction of computational vademecum to take into account the multiparametric aspect. One example concerns the optimization and inverse identification problems encountered in welding processes. This paper presents a nonintrusive a posteriori strategy for constructing quasi‐optimal space‐time computational vademecum using the higher‐order proper generalized decomposition method. Contrary to conventional tensor decomposition methods, based on full grids (eg, parallel factor analysis/higher‐order singular value decomposition), the proposed method is adapted to sparse grids, which allows an efficient adaptive sampling in the multidimensional parameter space. In addition, a residual‐based accelerator is proposed to accelerate the higher‐order proper generalized decomposition procedure for the optimal aspect of computational vademecum. Based on a simplified welding model, different examples of computational vademecum of dimension up to 6, taking into account both geometry and material parameters, are presented. These vademecums lead to real‐time parametric solutions and can serve as handbook for engineers to deal with optimization, identification, or other problems related to repetitive task.     

Conference diary

We present a method that has been developed for the construction of grids suitable for a large class of Computational Fluid Dynamics (CFD) solvers. Three independent steps are considered: a multidomain generation, an optimization and an adaptation. The first step handles the complexity of the three-dimensional domain to be meshed and is able to perform an algebraic construction of the grid points within a multidomain topology; any decomposition can be considered and analysed by the algorithm. The second step is able to optimize a mesh with respect to a quality measure defined in terms of cell deformation; a conjugate gradient algorithm drives the nodes up to an equilibrium position that realizes the minimum of a mesh energy quantity. The final step handles the physics of the problem and moves the nodes in order to refine the mesh where anything of interest takes place, while preserving its good metric quality. The three steps have been implemented independently and successfully, as shown by the examples presented.     

Robust and efficient domain decomposition preconditioners for adaptive hp finite element approximations of linear elasticity with and without discontinuous coefficients

Adaptive finite element methods (FEM) generate linear equation systems that require dynamic and irregular patterns of storage, access, and computation, making their parallelization difficult. Additional difficulties are generated for problems in which the coefficients of the governing partial differential equations have large discontinuities. We describe in this paper the development of a set of iterative substructuring based solvers and domain decomposition preconditioners with an algebraic coarse‐grid component that address these difficulties for adaptive hp approximations of linear elasticity with both homogeneous and inhomogeneous material properties. Our solvers are robust and efficient and place no restrictions on the mesh or partitioning. Copyright © 2003 John Wiley & Sons, Ltd.     

LayTracks: a new approach to automated geometry adaptive quadrilateral mesh generation using medial axis transform

A new mesh generation algorithm called ‘LayTracks’, to automatically generate an all quad mesh that is adapted to the variation of geometric feature size in the domain is described. LayTracks combines the merits of two popular direct techniques for quadrilateral mesh generation—quad meshing by decomposition and advancing front quad meshing. While the MAT has been used for the domain decomposition before, this is the first attempt to use the MAT, for the robust subdivision of a complex domain into a well defined sub‐domain called ‘Tracks’, for terminating the advancing front of the mesh elements without complex interference checks and to use radius function for providing sizing function for adaptive meshing. The process of subdivision of a domain is analogous to, formation of railway tracks by laying rails on the ground. Each rail starts from a node on the boundary and propagates towards the medial axis (MA) and then from the MA towards the boundary. Quadrilateral elements are then obtained by placing nodes on these rails and connecting them inside each track, formed by adjacent rails. The algorithm has been implemented and tested on some typical geometries and the quality of the output mesh obtained are presented. Extension of this technique to all hexahedral meshing is discussed. Copyright © 2004 John Wiley & Sons, Ltd.     

A meshless method for conjugate heat transfer problems

Mesh reduction methods such as boundary element methods, method of fundamental solutions, and spectral methods all lead to fully populated matrices. This poses serious challenges for large-scale three-dimensional problems due to storage requirements and iterative solution of a large set of non-symmetric equations. Researchers have developed several approaches to address this issue including the class of fast-multipole techniques, use of wavelet transforms, and matrix decomposition. In this paper, we develop a domain decomposition, or the artificial sub-sectioning technique, along with a region-by-region iteration algorithm particularly tailored for parallel computation to address the coefficient matrix issue. The meshless method we employ is based on expansions using radial-basis functions (RBFs).An efficient physically based procedure provides an effective initial guess of the temperatures along the sub-domain interfaces. The iteration process converges very efficiently, offers substantial savings in memory, and features superior computational efficiency. The meshless iterative domain decomposition technique is ideally suited for parallel computation. We discuss its implementation under MPI standards on a small Windows XP PC cluster. Numerical results reveal the domain decomposition meshless methods produce accurate temperature predictions while requiring a much-reduced effort in problem preparation in comparison to other traditional numerical methods.     

Obtaining smooth mesh transitions using vertex optimization

Mesh optimization has proven to be an effective way to improve mesh quality for arbitrary Lagrangian Eulerian (ALE) simulations. To date, however, most of the focus has been on improving the geometric shape of individual elements, and these methods often do not result in smooth transitions in element size or aspect ratio across groups of elements. We present an extension to the mean ratio optimization that addresses this problem and yields smooth transitions within regions and across regions in the ALE simulation. While this method is presented in the context of ALE simulations, it is applicable to a wider set of applications that require mesh improvement, including the mesh generation process. Published in 2007 by 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.     

Mesh refinement and iterative solution methods for finite element computations

Global and element residuals are introduced to determine a posteriori, computable, error bounds for finite element computations on a given mesh. The element residuals provide a criterion for determining where a finite element mesh requires refinement. This indicator is implemented in an algorithm in a finite element research program. There it is utilized to automatically refine the mesh for sample two-point problems exhibiting boundary layer and interior layer solutions. Results for both linear and nonlinear problems are presented. An important aspect of this investigation concerns the use of adaptive refinement in conjunction with iterative methods for system solution. As the mesh is being enriched through the refinement process, the solution on a given mesh provides an accurate starting iterate for the next mesh, and so on. A wide range of iterative methods are examined in a feasibility study and strategies for interweaving refinement and iteration are compared.     

A sequential approximation method using neural networks for engineering design optimization problems

There are three characteristics in engineering design optimization problems: (1) the design variables are often discrete physical quantities; (2) the constraint functions often cannot be expressed analytically in terms of design variables; (3) in many engineering design applications, critical constraints are often ‘pass–fail’, ‘0–1’ type binary constraints. This paper presents a sequential approximation method specifically for engineering optimization problems with the three characteristics. In this method a back-propagation neural network is trained to simulate a rough map of the feasible domain formed by the constraints using a few representative training data. A training data point consists of a discrete design point and whether this design point is feasible or infeasible. Function values of the constraints are not required. A search algorithm then searches for the optimal point in the feasible domain simulated by the neural network. This new design point is checked against the true constraints to see whether it is feasible, and is then added to the training set. The neural network is trained again with this added information, in the hope that the network will better simulate the boundary of the feasible domain of the true optimization problem. Then a further search is made for the optimal point in this new approximated feasible domain. This process continues in an iterative manner until the approximate model locates the same optimal point in consecutive iterations. A restart strategy is also employed so that the method may have a better chance to reach a global optimum. Design examples with large discrete design spaces and implicit constraints are solved to demonstrate the practicality of this method.     

Anisotropic mixed finite elements for elasticity

In this paper, we present a family of mixed finite elements, which are suitable for the discretization of slim domains. The displacement space is chosen as Nédélec's space of tangential continuous elements, whereas the stress is approximated by normal–normal continuous symmetric tensor‐valued finite elements. We show stability of the system on a slim domain discretized by a tensor product mesh, where the constant of stability does not depend on the aspect ratio of the discretization. We give interpolation operators for the finite element spaces, and thereby obtain optimal order a priori error estimates for the approximate solution. All estimates are independent of the aspect ratio of the finite elements. Copyright © 2011 John Wiley & Sons, Ltd.