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 comparison of preconditioners for incompressible Navier–Stokes solvers

We consider solution methods for large systems of linear equations that arise from the finite element discretization of the incompressible Navier–Stokes equations. These systems are of the so‐called saddle point type, which means that there is a large block of zeros on the main diagonal. To solve these types of systems efficiently, several block preconditioners have been published. These types of preconditioners require adaptation of standard finite element packages. The alternative is to apply a standard ILU preconditioner in combination with a suitable renumbering of unknowns. We introduce a reordering technique for the degrees of freedom that makes the application of ILU relatively fast. We compare the performance of this technique with some block preconditioners. The performance appears to depend on grid size, Reynolds number and quality of the mesh. For medium‐sized problems, which are of practical interest, we show that the reordering technique is competitive with the block preconditioners. Its simple implementation makes it worthwhile to implement it in the standard finite element method software. Copyright © 2007 John Wiley & Sons, Ltd.     

Numerical solutions of fully non‐linear and highly dispersive Boussinesq equations in two horizontal dimensions

This paper investigates preconditioned iterative techniques for finite difference solutions of a high‐order Boussinesq method for modelling water waves in two horizontal dimensions. The Boussinesq method solves simultaneously for all three components of velocity at an arbitrary z‐level, removing any practical limitations based on the relative water depth. High‐order finite difference approximations are shown to be more efficient than low‐order approximations (for a given accuracy), despite the additional overhead. The resultant system of equations requires that a sparse, unsymmetric, and often ill‐conditioned matrix be solved at each stage evaluation within a simulation. Various preconditioning strategies are investigated, including full factorizations of the linearized matrix, ILU factorizations, a matrix‐free (Fourier space) method, and an approximate Schur complement approach. A detailed comparison of the methods is given for both rotational and irrotational formulations, and the strengths and limitations of each are discussed. Mesh‐independent convergence is demonstrated with many of the preconditioners for solutions of the irrotational formulation, and solutions using the Fourier space and approximate Schur complement preconditioners are shown to require an overall computational effort that scales linearly with problem size (for large problems). Calculations on a variable depth problem are also compared to experimental data, highlighting the accuracy of the model. Through combined physical and mathematical insight effective preconditioned iterative solutions are achieved for the full physical application range of the model. Copyright © 2004 John Wiley & Sons, Ltd.     

A preconditioned alternating inner-outer iterative solution method for the mixed finite element formulation of the Navier-Stokes equations

In the present work a new iterative method for solving the Navier-Stokes equations is designed. In a previous paper a coupled node fill-in preconditioner for iterative solution of the Navier-Stokes equations proved to increase the convergence rate considerably compared with traditional preconditioners. The further development of the present iterative method is based on the same storage scheme for the equation matrix as for the coupled node fill-in preconditioner. This storage scheme separates the velocity, the pressure and the coupling of pressure and velocity coefficients in the equation matrix. The separation storage scheme allows for an ILU factorization of both the velocity and pressure unknowns. With the inner-outer solution scheme the velocity unknowns are eliminated before the resulting equation system for the pressures is solved iteratively. After the pressure unknown has been found, the pressures are substituted into the original equation system and the velocities are also found iteratively. The behaviour of the inner-outer iterative solution algorithm is investigated in order to find optimal convergence criteria for the inner iterations and compared with the solution algorithm for the original equation system. The results show that the coupled node fill-in preconditioner of the original equation system is more efficient than the coupled node fill-in preconditioner of the reduced equation system. However, the solution technique of the reduced equation system revals properties which may be advantageous in future solution algorithms.     

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.     

ROBUST NUMERICAL METHODS FOR TRANSONIC FLOWS

In this paper, numerical methods for solving the transonic full potential equation are developed. The governing equation is discretized by a flux-biasing finite volume method. The resulting non-linear algebraic system is solved by using a continuation method with full Newton iteration. The continuation method is based on solving a highly ‘upstream-weighted’ discretization and then gradually reducing the upstream weighting. A general PCG-like sparse matrix iterative solver is used to solve the Jacobians at each non-linear step. Various types of incomplete LU (ILU) preconditioners and ordering techniques are compared. Numerical results are presented to demonstrate that these methods are efficient and robust for solving the transonic potential equation in the workstation computing environment. © 1997 by John Wiley & Sons, Ltd.     

ℋ︁‐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.     

An ILU preconditioner with coupled node fill-in for iterative solution of the mixed finite element formulation of the 2D and 3D Navier-Stokes equations

