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.     

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.     

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.     

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.     

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.     

COMPUTATION OF TRANSIENT NONLINEAR SHIP WAVES USING AN ADAPTIVE ALGORITHM

An indirect boundary integral method is used to solve transient nonlinear ship wave problems. A resulting mixed boundary value problem is solved at each time-step using a mixed Eulerian– Lagrangian time integration technique. Two dynamic node allocation techniques, which basically distribute nodes on an ever changing body surface, are presented. Both two-sided hyperbolic tangent and variational grid generation algorithms are developed and compared on station curves. A ship hull form is generated in parametric space using a B-spline surface representation. Two-sided hyperbolic tangent and variational adaptive curve grid-generation methods are then applied on the hull station curves to generate effective node placement. The numerical algorithm, in the first method, used two stretching parameters. In the second method, a conservative form of the parametric variational Euler–Lagrange equations is used the perform an adaptive gridding on each station. The resulting unsymmetrical influence coefficient matrix is solved using both a restarted version of GMRES based on the modified Gram–Schmidt procedure and a line Jacobi method based on LU decomposition. The convergence rates of both matrix iteration techniques are improved with specially devised preconditioners. Numerical examples of node placements on typical hull cross-sections using both techniques are discussed and fully nonlinear ship wave patterns and wave resistance computations are presented.     

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 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.     

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.     

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.     

Multibody graph transformations and analysis

This two-part paper uses graph transformation methods to develop methods for partitioning, aggregating, and constraint embedding for multibody systems. This first part focuses on tree-topology systems and reviews the key notion of spatial kernel operator (SKO) models for such systems. It develops systematic and rigorous techniques for partitioning SKO models in terms of the SKO models of the component subsystems based on the path-induced property of the component subgraphs. It shows that the sparsity structure of key matrix operators and the mass matrix for the multibody system can be described using partitioning transformations. Subsequently, the notions of node contractions and subgraph aggregation and their role in coarsening graphs are discussed. It is shown that the tree property of a graph is preserved after subgraph aggregation if and only if the subgraph satisfies an aggregation condition. These graph theory ideas are used to develop SKO models for the aggregated tree multibody systems.     

Efficient solution techniques for implicit finite element schemes with flux limiters

The algebraic flux correction (AFC) paradigm is equipped with efficient solution strategies for implicit time‐stepping schemes. It is shown that Newton‐like techniques can be applied to the nonlinear systems of equations resulting from the application of high‐resolution flux limiting schemes. To this end, the Jacobian matrix is approximated by means of first‐ or second‐order finite differences. The edge‐based formulation of AFC schemes can be exploited to devise an efficient assembly procedure for the Jacobian. Each matrix entry is constructed from a differential and an average contribution edge by edge. The perturbation of solution values affects the nodal correction factors at neighbouring vertices so that the stencil for each individual node needs to be extended. Two alternative strategies for constructing the corresponding sparsity pattern of the resulting Jacobian are proposed. For nonlinear governing equations, the contribution to the Newton matrix which is associated with the discrete transport operator is approximated by means of divided differences and assembled edge by edge. Numerical examples for both linear and nonlinear benchmark problems are presented to illustrate the superiority of Newton methods as compared to the standard defect correction approach. Copyright © 2007 John Wiley & Sons, Ltd.     

结构的多机并行分析I——结构的并行有限元方法

本文详细分析和讨论了结构分析的并行有限元方法—并行预处理共轭梯度法(以下简称PPCG法)。着重讨论了基于自带存储器的多处理机系统的并行预处理算法问题,并由此提出了两种PPCG法:PPCG1和PPCG2法。这两种方法适用于以单道剖分(one-way dissection)的子结构法为基础的并行分析。由于这种剖分法产生的结构刚度矩阵具有箭头形状,可独立地消除各子结构的内部自由度,并且不会在刚度矩阵中产生新的非零元素,因此很适合具有较多处理机的并行机系统对复杂结构进行的并行分析。     

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.     

Eigenfunction expansion method of upper triangular operator matrix and application to two-dimensional elasticity problems based on stress formulation

This paper studies the eigenfunction expansion method to solve the two-dimensional(2D) elasticity problems based on the stress formulation.The fundamentalsystem of partial differential equations of the 2D problems is rewritten as an upper tri-angular differential system based on the known results,and then the associated uppertriangular operator matrix matrix is obtained.By further research,the two simpler com-plete orthogonal systems of eigenfunctions in some space are obtained,which belong tothe two block operators arising in the operator matrix.Then,a more simple and conve-nient general solution to the 2D problem is given by the eigenfunction expansion method.Furthermore,the boundary conditions for the 2D problem,which can be solved by thismethod,are indicated.Finally,the validity of the obtained results is verified by a specificexample.     

Eigenfunction expansion method and its application to two-dimensional elasticity problems based on stress formulation

This paper proposes an eigenfunction expansion method to solve twodimensional （2D） elasticity problems based on stress formulation. By introducing appropriate state functions, the fundamental system of partial differential equations of the above 2D problems is rewritten as an upper triangular differential system. For the associated operator matrix, the existence and the completeness of two normed orthogonal eigenfunction systems in some space are obtained, which belong to the two block operators arising in the operator matrix. Moreover, the general solution to the above 2D problem is given by the eigenfunction expansion method.     

随机结构系统的一般实矩阵特征值问题的概率分析

由于工程实际结构的复杂性和所用材料在统计上的离散性以及测量、加工、制造误差的存在，必然导致具有随机参数的随机结构振动系统，按结构参数的性质来划分，随机振动问题包括两方面内容：(1)确定结构问题；(2)随机结构问题。本文以现代数学理论为依托，研究了随机结构系统的一般实矩阵的特征值问题。根据Kronecker代数、向量值和矩阵值函数的灵敏度分析、一般二阶矩法和概率摄动技术给出了计算随机结构系统的一般实矩阵的特征值和特征向量的数值方法，可以有效地得出随机结构系统的一般实矩阵的特征向量的统计量，发展了2D矩阵值函数的随机结构系统的特征值问题概率分析理论。     

Evaluation of the deflated preconditioned CG method to solve bubbly and porous media flow problems on GPU and CPU

In both bubbly and porous media flow, the jumps in coefficients may yield an ill‐conditioned linear system. The solution of this system using an iterative technique like the conjugate gradient (CG) is delayed because of the presence of small eigenvalues in the spectrum of the coefficient matrix. To accelerate the convergence, we use two levels of preconditioning. For the first level, we choose between out‐of‐the‐box incomplete LU decomposition, sparse approximate inverse, and truncated Neumann series‐based preconditioner. For the second level, we use deflation. Through our experiments, we show that it is possible to achieve a computationally fast solver on a graphics processing unit. The preconditioners discussed in this work exhibit fine‐grained parallelism. We show that the graphics processing unit version of the two‐level preconditioned CG can be up to two times faster than a dual quad core CPU implementation. John Wiley & Sons, Ltd.