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.     

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.     

Parallel edge-based solution of viscoplastic flows with the SUPG/PSPG formulation

A parallel edge-based solution of three dimensional viscoplastic flows governed by the steady Navier–Stokes equations is presented. The governing partial differential equations are discretized using the SUPG/PSPG stabilized finite element method on unstructured grids. The highly nonlinear algebraic system arising from the convective and material effects is solved by an inexact Newton-Krylov method. The locally linear Newton equations are solved by GMRES with nodal block diagonal preconditioner. Matrix-vector products within GMRES are computed edge-by-edge (EDE), diminishing flop counts and memory requirements. A comparison between EDE and element-by-element data structures is presented. The parallel computations were based in a message passing interface standard. Performance tests were carried out in representative three dimensional problems, the sudden expansion for power-law fluids and the flow of Bingham fluids in a lid-driven cavity. Results have shown that edge based schemes requires less CPU time and memory than element-based solutions.     

An efficient block preconditioner for Jacobian‐free global–local multiscale methods

In this paper, we develop a block preconditioner for Jacobian‐free global–local multiscale methods, in which the explicit computation of the Jacobian may be circumvented at the macroscale by using a Newton–Krylov process. Effective preconditioning is necessary for the Krylov subspace iterations (e.g. GMRES) to enhance computational efficiency. This is, however, challenging since no explicit information regarding the Jacobian matrix is available. The block preconditioning technique developed in this paper circumvents this problem by effectively deflating the spectrum of the Jacobian matrix at the current Newton step using information about only the Krylov subspaces corresponding to the Jacobian matrices in the previous Newton steps and their representations on those subspaces. This approach is optimal and results in exponential convergence of the GMRES iterations within each Newton step, thus minimizing expensive microscale computations without requiring explicit Jacobian formation in any step. In terms of both computational cost and storage requirements, the action of a single block of the preconditioner per GMRES step scales linearly as the number of degrees of freedom of the macroscale problem as well as the dimension of the invariant subspace of the preconditioned Jacobian matrix. Copyright © 2011 John Wiley & Sons, Ltd.     

Incomplete factorization‐based preconditionings for solving the Helmholtz equation

Preconditioning techniques based on incomplete factorization of matrices are investigated, to solve highly indefinite complex‐symmetric linear systems. A novel preconditioning is introduced. The real part of the matrix is made positive definite, or less indefinite, by adding properly defined perturbations to the diagonal entries, while the imaginary part is unaltered. The resulting preconditioning matrix, which is obtained by applying standard methods to the perturbed complex matrix, turns out to perform significantly better than classical incomplete factorization schemes. For realistic values of the GMRES restart parameter, spectacular reduction of iteration counts is observed. A theoretical spectral analysis is provided, in which the spectrum of the preconditioner applied to indefinite matrix is related to the spectrum of the same preconditioner applied to a Stieltjes matrix extracted from the indefinite matrix. Results of numerical experiments are reported, which display the efficiency of the new preconditioning. Copyright © 2001 John Wiley & Sons, Ltd.     

Enhancing the performance of the FETI method with preconditioning ¶techniques implemented on clusters of networked computers

 The FETI domain decomposition method for solving large-scale problems in computational structural mechanics involves the solution of an interface problem, which is handled by a Preconditioned Conjugate Projected Gradient (PCPG) algorithm. Two preconditioners are widely used to accelerate the convergence of the iterative PCPG algorithm: the optimal Dirichlet preconditioner and the economical lumped preconditioner. The Dirichlet preconditioner is computationally more efficient than the lumped preconditioner for ill-conditioned problems, but needs additional storage for the stiffness matrices of the subdomains' internal degrees of freedom (d.o.f.). In this study a new set of PCPG preconditioners is presented by providing approximate expressions to the inverse iteration matrix of the PCPG algorithm. The resulting approximate Dirichlet preconditioners are obtained by using instead of the whole stiffness matrix of the internal d.o.f. in each subdomain the following alternatives: a diagonal scaling matrix, a SSOR type matrix or an incomplete Cholesky factorization matrix. The computational behavior and performance of the proposed PCPG preconditioners is evaluated using an implementation of the FETI method on a cluster of ethernet-networked PCs running the message passing software PVM. It is demonstrated that the FETI method equipped with the approximate Dirichlet preconditioners leads for a number of large-scale problems to faster and less storage demanding overall solutions than with either Dirichlet or lumped preconditioner. Received: 28 December 2001 / Accepted: 22 August 2002     

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.     

