ℋ︁‐LU factorization in preconditioners for augmented Lagrangian and grad‐div stabilized saddle point systems

The (mixed finite element) discretization of the linearized Navier–Stokes equations leads to a linear system of equations of saddle point type. The iterative solution of this linear system requires the construction of suitable preconditioners, especially in the case of high Reynolds numbers. In the past, a stabilizing approach has been suggested which does not change the exact solution but influences the accuracy of the discrete solution as well as the effectiveness of iterative solvers. This stabilization technique can be performed on the continuous side before the discretization, where it is known as ‘grad‐div’ (GD) stabilization, as well as on the discrete side where it is known as an ‘augmented Lagrangian’ (AL) technique (and does not change the discrete solution). In this paper, we study the applicability of ??‐LU factorizations to solve the arising subproblems in the different variants of stabilized saddle point systems. We consider both the saddle point systems that arise from the stabilization in the continuous as well as on the discrete setting. Recently, a modified AL preconditioner has been proposed for the system resulting from the discrete stabilization. We provide a straightforward generalization of this approach to the GD stabilization. We conclude the paper with numerical tests for a variety of problems to illustrate the behavior of the considered preconditioners as well as the suitability of ??‐LU factorization in the preconditioners. Copyright © 2010 John Wiley & Sons, Ltd.     

Conjugate gradient methods and ILU preconditioning of non-symmetric matrix systems with arbitrary sparsity patterns

Preconditioning techniques based on incomplete Gaussian elimination for large, sparse, non-symmetric matrix systems are described. A certain level of fill-in may be specified in the incomplete factorizations. All methods considered may be applied to matrices with arbitrary sparsity patterns, for instance those associated with the general preprocessor algorithms or adaptive mesh techniques. The preconditioners have been combined with five conjugate gradient-like methods and tested on finite element discretized scalar convection-diffusion equations in 2D and 3D. It is found from numerical experiments that an amount of fill-in corresponding to about 50% of the number of original non-zero matrix entries is the optimal choice for this class of preconditioners. The preconditioners show almost no sensitivity to grid distortion. In problems with significantly variable coefficients or anisotropy the preconditioners stabilize the basic iterative schemes in addition to reducing the computational work substantially, mostly by more than 90%. The modified preconditioning technique, where fill-in is added on the main diagonal, performs in general better than the standard incomplete LU factorization, but is inferior to the latter in 3D problems and for matrix systems with complicated sparsity patterns.     

Modified augmented Lagrangian preconditioners for the incompressible Navier–Stokes equations

We study different variants of the augmented Lagrangian (AL)‐based block‐triangular preconditioner introduced by the first two authors in [SIAM J. Sci. Comput. 2006; 28 : 2095–2113]. The preconditioners are used to accelerate the convergence of the Generalized Minimal Residual method (GMRES) applied to various finite element and Marker‐and‐Cell discretizations of the Oseen problem in two and three space dimensions. Both steady and unsteady problems are considered. Numerical experiments show the effectiveness of the proposed preconditioners for a wide range of problem parameters. Implementation on parallel architectures is also considered. The AL‐based approach is further generalized to deal with linear systems from stabilized finite element discretizations. Copyright © 2010 John Wiley & Sons, Ltd.     

Efficient preconditioning techniques for finite‐element quadratic discretization arising from linearized incompressible Navier–Stokes equations

We develop an efficient preconditioning techniques for the solution of large linearized stationary and non‐stationary incompressible Navier–Stokes equations. These equations are linearized by the Picard and Newton methods, and linear extrapolation schemes in the non‐stationary case. The time discretization procedure uses the Gear scheme and the second‐order Taylor–Hood element P₂?P₁ is used for the approximation of the velocity and the pressure. Our purpose is to develop an efficient preconditioner for saddle point systems. Our tools are the addition of stabilization (penalization) term r?(div(·)), and the use of triangular block matrix as global preconditioner. This preconditioner involves the solution of two subsystems associated, respectively, with the velocity and the pressure and have to be solved efficiently. Furthermore, we use the P₁?P₂ hierarchical preconditioner recently proposed by the authors, for the block matrix associated with the velocity and an additive approach for the Schur complement approximation. Finally, several numerical examples illustrating the good performance of the preconditioning techniques are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

SIMPLE‐type preconditioners for the Oseen problem

