A fast implementation of the FETI‐DP method: FETI‐DP‐RBS‐LNA and applications on large scale problems with localized non‐linearities

As parallel and distributed computing gradually becomes the computing standard for large scale problems, the domain decomposition method (DD) has received growing attention since it provides a natural basis for splitting a large problem into many small problems, which can be submitted to individual computing nodes and processed in a parallel fashion. This approach not only provides a method to solve large scale problems that are not solvable on a single computer by using direct sparse solvers but also gives a flexible solution to deal with large scale problems with localized non‐linearities. When some parts of the structure are modified, only the corresponding subdomains and the interface equation that connects all the subdomains need to be recomputed. In this paper, the dual–primal finite element tearing and interconnecting method (FETI‐DP) is carefully investigated, and a reduced back‐substitution (RBS) algorithm is proposed to accelerate the time‐consuming preconditioned conjugate gradient (PCG) iterations involved in the interface problems. Linear–non‐linear analysis (LNA) is also adopted for large scale problems with localized non‐linearities based on subdomain linear–non‐linear identification criteria. This combined approach is named as the FETI‐DP‐RBS‐LNA algorithm and demonstrated on the mechanical analyses of a welding problem. Serial CPU costs of this algorithm are measured at each solution stage and compared with that from the IBM Watson direct sparse solver and the FETI‐DP method. The results demonstrate the effectiveness of the proposed computational approach for simulating welding problems, which is representative of a large class of three‐dimensional large scale problems with localized non‐linearities. Copyright © 2005 John Wiley & Sons, Ltd.     

Iterative solution of large‐scale acoustic scattering problems with multiple right hand‐sides by a domain decomposition method with Lagrange multipliers

An extension of the FETI‐H method is designed for the solution of acoustic scattering problems with multiple right‐hand sides. A new local pre‐conditioning of this domain decomposition method is also presented. The potential of the resulting iterative solver is demonstrated by numerical experiments for two‐dimensional problems with high wavenumbers, as many as 2.5 million complex degrees of freedom, and a sweep on the angle of the incident wave. Preliminary results for a three‐dimensional submarine problem are also included. The FETI‐H method, whose numerical scalability with respect to the mesh and subdomain sizes was previously established, is shown here to be also numerically scalable with respect to the wavenumber. Copyright © 2001 John Wiley & Sons, Ltd.     

A Parallel Strategy for the Logical‐probabilistic Calculus‐based Method to Calculate Two‐terminal Reliability

The theory of network reliability has been applied to many complicated network structures, such as computer and communication networks, piping systems, electricity networks, and traffic networks. The theory is used to evaluate the operational performance of networks that can be modeled by probabilistic graphs. Although evaluating network reliability is an Non‐deterministic Polynomial‐time hard problem, numerous solutions have been proposed. However, most of them are based on sequential computing, which under‐utilizes the benefits of multi‐core processor architectures. This paper addresses this limitation by proposing an efficient strategy for calculating the two‐terminal (terminal‐pair) reliability of a binary‐state network that uses parallel computing. Existing methods are analyzed. Then, an efficient method for calculating terminal‐pair reliability based on logical‐probabilistic calculus is proposed. Finally, a parallel version of the proposed algorithm is developed. This is the first study to implement an algorithm for estimating terminal‐pair reliability in parallel on multi‐core processor architectures. The experimental results show that the proposed algorithm and its parallel version outperform an existing sequential algorithm in terms of execution time. Copyright © 2015 John Wiley & Sons, Ltd.     

A fast,memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices

In this article, we introduce a fast, memory efficient and robust sparse preconditioner that is based on a direct factorization scheme for sparse matrices arising from the finite‐element discretization of elliptic partial differential equations. We use a fast (but approximate) multifrontal approach as a preconditioner and use an iterative scheme to achieve a desired accuracy. This approach combines the advantages of direct and iterative schemes to arrive at a fast, robust, and accurate preconditioner. We will show that this approach is faster (～2×) and more memory efficient (～2–3×) than a conventional direct multifrontal approach. Furthermore, we will demonstrate that this preconditioner is both faster and more effective than other preconditioners such as the incomplete LU preconditioner. Specific speedups depend on the matrix size and improve as the size of the matrix increases. The preconditioner can be applied to both structured and unstructured meshes in a similar manner. We build on our previous work and utilize the fact that dense frontal and update matrices, in the multifrontal algorithm, can be represented as hierarchically off‐diagonal low‐rank matrices. Using this idea, we replace all large dense matrix operations in the multifrontal elimination process with O(N) hierarchically off‐diagonal low‐rank operations to arrive at a faster and more memory efficient factorization scheme. We then use this direct factorization method at low accuracies as a preconditioner and apply it to various real‐life engineering test cases. Copyright © 2016 John Wiley & Sons, Ltd.     

