An efficient preconditioner for the fast simulation of a 2D stokes flow in porous media

We consider an efficient preconditioner for a boundary integral equation (BIE) formulation of the two‐dimensional Stokes equations in porous media. While BIEs are well‐suited for resolving the complex porous geometry, they lead to a dense linear system of equations that is computationally expensive to solve for large problems. This expense is further amplified when a significant number of iterations is required in an iterative Krylov solver such as generalized minimial residual method (GMRES). In this paper, we apply a fast inexact direct solver, the inverse fast multipole method, as an efficient preconditioner for GMRES. This solver is based on the framework of ‐matrices and uses low‐rank compressions to approximate certain matrix blocks. It has a tunable accuracy ε and a computational cost that scales as . We discuss various numerical benchmarks that validate the accuracy and confirm the efficiency of the proposed method. We demonstrate with several types of boundary conditions that the preconditioner is capable of significantly accelerating the convergence of GMRES when compared to a simple block‐diagonal preconditioner, especially for pipe flow problems involving many pores.     

A Block Diagonal Preconditioner for Generalised Saddle Point Problems

A lopsided alternating direction iteration (LADI) method and an induced block diagonal preconditioner for solving block two-by-two generalised saddle point problems are presented. The convergence of the LADI method is analysed, and the block diagonal preconditioner can accelerate the convergence rates of Krylov subspace iteration methods such as GMRES. Our new preconditioned method only requires a solver for two linear equation sub-systems with symmetric and positive definite coefficient matrices. Numerical experiments show that the GMRES with the new preconditioner is quite effective.     

Perturbed incomplete ILU preconditioner for efficient solution of electric field integral equations

To efficiently solve large, dense, complex linear systems that arise in the electric field integral equation (EFIE) formulation of electromagnetic scattering problems, a new modified incomplete LU (ILU) preconditioner is developed and used in the context of the generalised minimal residual iterative method accelerated with the multilevel fast multipole method. The key idea is to perturb the near-field impedance matrix of EFIE with the principle value term of the magnetic field integral equation operator before constructing ILU preconditioners. Numerical experiments indicate that this new perturbation technique is very effective with the ILU preconditioner and the resulted ILU preconditioner can reduce both the iteration number and the computational time substantially.     

Comparison of matrix-free acceleration techniques in compressible Navier–Stokes calculations

Six different preconditioning methods to accelerate the convergence rate of Krylov-subspace iterative methods are described, implemented and compared in the context of matrix-free techniques. The acceleration techniques comprehend Krylov-subspace iterative methods; invariant subspace-based methods and matrix approximations: Jacobi, LU-SGS, Deflated GMRES; Augmented GMRES; polynomial preconditioner and FGMRES/Krylov. The relative behaviour of the methods is explained in terms of the spectral properties of the resulting iterative matrix. The employed code uses a Newton–Krylov approach to iteratively solve the Euler or Navier–Stokes equations, for a supersonic ramp or a viscous compressible double-throat flow. The linear system approximate solver is the GMRES method, in either the restarted or FGMRES variants. The results show the better performance of the methods that approximate the iterative matrix, such as Jacobi, LU-SGS and FGMRES/Krylov. Copyright © 2004 John Wiley & Sons, Ltd.     

Newton‐Krylov method for computing the cyclic steady states of evolution problems in nonlinear mechanics

This work is focused on the Newton‐Krylov technique for computing the steady cyclic states of evolution problems in nonlinear mechanics with space‐time periodicity conditions. This kind of problems can be faced, for instance, in the modeling of a rolling tire with a periodic tread pattern, where the cyclic state satisfies “rolling” periodicity condition, including shifts both in time and space. The Newton‐Krylov method is a combination of a Newton nonlinear solver with a Krylov linear solver, looking for the initial state, which provides the space‐time periodic solution. The convergence of the Krylov iterations is proved to hold in presence of an adequate preconditioner. After preconditioning, the Newton‐Krylov method can be also considered as an observer‐controller method, correcting the transient solution of the initial value problem after each period. Using information stored while computing the residual, the Krylov solver computation time becomes negligible with respect to the residual computation time. The method has been analyzed and tested on academic applications and compared with the standard evolution (fixed point) method. Finally, it has been implemented into the Michelin industrial code, applied to a full 3D rolling tire model.     

On the preconditioners for fast multipole boundary element methods for 2D multi-domain elastostatics