In this paper, the steady incompressible Navier–Stokes equations are discretized by the finite element method. The resulting systems of equations are solved by preconditioned Krylov subspace methods. Some new preconditioning strategies, both algebraic and problem dependent are discussed. We emphasize on the approximation of the Schur complement as used in semi implicit method for pressure‐linked equations‐type preconditioners. In the usual formulation, the Schur complement matrix and updates use scaling with the diagonal of the convection–diffusion matrix. We propose a variant of the SIMPLER preconditioner. Instead of using the diagonal of the convection–diffusion matrix, we scale the Schur complement and updates with the diagonal of the velocity mass matrix. This variant is called modified SIMPLER (MSIMPLER). With the new approximation, we observe a drastic improvement in convergence for large problems. MSIMPLER shows better convergence than the well‐known least‐squares commutator preconditioner which is also based on the diagonal of the velocity mass matrix. Copyright © 2008 John Wiley & Sons, Ltd.     

A preconditioned semi‐staggered dilation‐free finite volume method for the incompressible Navier–Stokes equations on all‐hexahedral elements

A new semi‐staggered finite volume method is presented for the solution of the incompressible Navier–Stokes equations on all‐quadrilateral (2D)/hexahedral (3D) meshes. The velocity components are defined at element node points while the pressure term is defined at element centroids. The continuity equation is satisfied exactly within each elements. The checkerboard pressure oscillations are prevented using a special filtering matrix as a preconditioner for the saddle‐point problem resulting from second‐order discretization of the incompressible Navier–Stokes equations. The preconditioned saddle‐point problem is solved using block preconditioners with GMRES solver. In order to achieve higher performance FORTRAN source code is based on highly efficient PETSc and HYPRE libraries. As test cases the 2D/3D lid‐driven cavity flow problem and the 3D flow past array of circular cylinders are solved in order to verify the accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

A parallel monolithic algorithm for the numerical simulation of large‐scale fluid structure interaction problems

A novel parallel monolithic algorithm has been developed for the numerical simulation of large‐scale fluid structure interaction problems. The governing incompressible Navier–Stokes equations for the fluid domain are discretized using the arbitrary Lagrangian–Eulerian formulation‐based side‐centered unstructured finite volume method. The deformation of the solid domain is governed by the constitutive laws for the nonlinear Saint Venant–Kirchhoff material, and the classical Galerkin finite element method is used to discretize the governing equations in a Lagrangian frame. A special attention is given to construct an algorithm with exact total fluid volume conservation while obeying both the global and the local discrete geometric conservation law. The resulting large‐scale algebraic nonlinear equations are multiplied with an upper triangular right preconditioner that results in a scaled discrete Laplacian instead of a zero block in the original system. Then, a one‐level restricted additive Schwarz preconditioner with a block‐incomplete factorization within each partitioned sub‐domains is utilized for the modified system. The accuracy and performance of the proposed algorithm are verified for the several benchmark problems including a pressure pulse in a flexible circular tube, a flag interacting with an incompressible viscous flow, and so on. John Wiley & Sons, Ltd.     

Parallelization of the ILU(0) preconditioner for CFD problems on shared‐memory computers

The use of ILU(0) factorization as a preconditioner is quite frequent when solving linear systems of CFD computations. This is because of its efficiency and moderate memory requirements. For a small number of processors, this preconditioner, parallelized through coloring methods, shows little savings when compared with a sequential one using adequate reordering of the unknowns. Level scheduling techniques are applied to obtain the same preconditioning efficiency as in a sequential case, while taking advantage of parallelism through block algorithms. Numerical results obtained from the parallel solution of the compressible Navier–Stokes equations show that this technique gives interesting savings in computational times on a small number of processors of shared‐memory computers. In addition, it does this while keeping all the benefits of an ILU(0) factorization with an adequate reordering of the unknowns, and without the loss of efficiency of factorization associated with a more scalable coloring strategy. Copyright © 1999 John Wiley & Sons, Ltd.     

Reordering and incomplete preconditioning in serial and parallel adaptive mesh refinement and coarsening flow solutions

The effects of reordering the unknowns on the convergence of incomplete factorization preconditioned Krylov subspace methods are investigated. Of particular interest is the resulting preconditioned iterative solver behavior when adaptive mesh refinement and coarsening (AMR/C) are utilized for serial or distributed parallel simulations. As representative schemes, we consider the familiar reverse Cuthill–McKee and quotient minimum degree algorithms applied with incomplete factorization preconditioners to CG and GMRES solvers. In the parallel distributed case, reordering is applied to local subdomains for block ILU preconditioning, and subdomains are repartitioned dynamically as mesh adaptation proceeds. Numerical studies for representative applications are conducted using the object‐oriented AMR/C software system libMesh linked to the PETSc solver library. Serial tests demonstrate that global unknown reordering and incomplete factorization preconditioning can reduce the number of iterations and improve serial CPU time in AMR/C computations. Parallel experiments indicate that local reordering for subdomain block preconditioning associated with dynamic repartitioning because of AMR/C leads to an overall reduction in processing time. Copyright © 2011 John Wiley & Sons, Ltd.     