In the present paper, preconditioning of iterative equation solvers for the Navier-Stokes equations is investigated. The Navier-Stokes equations are solved for the mixed finite element formulation. The linear equation solvers used are the orthomin and the Bi-CGSTAB algorithms. The storage structure of the equation matrix is given special attention in order to avoid swapping and thereby increase the speed of the preconditioner. The preconditioners considered are Jacobian, SSOR and incomplete LU preconditioning of the matrix associated with the velocities. A new incomplete LU preconditioning with fill-in for the pressure matrix at locations in the matrix where the corner nodes are coupled is designed. For all preconditioners, inner iterations are investigated for possible improvement of the preconditioning. Numerical experiments are executed both in two and three dimensions.     

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.     

A parallel finite element sliding mesh technique for the simulation of viscous flows in agitated tanks

A parallel sliding mesh algorithm for the finite element simulation of viscous fluid flows in agitated tanks is presented. Lagrange multipliers are used at the sliding interfaces to enforce the continuity between the fixed and moving subdomains. The novelty of the method consists of the coupled solution of the resulting velocity–pressure‐Lagrange multipliers system of equations by an ILU(0)‐QMR solver. A penalty parameter is introduced for both the interface and the incompressibility constraints to avoid pivoting problems in the ILU(0) algorithm. To handle the convective term, both the Newton–Raphson scheme and the semi‐implicit linearization are tested. A penalty parameter is introduced for both the interface and the incompressibility constraints to avoid the failure of the ILU(0) algorithm due to the lack of pivoting. Furthermore, this approach is versatile enough so that it allows partitioning of sliding and fixed subdomains if parallelization is required. Although the sliding mesh technique is fairly common in CFD, the main advantage of the proposed approach is its low computational cost due to the inexpensive and parallelizable calculations that involve preconditioned sparse iterative solvers. The method is validated for Couette and coaxial stirred tanks. Copyright © 2011 John Wiley & Sons, Ltd.     

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.     

Two preconditioners for saddle point problems in fluid flows

In this paper two preconditioners for the saddle point problem are analysed: one based on the augmented Lagrangian approach and another involving artificial compressibility. Eigenvalue analysis shows that with these preconditioners small condition numbers can be achieved for the preconditioned saddle point matrix. The preconditioners are compared with commonly used preconditioners from literature for the Stokes and Oseen equation and an ocean flow problem. The numerical results confirm the analysis: the preconditioners are a good alternative to existing ones in fluid flow problems. Copyright © 2006 John Wiley & Sons, Ltd.     

A Newton–Krylov finite volume algorithm for the power-law non-Newtonian fluid flow using pseudo-compressibility technique

An implicit Newton–Krylov finite volume algorithm has been developed for efficient steady-state computation of the power-law non-Newtonian fluid flows. The pseudo-compressibility technique is used for the coupling of continuity and momentum equations. The spatial discretization is central (second-order) for both convective and diffusive terms and the accuracy of the solution is verified. The nine block diagonal Jacobian matrix (needed for implicit formulation) is computed directly through the flux differentiation. Five-diagonal and three-diagonal block matrices (the simplified versions of the main Jacobian matrix) are used with the ILU(0 & 1) and the Thomas linear solvers for preconditioning, respectively. The performance of the Newton-GMRES solver is examined in detail for different preconditioning strategies. The effects of the power-law behavior index and Re number on the convergence rate are also studied. The performance of the Newton-BiCGSTAB and the Newton-GMRES solvers are compared with each other. The results show, the ILU(1)/Newton-GMRES is the most efficient combination that is robust even in high Reynolds number shear-thinning fluid flow cases.     

A control volume finite‐element method for numerical simulating incompressible fluid flows without pressure correction

This paper presents a numerical model to study the laminar flows induced in confined spaces by natural convection. A control volume finite‐element method (CVFEM) with equal‐order meshing is employed to discretize the governing equations in the pressure–velocity formulation. In the proposed model, unknown variables are calculated in the same grid system using different specific interpolation functions without pressure correction. To manage memory storage requirements, a data storage format is developed for generated sparse banded matrices. The performance of various Krylov techniques, including Bi‐CGSTAB (Bi‐Conjugate Gradient STABilized) with an incomplete LU (ILU) factorization preconditioner is verified by applying it to three well‐known test problems. The results are compared to those of independent numerical or theoretical solutions in literature. The iterative computer procedure is improved by using a coupled strategy, which consists of solving simultaneously the momentum and the continuity equation transformed in a pressure equation. Results show that the strategy provides useful benefits with respect to both reduction of storage requirements and central processing unit runtime. Copyright © 2006 John Wiley & Sons, Ltd.     