Fast multipole method (FMM) has been successfully applied to accelerate the numerical solvers of boundary element method (BEM). However, the coefficient matrix implicitly formed by using FMM is sometimes ill-conditioned in cases when mixed boundary conditions exist, resulting in poor rate of convergence for iteration. So preconditioning is a critical part in the development of efficient FMM solver for BEM. In this paper, preconditioners based on sparse approximate inverse type are used for fast multipole BEM to deal with 2D elastostatics. Several sparsity patterns of the preconditioner are considered for single- and multi-domain problems, especially for 2D elastic body with large number of inclusions or cracks. Algorithms and cost analysis of preconditioning under different prescribed sparsity patterns are discussed. GMRES is used as the iterative solver. Numerical results show this type of preconditioner achieves satisfactory rate of convergence for fast multipole BEM and performs well for problems of fairly large sizes.     

A domain decomposition method for discontinuous Galerkin discretizations of Helmholtz problems with plane waves and Lagrange multipliers

A nonoverlapping domain decomposition (DD) method is proposed for the iterative solution of systems of equations arising from the discretization of Helmholtz problems by the discontinuous enrichment method. This discretization method is a discontinuous Galerkin finite element method with plane wave basis functions for approximating locally the solution and dual Lagrange multipliers for weakly enforcing its continuity over the element interfaces. The primal subdomain degrees of freedom are eliminated by local static condensations to obtain an algebraic system of equations formulated in terms of the interface Lagrange multipliers only. As in the FETI‐H and FETI‐DPH DD methods for continuous Galerkin discretizations, this system of Lagrange multipliers is iteratively solved by a Krylov method equipped with both a local preconditioner based on subdomain data, and a global one using a coarse space. Numerical experiments performed for two‐ and three‐dimensional acoustic scattering problems suggest that the proposed DD‐based iterative solver is scalable with respect to both the size of the global problem and the number of subdomains. Copyright © 2009 John Wiley & Sons, Ltd.     

On the implementation of 3D Galerkin boundary integral equations

In this article, a reverse contribution technique is proposed to accelerate the construction of the dense influence matrices associated with a Galerkin approximation of hypersingular boundary integral equations of mixed-type in potential theory. In addition, a general-purpose sparse preconditioner for boundary element methods has also been developed to successfully deal with ill-conditioned linear systems arising from the discretization of mixed boundary-value problems on non-smooth surfaces. The proposed preconditioner, which originates from the precorrected-FFT method, is sparse, easy to generate and apply in a Krylov subspace iterative solution of discretized boundary integral equations. Moreover, an approximate inverse of the preconditioner is implicitly built by employing an incomplete LU factorization. Numerical experiments involving mixed boundary-value problems for the Laplace equation are included to illustrate the performance and validity of the proposed techniques.     

Performance of a Petrov–Galerkin algebraic multilevel preconditioner for finite element modeling of the semiconductor device drift‐diffusion equations

This study compares the performance of a relatively new Petrov–Galerkin smoothed aggregation (PGSA) multilevel preconditioner with a nonsmoothed aggregation (NSA) multilevel preconditioner to accelerate the convergence of Krylov solvers on systems arising from a drift‐diffusion model for semiconductor devices. PGSA is designed for nonsymmetric linear systems, Ax=b, and has two main differences with smoothed aggregation. Damping parameters for smoothing interpolation basis functions are now calculated locally and restriction is no longer the transpose of interpolation but instead corresponds to applying the interpolation algorithm to A^T and then transposing the result. The drift‐diffusion system consists of a Poisson equation for the electrostatic potential and two convection–diffusion‐reaction‐type equations for the electron and hole concentration. This system is discretized in space with a stabilized finite element method and the discrete solution is obtained by using a fully coupled preconditioned Newton–Krylov solver. The results demonstrate that the PGSA preconditioner scales significantly better than the NSA preconditioner, and can reduce the solution time by more than a factor of two for a problem with 110 million unknowns on 4000 processors. The solution of a 1B unknown problem on 24 000 processor cores of a Cray XT3/4 machine was obtained using the PGSA preconditioner. Copyright © 2010 John Wiley & Sons, Ltd.     

CMRH method as iterative solver for boundary element acoustic systems