两点边值问题3次Lagrange形函数有限元方程的条件数和预处理

大型病态稀疏线性方程组的求解是科学计算和工程应用中的重要问题之一,采用预处理方法,通过降低条件数来减少病态是解决这一问题的关键。基于3次Lagrange形函数,用有限元方法将积分形式两点边值问题的求解转化成病态七对角方程组的求解。通过研究该方程组的特殊结构,分析了该方程的条件数,找到产生病态的因子(致病因子)。将系数矩阵的大范数部分分解成几个简单矩阵的特殊组合,基于这种特殊分解,设计出预条件子(去病因子),并对预条件子的性能进行了定量分析。结果表明,该预条件子的使用几乎不增加迭代的计算量,预处理后的条件数接近1。     

Improved parallel preconditioners for multidisciplinary topology optimisations

Two commonly used preconditioners were evaluated for parallel solution of linear systems of equations with high condition numbers. The test cases were derived from topology optimisation applications in multiple disciplines, where the material distribution finite element methods were used. Because in this optimisation method, the equations rapidly become ill-conditioned due to disappearance of large number of elements from the design space as the optimisations progresses, it is shown that the choice for a suitable preconditioner becomes very crucial. In an earlier work the conjugate gradient (CG) method with a Block-Jacobi preconditioner was used, in which the number of CG iterations increased rapidly with the increasing number processors. Consequently, the parallel scalability of the method deteriorated fast due to the increasing loss of interprocessor information among the increased number of processors. By replacing the Block-Jacobi preconditioner with a sparse approximate inverse preconditioner, it is shown that the number of iterations to converge became independent of the number of processors. Therefore, the parallel scalability is improved.     

Numbering techniques for preconditioners in iterative solvers for compressible flows

We consider Newton–Krylov methods for solving discretized compressible Euler equations. A good preconditioner in the Krylov subspace method is crucial for the efficiency of the solver. In this paper we consider a point‐block Gauss–Seidel method as preconditioner. We describe and compare renumbering strategies that aim at improving the quality of this preconditioner. A variant of reordering methods known from multigrid for convection‐dominated elliptic problems is introduced. This reordering algorithm is essentially black‐box and significantly improves the robustness and efficiency of the point‐block Gauss–Seidel preconditioner. Results of numerical experiments using the QUADFLOW solver and the PETSc library are given. Copyright © 2007 John Wiley & Sons, Ltd.     

Some special purpose preconditioners for conjugate gradient-like methods applied to CFD

Standard preconditioners such as incomplete LU decomposition perform well when used with conjugate gradient-like iterative solvers such as GMRES for the solution of elliptic problems. However, efficient computation of convection-dominated problems requires, in general, the use of preconditioners tuned to the particular class of fluid-flow problems at hand. This paper presents three such preconditioners. The first is applied to the finite element computation of inviscid (Euler equations) transonic and supersonic flows with shocks and uses incomplete LU decomposition applied to a matrix with extra artificial dissipation. The second preconditioner is applied to the finite difference computation of unsteady incompressible viscous flow; it uses incomplete LU decomposition applied to a matrix to which a pseudo-compressible term has been added. The third method and application are similar to the second, only the LU decomposition is replaced by Beam-warming approximate factorization. In all cases, the results are in very good agreement with other published results and the new algorithms are found to be competitive with others; it is anticipated that the efficiency and robustness of conjugate-gradient-like methods will render them the method of choice as the difficulty of the problems that they are applied to is increased.     

Efficiency of high‐performance discontinuous Galerkin spectral element methods for under‐resolved turbulent incompressible flows

The present paper addresses the numerical solution of turbulent flows with high‐order discontinuous Galerkin methods for discretizing the incompressible Navier‐Stokes equations. The efficiency of high‐order methods when applied to under‐resolved problems is an open issue in the literature. This topic is carefully investigated in the present work by the example of the three‐dimensional Taylor‐Green vortex problem. Our implementation is based on a generic high‐performance framework for matrix‐free evaluation of finite element operators with one of the best realizations currently known. We present a methodology to systematically analyze the efficiency of the incompressible Navier‐Stokes solver for high polynomial degrees. Due to the absence of optimal rates of convergence in the under‐resolved regime, our results reveal that demonstrating improved efficiency of high‐order methods is a challenging task and that optimal computational complexity of solvers and preconditioners as well as matrix‐free implementations are necessary ingredients in achieving the goal of better solution quality at the same computational costs already for a geometrically simple problem such as the Taylor‐Green vortex. Although the analysis is performed for a Cartesian geometry, our approach is generic and can be applied to arbitrary geometries. We present excellent performance numbers on modern cache‐based computer architectures achieving a throughput for operator evaluation of 3·10⁸ up to 1·10⁹ DoFs/s (degrees of freedom per second) on one Intel Haswell node with 28 cores. Compared to performance results published within the last five years for high‐order discontinuous Galerkin discretizations of the compressible Navier‐Stokes equations, our approach reduces computational costs by more than one order of magnitude for the same setup.     