Convergence bounds of GMRES with Schwarz' preconditioner for the scattering problem

We consider the Jacobi preconditioner of the GMRES method introduced by Liu and Jin for the scattering problem (IEEE Trans. Ante. Prop. 2002; 50 :132–140). We explain why it is a particular form of the Schwarz' preconditioner with a complete overlap and specific transmission conditions. So far, a superlinear convergence has been predicted by the general theory without any additional indication on the convergence rates. Here, we establish error bounds that provide accurate convergence rates in two and three dimensions. Courant–Weyl's min–max principle applied to some kernel operators together with some polynomial approximation estimates are the milestones for the proofs. Copyright © 2009 John Wiley & Sons, Ltd.     

Using spectral low rank preconditioners for large electromagnetic calculations

For solving large dense complex linear systems that arise in electromagnetic calculations, we perform experiments using a general purpose spectral low rank update preconditioner in the context of the GMRES method preconditioned by an approximate inverse preconditioner. The goal of the spectral preconditioner is to improve the convergence properties by shifting by one the smallest eigenvalues of the original preconditioned system. Numerical experiments on parallel distributed memory computers are presented to illustrate the efficiency of this technique on large and challenging real‐life industrial problems. Copyright © 2004 John Wiley & Sons, Ltd.     

An efficient implementation of the generalized minimum residual algorithm with a new preconditioner for the boundary element method

Despite the numerical stability and robustness of the generalized minimum residual algorithm, it still suffers from slow convergence rate and unexpected breakdown when applied to the boundary element method, even with the conventional preconditioners. To address these problems, we have devised a new preconditioner by combining the partial pivot method and diagonal scaling preconditioner with use of the selective reorthogonalization criterion. We examine the performance of these implementations through three numerical examples having a simple-domain, a multi-domain and a multiply-connected domain. The results of the numerical analyses confirm that the selective reorthogonalization criterion can retain the orthogonality of the basis vectors with a small number of reorthogonalizations and that the proposed preconditioner improve the computational efficiency.     

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.     

A fast multipole boundary element method based on the improved Burton–Miller formulation for three-dimensional acoustic problems

A fast multipole boundary element method (FMBEM) based on the improved Burton–Miller formulation is presented in this paper for solving large-scale three-dimensional (3D) acoustic problems. Some improvements can be made for the developed FMBEM. In order to overcome the non-unique problems of the conventional BEM, the FMBEM employs the improved Burton–Miller formulation developed by the authors recently to solve the exterior acoustic problems for all wave numbers. The improved Burton–Miller formulation contains only weakly singular integrals, and avoids the numerical difficulties associated to the evaluation of the hypersingular integral, it leads to the numerical implementations more efficient and straightforward. In this study, the fast multipole method (FMM) and the preconditioned generalized minimum residual method (GMRES) iterative solver are applied to solve system matrix equation. The block diagonal preconditioner needs no extra memory and no extra CPU time in each matrix–vector product. Thus, the overall computational efficiency of the developed FMBEM is further improved. Numerical examples clearly demonstrate the accuracy, efficiency and applicability of the FMBEM based on improved Burton–Miller formulation for large-scale acoustic problems.     

Effectiveness of GMRES-DR and OSP-ILUC for wave diffraction analysis of a very large floating structure (VLFS)

This paper presents the performance of iterative solvers and preconditioners for the non-Hermitian dense linear systems arising from the boundary value problem related to the diffraction wave field around a very large floating structure (VLFS). These systems can be solved iteratively using the GMRES with deflated restarting (GMRES-DR), which has Krylov subspaces with approximate eigenvectors as starting vectors. The number of iteration needed by GMRES or GMRES-DR can be significantly reduced using preconditioning techniques. Matrix-vector products are approximated by utilizing the fast multipole method (FMM), which need not directly calculate the dense matrix of the far field interactions. The combination of the operator splitting preconditioner (OSP) and the Crout version of the incomplete LU factorization (ILUC) does not require the dense matrix of the far field interactions. Numerical experiments from a hybrid-type VLFS, which is composed of pontoon-part and semi-submersible part, whose length is 3000 m are presented.     

Overlapping Schwarz preconditioners for spectral element discretizations of convection‐diffusion problems