Disceretization of boundary integral equations leads to complex and fully populated linear systems. One inherent drawback of the boundary element method (BEM) is that, the dense linear system has to be constructed and solved for each frequency. For large-scale problems, BEM can be more efficient by improving the construction and solution phases of the linear system. For these problems, the application of common direct solver is inefficient. In this paper, the corresponding linear systems are solved more efficiently than common direct solvers by using the iterative technique called CMRH (Changing Minimal Residual method based on Hessenberg process). In this method, the generation of the basis vectors of the Krylov subspace is based on the Hessenberg process instead of Arnoldi's one that the most known GMRES (Generalized Minimal RESidual) solver uses. Compared to GMRES, the storage requirements are considerably reduced in CMRH.     

On the performance of Krylov smoothing for fully coupled AMG preconditioners for VMS resistive MHD

This study explores the performance and scaling of a GMRES Krylov method employed as a smoother for an algebraic multigrid preconditioned Newton-Krylov solution approach applied to a fully implicit variational multiscale finite element resistive magnetohydrodynamics formulation. In this context, a Newton iteration is used for the nonlinear system and a parallel MPI-based Krylov method is employed for the linear subsystems. The efficiency of this approach is critically dependent on the scalability and performance of the parallel algebraic multigrid preconditioner for the linear solutions and the performance of the multigrid smoothers play a critical role. Krylov multigrid smoothers are considered in an attempt to reduce the time and memory requirements of existing robust smoothers based on additive Schwarz domain decomposition with incomplete LU factorization solves on each subdomain. Three time-dependent resistive magnetohydrodynamics test cases are considered to evaluate the method. Compared with a domain decomposition incomplete LU smoother, the GMRES smoother can reduce the solve time due to a significant decrease in the preconditioner setup time and often a reduction in outer Krylov solver iterations, and requires less memory, typically 35% less memory.     

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.     

Efficient solution of time‐domain boundary integral equations arising in sound‐hard scattering

We consider the efficient numerical solution of the three‐dimensional wave equation with Neumann boundary conditions via time‐domain boundary integral equations. A space‐time Galerkin method with C^∞‐smooth, compactly supported basis functions in time and piecewise polynomial basis functions in space is employed. We discuss the structure of the system matrix and its efficient parallel assembly. Different preconditioning strategies for the solution of the arising systems with block Hessenberg matrices are proposed and investigated numerically. Furthermore, a C++ implementation parallelized by OpenMP and MPI in shared and distributed memory, respectively, is presented. The code is part of the boundary element library BEM4I. Results of numerical experiments including convergence and scalability tests up to a thousand cores on a cluster are provided. The presented implementation shows good parallel scalability of the system matrix assembly. Moreover, the proposed algebraic preconditioner in combination with the FGMRES solver leads to a significant reduction of the computational time. Copyright © 2015 John Wiley & Sons, Ltd.     

A modified SSOR preconditioner for sparse symmetric indefinite linear systems of equations

The standard SSOR preconditioner is ineffective for the iterative solution of the symmetric indefinite linear systems arising from finite element discretization of the Biot's consolidation equations. In this paper, a modified block SSOR preconditioner combined with the Eisenstat‐trick implementation is proposed. For actual implementation, a pointwise variant of this modified block SSOR preconditioner is highly recommended to obtain a compromise between simplicity and effectiveness. Numerical experiments show that the proposed modified SSOR preconditioned symmetric QMR solver can achieve faster convergence than several effective preconditioners published in the recent literature in terms of total runtime. Moreover, the proposed modified SSOR preconditioners can be generalized to non‐symmetric Biot's systems. Copyright © 2005 John Wiley & Sons, Ltd.     

Incorporation of multipoint constraints into the balancing domain decomposition method and its parallel implementation

The domain decomposition method (DDM) is a major solution algorithm that is used to parallelize the finite element method. In the case of implicit structural analysis using the DDM, the substructuring‐based iterative linear solver is a powerful tool when an effective preconditioner such as the balancing domain decomposition (BDD) method is used. In the present study, a method by which to incorporate a set of linear multipoint constraints (MPC) into the BDD method is proposed. In this method, when an MPC is enforced on the internal degrees of freedom (DOFs) in some subdomains, the DOFs are converted into interface DOFs, that is, all of the DOFs constrained by MPCs become interface DOFs. Then, the interface problem with the set of MPCs for the interface DOFs is solved by the conjugate projected gradient method. In order to combine the above procedure with the preconditioner used in the BDD method, the effect of the MPCs for the interface DOFs is also imposed on the coarse grid problem of the BDD method using the penalty method. A parallel implementation of the present method is also described. Some illustrative examples are solved and good convergence and parallel performance of the present method are demonstrated. Copyright © 2006 John Wiley & Sons, Ltd.     

Accelerated engineering design optimization using successive matrix inversion method