Fast solvers for models of ICEO microfluidic flows

We demonstrate the performance of a fast computational algorithm for modeling the design of a microfluidic mixing device. The device uses an electrokinetic process, induced charge electroosmosis (J. Fluid Mech. 2004; 509 ), by which a flow through the device is driven by a set of polarizable obstacles in it. Its design is realized by manipulating the shape and orientation of the obstacles in order to maximize the amount of fluid mixing within the device. The computation entails the solution of a constrained optimization problem in which function evaluations require the numerical solution of a set of partial differential equations: a potential equation, the incompressible Navier–Stokes equations, and a mass‐transport equation. The most expensive component of the function evaluation (which must be performed at every step of an iteration for the optimization) is the solution of the Navier–Stokes equations. We show that by using some new robust algorithms for this task (SIAM J. Sci. Comput. 2002; 24 :237–256; J. Comput. Appl. Math. 2001; 128 :261–279), based on certain preconditioners that take advantage of the structure of the linearized problem, this computation can be done efficiently. Using this computational strategy, in conjunction with a derivative‐free pattern search algorithm for the optimization, applied to a finite element discretization of the problem, we are able to determine optimal configurations of microfluidic devices. Copyright © 2009 John Wiley & Sons, Ltd.     

ILUS: An incomplete LU preconditioner in sparse skyline format

Incomplete LU factorizations are among the most effective preconditioners for solving general large, sparse linear systems arising from practical engineering problems. This paper shows how an ILU factorization may be easily computed in sparse skyline storage format, as opposed to traditional row-by-row schemes. This organization of the factorization has many advantages, including its amenability when the original matrix is in skyline format, the ability to dynamically monitor the stability of the factorization and the fact that factorizations may be produced with symmetric structure. Numerical results are presented for Galerkin finite element matrices arising from the standard square lid-driven cavity problem. © 1997 John Wiley & Sons, Ltd.     

Fast boundary‐domain integral algorithm for the computation of incompressible fluid flow problems

The paper deals with the numerical solution of fluid dynamics using the boundary‐domain integral method (BDIM). A velocity–vorticity formulation of the Navier–Stokes equations is adopted, where the kinematic equation is written in its parabolic form. Computational aspects of the numerical simulation of two‐dimensional flows is described in detail. In order to lower the computational cost, the subdomain technique is applied. A preconditioned Krylov subspace method (PKSM) is used for the solution of systems of linear equations. Level‐based fill‐in incomplete lower upper decomposition (ILU) preconditioners are developed and their performance is examined. Scaling of stopping criteria is applied to minimize the number of iterations for the PKSM. The effectiveness of the proposed method is tested on several benchmark test problems. Copyright © 1999 John Wiley & Sons, Ltd.     

A design of residual error estimates for a high order BDF‐DGFE method applied to compressible flows

We deal with the numerical solution of the non‐stationary compressible Navier–Stokes equations with the aid of the backward difference formula – discontinuous Galerkin finite element method. This scheme is sufficiently stable, efficient and accurate with respect to the space as well as time coordinates. The nonlinear algebraic systems arising from the backward difference formula – discontinuous Galerkin finite element discretization are solved by an iterative Newton‐like method. The main benefit of this paper are residual error estimates that are able to identify the computational errors following from the space and time discretizations and from the inexact solution of the nonlinear algebraic systems. Thus, we propose an efficient algorithm where the algebraic, spatial and temporal errors are balanced. The computational performance of the proposed method is demonstrated by a list of numerical experiments. Copyright © 2013 John Wiley & Sons, Ltd.     

High‐order ILU preconditioners for CFD problems

This paper tests a number of incomplete lower–upper (ILU)‐type preconditioners for solving indefinite linear systems, which arise from complex applications such as computational fluid dynamics (CFD). Both point and block preconditioners are considered. The paper focuses on ILU factorization that can be computed with high accuracy by allowing liberal amounts of fill‐in. A number of strategies for enhancing the stability of the factorizations are examined. Copyright © 2000 John Wiley & Sons, Ltd.