An algorithm for the matrix‐free solution of quasistatic frictional contact problems

A contact enforcement algorithm has been developed for matrix‐free quasistatic finite element techniques. Matrix‐free (iterative) solution algorithms such as non‐linear conjugate gradients (CG) and dynamic relaxation (DR) are desirable for large solid mechanics applications where direct linear equation solving is prohibitively expensive, but in contrast to more traditional Newton–Raphson and quasi‐Newton iteration strategies, the number of iterations required for convergence is typically of the same order as the number of degrees of freedom of the model. It is therefore crucial that each of these iterations be inexpensive to per‐form, which is of course the essence of a matrix free method. In applying such methods to contact problems we emphasize here two requirements: first, that the treatment of the contact should not make an average equilibrium iteration considerably more expensive; and second, that the contact constraints should be imposed in such a way that they do not introduce spurious energy that acts against the iterative solver. These practical concerns are utilized to develop an iterative technique for accurate constraint enforcement that is suitable for non‐linear conjugate gradient and dynamic relaxation iterative schemes. Copyright © 1999 John Wiley & Sons, Ltd.     

A flow‐aligning algorithm for convection‐dominated problems

This paper proposes and studies an algorithm for aligning a triangulation with a given convection field. Approximate solutions of convection‐dominated problems on flow‐aligned meshes typically have sharper internal layers, less over and undershooting and higher accuracy. The algorithm we present can be imported easily into any 2D finite element solver, does not change the number of meshpoints, and can improve solution quality quite dramatically. This improvement in solution quality on the flow‐aligned triangulation is illustrated for both the usual Galerkin method and the streamline‐diffusion method. Copyright © 1999 John Wiley & Sons, Ltd.     

Shifted FSAI preconditioners for the efficient parallel solution of non‐linear groundwater flow models

The present paper investigates the performance of a shifted factorized sparse approximate inverse as a parallel preconditioner for the iterative solution to the linear systems arising in the finite element discretization of non‐linear groundwater flow models. The shift strategy is based on an inexpensive preconditioner update exploiting the structure of the coefficient matrix. The proposed algorithm is experimented with in the parallel simulation of a large‐scale real multi‐aquifer system characterized by a stochastic distribution of the hydraulic conductivity. The numerical results show that the shifted factorized sparse approximate inverse algorithm may yield an overall computational gain up to 300% with respect to the non‐shifted scheme with an excellent parallel efficiency. Copyright © 2011 John Wiley & Sons, Ltd.     

A monolithic geometric multigrid solver for fluid‐structure interactions in ALE formulation

We present a monolithic geometric multigrid solver for fluid‐structure interaction problems in Arbitrary Lagrangian Eulerian coordinates. The coupled dynamics of an incompressible fluid with nonlinear hyperelastic solids gives rise to very large and ill‐conditioned systems of algebraic equations. Direct solvers usually are out of question because of memory limitations, and standard coupled iterative solvers are seriously affected by the bad condition number of the system matrices. The use of partitioned preconditioners in Krylov subspace iterations is an option, but the convergence will be limited by the outer partitioning. Our proposed solver is based on a Newton linearization of the fully monolithic system of equations, discretized by a Galerkin finite element method. Approximation of the linearized systems is based on a monolithic generalized minimal residual method iteration, preconditioned by a geometric multigrid solver. The special character of fluid‐structure interactions is accounted for by a partitioned scheme within the multigrid smoother only. Here, fluid and solid field are segregated as Dirichlet–Neumann coupling. We demonstrate the efficiency of the multigrid iteration by analyzing 2d and 3d benchmark problems. While 2d problems are well manageable with available direct solvers, challenging 3d problems highly benefit from the resulting multigrid solver. Copyright © 2015 John Wiley & Sons, Ltd.     