The classical overlapping Schwarz algorithm is here extended to stabilized spectral element discretizations of convection‐diffusion problems. The algorithm solves iteratively the resulting non‐symmetric system of linear equations by a preconditioned GMRES method. The preconditioner is built from local convection‐diffusion solvers on overlapping subdomains and from a coarse convection‐diffusion solver on a coarse mesh defined by the subdomain boundaries. Several numerical experiments on test problems in the plane indicate that this algorithm retains the fast convergence rate and optimal scalability properties of classical overlapping methods for diffusion dominated problems. Fast convergence is also obtained for convection dominated problems without closed streamlines and with a moderate number of subdomains. Copyright © 2001 John Wiley & Sons, Ltd.     

An algebraically partitioned FETI method for parallel structural analysis: performance evaluation

This paper presents the algorithmic performance of an algebraically partitioned Finite Element Tearing and Interconnection (FETI) method presented in a companion paper. A simple structural assembly topology is employed to illustrate the implementation steps in a Matlab software environment. Numerical results indicate that the method is scalable, provided the iterative solution preconditioner employs the reduced interface Dirichlet preconditioner. A limited comparison of the present method with the differentially partitioned FETI method with corner modes is also offered. Based on this comparison and a reasonable extrapolation, we conclude the present algebraically partitioned FETI method possesses a similar iteration convergence property of the differentially partitioned FETI method with corner modes. © 1997 John Wiley & Sons, Ltd.     

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.     

Block preconditioners for symmetric indefinite linear systems

This paper presents a systematic theoretical and numerical evaluation of three common block preconditioners in a Krylov subspace method for solving symmetric indefinite linear systems. The focus is on large‐scale real world problems where block approximations are a practical necessity. The main illustration is the performance of the block diagonal, constrained, and lower triangular preconditioners over a range of block approximations for the symmetric indefinite system arising from large‐scale finite element discretization of Biot's consolidation equations. This system of equations is of fundamental importance to geomechanics. Numerical studies show that simple diagonal approximations to the (1,1) block K and inexpensive approximations to the Schur complement matrix S may not always produce the most spectacular time savings when K is explicitly available, but is able to deliver reasonably good results on a consistent basis. In addition, the block diagonal preconditioner with a negative (2,2) block appears to be reasonably competitive when compared to the more complicated ones. These observation are expected to remain valid for coefficient matrices whereby the (1,1) block is sparse, diagonally significant (a notion weaker than diagonal dominance), moderately well‐conditioned, and has a much larger block size than the (2,2) block. Copyright © 2004 John Wiley & Sons, Ltd.     

求解线性系统的新预条件子及比较定理

本文提出了一种求解大规模线性系统的新预条件子,并从理论上证明了对AOR迭代法而言,新预条件子优于两类已知的预条件子,文中所得收敛性比较定理推广了已有结果.文尾给出的数值算例也充分验证了这种新预条件子的有效性.     

Algebraic multigrid methods for solving generalized eigenvalue problems

Three algebraic multigrid (AMG) methods for solving generalized eigenvalue problems are presented. The first method combines modern AMG techniques with a non‐linear multigrid approach and nested iteration strategy. The second method is a preconditioned inverse iteration with linear AMG preconditioner. The third method is an enhancement of the previous one, namely the locally optimal block preconditioned conjugate gradient. Efficiency and accuracy of solutions computed by these AMG eigensolvers are validated on standard benchmarks where part of the spectrum is known. In particular, the problem of isospectral drums is addressed. Copyright © 2005 John Wiley & Sons, Ltd.     

The generalized global basis (GGB) method

In this work, we present the generalized global basis (GGB) method aimed at enhancing performance of multilevel solvers for difficult systems such as those arising from indefinite and non‐symmetric matrices. The GGB method is based on the global basis (GB) method (Int J Numer Methods Eng 2000; 49 :439–460, 461–478), which constructs an auxiliary coarse model from the largest eigenvalues of the iteration matrix. The GGB method projects these modes which would cause slow convergence to a coarse problem which is then used to eliminate these modes. Numerical examples show that best performance is obtained when GGB is accelerated by GMRES and used for problems with multiple right‐hand sides. In addition, it is demonstrated that GGB method can enhance restarted GMRES strategies by retention of subspace information. Copyright © 2004 John Wiley & Sons, Ltd.