In a design optimization procedure, many repeated system analyses are conducted to evaluate certain performances of successively modified structural designs. To alleviate the high computational cost of structural reanalysis, an augmented preconditioner is introduced by using the successive matrix inversion (SMI) method. The SMI method, as an exact matrix solver, is successively applied to an iterative procedure to accelerate the solution convergence by improving the numerical condition of the reanalysis system. In this work, a new iterative technique, the binomial series iterative (BSI) method, is developed from the binomial series expansion by using the same concept as SMI. As a combined iterative (CI) method, SMI is incorporated in the procedure of BSI. The CI method, combined with SMI, shows sufficient efficiency and robustness through a stable iterative behaviour due to simple and straightforward computations in the iterative procedure. Published in 2005 by John Wiley & Sons, Ltd.     

A multilevel hierarchical preconditioner for thin elastic solids

In this study, a multilevel, recursively defined preconditioner, for use with the Preconditioned Conjugate Gradient (PCG) algorithm in connection with the finite element analysis of elastostatics is developed. The preconditioner is constructed from a sequence of hierarchical vector spaces arising from the p-version of the finite element method. Results from parametric studies evaluating the effects of skewed elements, orthotropic material properties, and extreme span ratios, for p=2 and 3 are given. The results indicate that the preconditioner may be used to produce an efficient solver. The efficiency of the iterative procedure is illustrated using thin elastic solids. Results indicate that the preconditioner developed herein can be used to produce an efficient iterative solver for two- and three-dimensional problems in structural mechanics. © 1998 John Wiley & Sons, Ltd.     

Performance of fully coupled algebraic multilevel domain decomposition preconditioners for incompressible flow and transport

This study investigates algebraic multilevel domain decomposition preconditioners of the Schwarz type for solving linear systems associated with Newton–Krylov methods. The key component of the preconditioner is a coarse approximation based on algebraic multigrid ideas to approximate the global behaviour of the linear system. The algebraic multilevel preconditioner is based on an aggressive coarsening graph partitioning of the non‐zero block structure of the Jacobian matrix. The scalability of the preconditioner is presented as well as comparisons with a two‐level Schwarz preconditioner using a geometric coarse grid operator. These comparisons are obtained on large‐scale distributed‐memory parallel machines for systems arising from incompressible flow and transport using a stabilized finite element formulation. The results demonstrate the influence of the smoothers and coarse level solvers for a set of 3D example problems. For preconditioners with more than one level, careful attention needs to be given to the balance of robustness and convergence rate for the smoothers and the cost of applying these methods. For properly chosen parameters, the two‐ and three‐level preconditioners are demonstrated to be scalable to 1024 processors. Copyright © 2006 John Wiley & Sons, Ltd.     

Multi‐level incomplete factorizations for the iterative solution of non‐linear finite element problems

Several engineering applications give rise quite naturally to linearized FE systems of equations possessing a multi‐level structure. An example is provided by geomechanical models of layered and faulted geological formations. For such problems the use of a multi‐level incomplete factorization (MIF) as a preconditioner for Krylov subspace methods can prove a robust and efficient solution accelerator, allowing for a fine tuning of the fill‐in degree with a significant improvement in both the solver performance and the memory consumption. The present paper develops two novel MIF variants for the solution of multi‐level symmetric positive definite systems. Two correction algorithms are proposed with the aim of preserving the positive definiteness of the preconditioner, thus avoiding possible breakdowns of the preconditioned conjugate gradient solver. The MIF variants are experimented with in the solution of both a single system and a long‐term quasi‐static simulation dealing with a multi‐level geomechanical application. The numerical results show that MIF typically outperforms by up to a factor 3 a more traditional algebraic preconditioner such as an incomplete Cholesky factorization with partial fill‐in. The advantage is emphasized in a long‐term simulation where the fine fill‐in tuning allowed for by MIF yields a significant improvement for the computer memory requirement as well. Copyright © 2009 John Wiley & Sons, Ltd.     

Computational fluid dynamics by boundary–domain integral method

A boundary–domain integral method for the solution of general transport phenomena in incompressible fluid motion given by the Navier–Stokes equation set is presented. Velocity–vorticity formulation of the conservation equations is employed. Different integral representations for conservation field functions based on different fundamental solutions are developed. Special attention is given to the use of subdomain technique and Krylov subspace iterative solvers. The computed solutions of several benchmark problems agree well with available experimental and other computational results. Copyright © 1999 John Wiley & Sons, Ltd.