An efficient out‐of‐core multifrontal solver for large‐scale unsymmetric element problems

In many applications where the efficient solution of large sparse linear systems of equations is required, a direct method is frequently the method of choice. Unfortunately, direct methods have a potentially severe limitation: as the problem size grows, the memory needed generally increases rapidly. However, the in‐core memory requirements can be limited by storing the matrix and its factors externally, allowing the solver to be used for very large problems. We have designed a new out‐of‐core package for the large sparse unsymmetric systems that arise from finite‐element problems. The code, which is called HSL _MA78 , implements a multifrontal algorithm and achieves efficiency through the use of specially designed code for handling the input/output operations and efficient dense linear algebra kernels. These kernels, which are available as a separate package called HSL _MA74 , use high‐level BLAS to perform the partial factorization of the frontal matrices and offer both threshold partial and rook pivoting. In this paper, we describe the design of HSL _MA78 and explain its user interface and the options it offers. We also describe the algorithms used by HSL _MA74 and illustrate the performance of our new codes using problems from a range of practical applications. Copyright © 2008 John Wiley & Sons, Ltd.     

A BEM‐level set domain‐decomposition strategy for non‐linear and fragmented interfacial flows

A domain‐decomposition algorithm has been developed to handle two‐phase flows with large deformation, breaking and fragmentation of the interface. The strategy couples a boundary element method with a Navier–Stokes solver combined with a level‐set technique for the tracking of the interface. The former is used in the fluid region where the interface can be modelled as a smooth surface. In the rest of the domain the field solver is applied. This results in an efficient and accurate method. In this paper, the features of the used strategy are described and the challenges connected with the coupling are deeply discussed. The numerical investigation highlighted the importance of a proper rational study when CFD methods are considered. In the present case, a crucial aspect is represented by the domain‐composition step, that is when the information from one solver to the other have to be properly reconstructed and made consistent with the receiver sub‐domain. Copyright © 2006 John Wiley & Sons, Ltd.     

Strict lower bounds with separation of sources of error in non‐overlapping domain decomposition methods

This article deals with the computation of guaranteed lower bounds of the error in the framework of finite element and domain decomposition methods. In addition to a fully parallel computation, the proposed lower bounds separate the algebraic error (due to the use of a domain decomposition iterative solver) from the discretization error (due to the finite element), which enables the steering of the iterative solver by the discretization error. These lower bounds are also used to improve the goal‐oriented error estimation in a substructured context. Assessments on 2D static linear mechanic problems illustrate the relevance of the separation of sources of error and the lower bounds' independence from the substructuring. We also steer the iterative solver by an objective of precision on a quantity of interest. This strategy consists in a sequence of solvings and takes advantage of adaptive remeshing and recycling of search directions. Copyright © 2016 John Wiley & Sons, Ltd.     

Classical and all‐floating FETI methods for the simulation of arterial tissues

High‐resolution and anatomically realistic computer models of biological soft tissues play a significant role in the understanding of the function of cardiovascular components in health and disease. However, the computational effort to handle fine grids to resolve the geometries as well as sophisticated tissue models is very challenging. One possibility to derive a strongly scalable parallel solution algorithm is to consider finite element tearing and interconnecting (FETI) methods. In this study, we propose and investigate the application of FETI methods to simulate the elastic behavior of biological soft tissues. As one particular example, we choose the artery which is—as most other biological tissues—characterized by anisotropic and nonlinear material properties. We compare two specific approaches of FETI methods, classical and all‐floating, and investigate the numerical behavior of different preconditioning techniques. In comparison with classical FETI, the all‐floating approach not only has advantages concerning the implementation but also has advantages concerning the convergence of the global iterative solution method. This behavior is illustrated with numerical examples. We present results of linear elastic simulations to show convergence rates, as expected from the theory, and results from the more sophisticated nonlinear case where we apply a well‐known anisotropic model to the realistic geometry of an artery. Although the FETI methods have a great applicability on artery simulations, we will also discuss some limitations concerning the dependence on material parameters. Copyright © 2014 John Wiley & Sons, Ltd.     

Element‐wise a posteriori estimates based on hierarchical bases for non‐linear parabolic problems