Parallel ILU preconditioning,a priori pivoting and segregation of variables for iterative solution of the mixed finite element formulation of the Navier–Stokes equations

A parallel ILU preconditioning algorithm for the incompressible Navier–Stokes equations has been designed, implemented and tested. The computational mesh is divided into N subdomains which are processed in parallel in different processors. During ILU factorization, matrices and vectors associated with the nodes on the interface between the subdomains are communicated to the equation matrices to the adjacent subdomain. The bases for the parallel algorithm are an appropriate node ordering scheme and a segregation of velocity and pressure degrees of freedom. The inner nodes of the subdomain are numbered first and then the nodes on the interface between the subdomains. To avoid division by zero during the ILU factorization, the equations corresponding to the velocity degrees of freedom are assembled first in the global equation matrix, followed by the equations corresponding to the pressure degrees of freedom. Copyright © 2003 John Wiley & Sons, Ltd.     

Parallel Iterative Solvers with Localized ILU Preconditioning for Unstructured Grids on Workstation Clusters

Incomplete Lower-Upper (0) (ILU(O)) factorization is a very effective preconditioning method of iterative solvers for large-scale linear sparse systems in scientific and engineering computations. However, this method requires global data dependency, which is not ideal for parallel computations in which locality is of utmost importance.

In this paper, the localized ILU(O) preconditioning method is implemented in various types of iterative solvers. This method provides data locality and good parallelization on each processor. The performance of the developed system was evaluated on a workstation cluster using MPI.

In 1997, the Science and Technology Agency of Japan (STA) began a five-year project to develop the Earth Simulator. Both hardware and software for various types of global earth simulation are to be developed under this project. The present study was conducted as part of the research on software for solid earth simulation. This simulation code, named GeoFEM, solves crust deformation, mantle convection, seismic wave propagation, etc., using the finite element method.     

Efficient multigrid preconditioners for atmospheric flow simulations at high aspect ratio

Many problems in fluid modelling require the efficient solution of highly anisotropic elliptic partial differential equations (PDEs) in ‘flat’ domains. For example, in numerical weather and climate prediction, an elliptic PDE for the pressure correction has to be solved at every time step in a thin spherical shell representing the global atmosphere. This elliptic solve can be one of the computationally most demanding components in semi‐implicit semi‐Lagrangian time stepping methods, which are very popular as they allow for larger model time steps and better overall performance. With increasing model resolution, algorithmically efficient and scalable algorithms are essential to run the code under tight operational time constraints. We discuss the theory and practical application of bespoke geometric multigrid preconditioners for equations of this type. The algorithms deal with the strong anisotropy in the vertical direction by using the tensor‐product approach originally analysed by Börm and Hiptmair [Numer. Algorithms, 26/3 (2001), pp. 219–234]. We extend the analysis to three dimensions under slightly weakened assumptions and numerically demonstrate its efficiency for the solution of the elliptic PDE for the global pressure correction in atmospheric forecast models. For this, we compare the performance of different multigrid preconditioners on a tensor‐product grid with a semi‐structured and quasi‐uniform horizontal mesh and a one‐dimensional vertical grid. The code is implemented in the Distributed and Unified Numerics Environment, which provides an easy‐to‐use and scalable environment for algorithms operating on tensor‐product grids. Parallel scalability of our solvers on up to 20 480 cores is demonstrated on the HECToR supercomputer. Copyright © 2015 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.     

Unstructured pressure‐correction solver based on a consistent discretization of the Poisson equation

A finite volume incompressible flow solver is presented for three‐dimensional unsteady flows based on an unstructured tetrahedral mesh, with collocation of the flow variables at the cell vertices. The solver is based on the pressure‐correction method, with an explicit prediction step of the momentum equations followed by a Poisson equation for the correction step to enforce continuity. A consistent discretization of the Poisson equation was found to be essential in obtaining a solution. The correction step was solved with the biconjugate gradient stabilized (Bi‐CGSTAB) algorithm coupled with incomplete lower–upper (ILU) preconditioning. Artificial dissipation is used to prevent the formation of instabilities. Flow solutions are presented for a stalling airfoil, vortex shedding past a bridge deck and flow in model alveoli. Copyright © 2000 John Wiley & Sons, Ltd.