We show that the issue of a posteriori estimate the errors in the numerical simulation of non‐linear parabolic equations can be reduced to a posteriori estimate the errors in the approximation of an elliptic problem with the right‐hand side depending on known data of the problem and the computed numerical solution. A procedure to obtain local error estimates for the p version of the finite element method by solving small discrete elliptic problems with right‐hand side the residual of the p‐FEM solution is introduced. The boundary conditions are inherited by those of the space of hierarchical bases to which the error estimator belongs. We prove that the error in the numerical solution can be reduced by adding the estimators that behave as a locally defined correction to the computed approximation. When the error being estimated is that of a elliptic problem constant free local lower bounds are obtained. The local error estimation procedure is applied to non‐linear parabolic differential equations in several space dimensions. Some numerical experiments for both the elliptic and the non‐linear parabolic cases are provided. Copyright © 2005 John Wiley & Sons, Ltd.     

An efficient parallel procedure for the simulation of crack growth using the cohesive surface methodology

Simulations of crack growth that are based on the cohesive surface methodology typically involve ill‐conditioned systems of equations and require much processing time. This paper shows how these systems of equations can be solved efficiently by adopting the domain decomposition approach in which the finite element mesh is partitioned into multiple blocks. The system of equations is then reduced to a much smaller system of equations that is solved with an iterative algorithm in combination with a powerful two‐level preconditioner. Although the solution algorithm is more efficient than a direct solution algorithm on a single‐processor computer, it becomes really attractive when used on a parallel computer. This is demonstrated for a large scale simulation of crack growth in a polymer using a Cray T3E with 64 processors. Copyright © 2001 John Wiley & Sons, Ltd.     

An implicit–explicit solution method for electro‐osmotic flow through three‐dimensional micro‐channels

This paper presents a comprehensive finite‐element modelling approach to electro‐osmotic flows on unstructured meshes. The non‐linear equation governing the electric potential is solved using an iterative algorithm. The employed algorithm is based on a preconditioned GMRES scheme. The linear Laplace equation governing the external electric potential is solved using a standard pre‐conditioned conjugate gradient solver. The coupled fluid dynamics equations are solved using a fractional step‐based, fully explicit, artificial compressibility scheme. This combination of an implicit approach to the electric potential equations and an explicit discretization to the Navier–Stokes equations is one of the best ways of solving the coupled equations in a memory‐efficient manner. The local time‐stepping approach used in the solution of the fluid flow equations accelerates the solution to a steady state faster than by using a global time‐stepping approach. The fully explicit form and the fractional stages of the fluid dynamics equations make the system memory efficient and free of pressure instability. In addition to these advantages, the proposed method is suitable for use on both structured and unstructured meshes with a highly non‐uniform distribution of element sizes. The accuracy of the proposed procedure is demonstrated by solving a basic micro‐channel flow problem and comparing the results against an analytical solution. The comparisons show excellent agreement between the numerical and analytical data. In addition to the benchmark solution, we have also presented results for flow through a fully three‐dimensional rectangular channel to further demonstrate the application of the presented method. Copyright © 2007 John Wiley & Sons, Ltd.     

A FETI‐DP method for the parallel iterative solution of indefinite and complex‐valued solid and shell vibration problems

The dual‐primal finite element tearing and interconnecting (FETI‐DP) domain decomposition method (DDM) is extended to address the iterative solution of a class of indefinite problems of the form ( K ?σ² M ) u = f , and a class of complex problems of the form ( K ?σ² M +iσ D ) u = f , where K , M , and D are three real symmetric matrices arising from the finite element discretization of solid and shell dynamic problems, i is the imaginary complex number, and σ is a real positive number. A key component of this extension is a new coarse problem based on the free‐space solutions of Navier's equations of motion. These solutions are waves, and therefore the resulting DDM is reminiscent of the FETI‐H method. For this reason, it is named here the FETI‐DPH method. For a practically large σ range, FETI‐DPH is shown numerically to be scalable with respect to all of the problem size, substructure size, and number of substructures. The CPU performance of this iterative solver is illustrated on a 40‐processor computing system with the parallel solution, for various σ ranges, of several large‐scale, indefinite, or complex‐valued systems of equations associated with shifted eigenvalue and forced frequency response structural dynamics problems. Copyright © 2005 John Wiley & Sons, Ltd.     

Accelerating boundary integral equation method using a special‐purpose computer

We present a new solution to accelerate the boundary integral equation method (BIEM). The calculation time of the BIEM is dominated by the evaluation of the layer potential in the boundary integral equation. We performed this task using MDGRAPE‐2, a special‐purpose computer designed for molecular dynamics simulations. MDGRAPE‐2 calculates pairwise interactions among particles (e.g. atoms and ions) using hardwired‐pipeline processors. We combined this hardware with an iterative solver. During the iteration process, MDGRAPE‐2 evaluates the layer potential. The rest of the calculation is performed on a conventional PC connected to MDGRAPE‐2. We applied this solution to the Laplace and Helmholtz equations in three dimensions. Numerical tests showed that BIEM is accelerated by a factor of 10–100. Our rather naive solution has a calculation cost of O(N² × N_iter), where N is the number of unknowns and N_iter is the number of iterations. Copyright © 2005 John Wiley & Sons, Ltd.     

An efficient parallel computation of unsteady incompressible viscous flow with elastic moving and compliant boundaries on unstructured grids

This paper presents the development and validation of a parallel unstructured‐grid fluid–structure interaction (FSI) solver for the simulation of unsteady incompressible viscous flow with long elastic moving and compliant boundaries. The Navier–Stokes solver on unstructured moving grid using the arbitrary Lagrangian Eulerian formulation is based on the artificial compressibility approach and a high‐order characteristics‐based finite‐volume scheme. Both unsteady flow and FSI are calculated with a matrix‐free implicit dual time‐stepping scheme. A membrane model has been formulated to study fluid flow in a channel with an elastic membrane wall and their interactions. This model can be employed to calculate arbitrary wall movement and variable tension along the membrane, together with a dynamic mesh method for large deformation of the flow field. The parallelization of the fluid–structure solver is achieved using the single program multiple data programming paradigm and message passing interface for communication of data. The parallel solver is used to simulate fluid flow in a two‐dimensional channel with and without moving membrane for validation and performance evaluation purposes. The speedups and parallel efficiencies obtained by this method are excellent, using up to 16 processors on a SGI Origin 2000 parallel computer. A maximum speedup of 23.14 could be achieved on 16 processors taking advantage of an improved handling of the membrane solver. The parallel results obtained are compared with those using serial code and they are found to be identical. Copyright © 2005 John Wiley & Sons, Ltd.     

Numerical accuracy of a Padé‐type non‐reflecting boundary condition for the finite element solution of acoustic scattering problems at high‐frequency

The present text deals with the numerical solution of two‐dimensional high‐frequency acoustic scattering problems using a new high‐order and asymptotic Padé‐type artificial boundary condition. The Padé‐type condition is easy‐to‐implement in a Galerkin least‐squares (iterative) finite element solver for arbitrarily convex‐shaped boundaries. The method accuracy is investigated for different model problems and for the scattering problem by a submarine‐shaped scatterer. As a result, relatively small computational domains, optimized according to the shape of the scatterer, can be considered while yielding accurate computations for high‐frequencies. Copyright © 2005 John Wiley & Sons, Ltd.     

The nsBETI method: an extension of the FETI method to non‐symmetrical BEM‐FEM coupled problems

The finite element tearing and interconnecting (FETI) method is recognized as an effective domain decomposition tool to achieve scalability in the solution of partitioned second‐order elasticity problems. In the boundary element tearing and interconnecting (BETI) method, a direct extension of the FETI algorithm to the BEM, the symmetric Galerkin BEM formulation, is used to obtain symmetric system matrices, making possible to apply the same FETI conjugate gradient solver. In this work, we propose a new BETI variant labeled nsBETI that allows to couple substructures modeled with the FEM and/or non‐symmetrical BEM formulations. The method connects non‐matching BEM and FEM subdomains using localized Lagrange multipliers and solves the associated non‐symmetrical flexibility equations with a Bi‐CGstab iterative algorithm. Scalability issues of nsBETI in BEM–BEM and combined BEM–FEM coupled problems are also investigated. Copyright © 2012 John Wiley & Sons, Ltd.