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.     

Application of conjugate-gradient-like methods to a hyperbolic problem in porous-media flow

This paper presents the application of a preconditioned conjugate-gradient-like method to a non-self-adjoint problem of interest in underground flow simulation. The method furnishes a reliable iterative solution scheme for the non-symmetric matrices arising at each iteration of the non-linear time-stepping scheme. The method employs a generalized conjugate residual scheme with nested factorization as a preconditioner. Model runs demonstrate significant computational savings over direct sparse matrix solvers.     

Linear and non-linear iterative methods for the incompressible Navier-Stokes equations

In this study, the discretized finite volume form of the two-dimensional, incompressible Navier-Stokes equations is solved using both a frozen coefficient and a full Newton non-linear iteration. The optimal method is a combination of these two techniques. The linearized equations are solved using a conjugate-gradient-like method (CGSTAB). Various types of preconditioning are developed. Completely general sparse matrix methods are used. Investigations are carried out to determine the effect of finite volume cell anisotropy on the preconditioner. Numerical results are given for several test problems.     

Preconditioned conjugate gradient methods for the incompressible Navier-Stokes equations

A robust technique for solving primitive variable formulations of the incompressible Navier-Stokes equations is to use Newton iteration for the fully implicit non-linear equations. A direct sparse matrix method can be used to solve the Jacobian but is costly for large problems; an alternative is to use an iterative matrix method. This paper investigates effective ways of using a conjugate-gradient-type method with an incomplete LU factorization preconditioner for two-dimensional incompressible viscous flow problems. Special attention is paid to the ordering of unknowns, with emphasis on a minimum updating matrix (MUM) ordering. Numerical results are given for several test problems.     

基于全隐式无分裂算法求解三维N-S方程

基于多块结构网格,本文研究和发展了三维N-S方程的全隐式无分裂算法.对流项的离散运用Roe格式,粘性项的离散利用中心型格式.在每一次隐式时间迭代中,运用GMRES方法直接求解隐式离散引起的大型稀疏线性方组.为了降低内存需求以及矩阵与向量之间的运算操作数,Jacobian矩阵的一种逼近方法被应用在本文的算法之中.计算结果与实验结果基本吻合,表明本文的全隐式无分裂方法是有效和可行的.     

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

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

A finite element solutionof three-dimensional mixed convection gas flows in horizontal chnnels using preconditioned iterative metrix methods

An algorithm is presented for the finite element solution of three-dimensional mixed convection gas flows in channels heated from below. The algorithm uses Newton's method and iterative matrix methods. Two iterative solution algorithms, conjugate gradient squared (CGS) and generalized minimal residual (GMERS), are used in conjunction with a preconditioning technique that is simple to implement. The preconditioner is a subset of the full Jacobian matrix centered around the main diagonal but retaining the most fundamental axial coupling of the residual equations. A domain-renumbering scheme that enhances the overall algorithm performance is proposed on the basis of and analysis of the preconditioner. Comparison with the frontal elimination method demonstrates that the iterative method will be faster when the front width exceeds approximately 500. Techniques for the direct assembly f the problem into a compressed sparse row storage format are demonstrated. Elimination of fixed boundary conditions is shown to decrease the size of the matrix problem by up to 30%. Finally, fluid flow solutions obtained with the numerical technique are presented. These solutions reveal complex three-dimensional mixed convection fluid flow phenomena at low Reynolds numbers, including the reversal of the direction of longitudinal rolls in the presence of a strong recirculation in the entrance region of the channel.     

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.     

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.     

Multilevel functional preconditioning for shape optimisation

We study the application of a multi-level preconditioner to a practical optimal shape design problem. The preconditioner is based on the Bramble-Pasciak-Xu (BPX) series. We extend it to the unstructured parametrization of 3D shapes by using the volume–agglomeration heuristics. The choice of the smoothing parameter is analysed from functional arguments. Application to the shape design for optimising aerodynamic and sonic boom performances of a wing is demonstrated.     

两类网格结构模型的预处理方法

针对参考节点分别为q=3和q=4的网格结构模型,设计了两种预处理方法:以块对角逆为预条件子的共轭梯度法(BPCG)及以块下三角逆为预条件子的PGMRES法。数值结果表明,BPCG法对q=3具有很好的求解效率和鲁棒性,但对q=4的情形,特别是当α很小时,其求解效率将变得很差。当α很小时,以块下三角逆为预条件子的PGMRES法对求解q=4的蜂窝状结构在计算CPU和算法稳定性等方面均全面占优。在这两种预处理方法中,利用了基于标量椭圆问题的GAMG法求各个子块矩阵的逆,以提高内迭代运算效率。近似连续方程的建立为内迭代方法的合理性提供了有效的理论支撑。     

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.     

Application of point implicit Runge–Kutta methods to inviscid and laminar flow problems using AUSM and AUSM+ upwinding

Explicit Runge–Kutta methods preconditioned by a pointwise matrix valued preconditioner can significantly improve the convergence rate to approximate steady state solutions of laminar flows. This has been shown for central discretisation schemes and Roe upwinding. Since the first-order approximation to the inviscid flux assuming constant weighting of the dissipative terms is given by the absolute value of the Roe matrix, the construction of the preconditioner is rather simple compared to other upwind techniques. However, in this article we show that similar improvements in the convergence rates can also be obtained for the AUSM⁺ scheme. Following the ideas for the central and Roe schemes, the preconditioner is obtained by a first-order approximation to the derivative of the convective flux. Viscous terms are included into the preconditioner considering a thin shear layer approximation. A complete derivation of the derivative terms is shown. In numerical examples, we demonstrate the improved convergence rates when compared with a standard explicit Runge–Kutta method accelerated with local time stepping.     

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.     

Efficient computation of two‐dimensional steady free‐surface flows

We consider a family of steady free‐surface flow problems in two dimensions, concentrating on the effect of nonlinearity on the train of gravity waves that appear downstream of a disturbance. By exploiting standard complex variable techniques, these problems are formulated in terms of a coupled system of Bernoulli equation and an integral equation. When applying a numerical collocation scheme, the Jacobian for the system is dense, as the integral equation forces each of the algebraic equations to depend on each of the unknowns. We present here a strategy for overcoming this challenge, which leads to a numerical scheme that is much more efficient than what is normally used for these types of problems, allowing for many more grid points over the free surface. In particular, we provide a simple recipe for constructing a sparse approximation to the Jacobian that is used as a preconditioner in a Jacobian‐free Newton‐Krylov method for solving the nonlinear system. We use this approach to compute numerical results for a variety of prototype problems including flows past pressure distributions, a surface‐piercing object and bottom topographies.     

Analysis of preconditioned iterative solvers for incompressible flow problems

Solving efficiently the incompressible Navier–Stokes equations is a major challenge, especially in the three‐dimensional case. The approach investigated by Elman et al. (Finite Elements and Fast Iterative Solvers. Oxford University Press: Oxford, 2005) consists in applying a preconditioned GMRES method to the linearized problem at each iteration of a nonlinear scheme. The preconditioner is built as an approximation of an ideal block‐preconditioner that guarantees convergence in 2 or 3 iterations. In this paper, we investigate the numerical behavior for the three‐dimensional lid‐driven cavity problem with wedge elements; the ultimate motivation of this analysis is indeed the development of a preconditioned Krylov solver for stratified oceanic flows which can be efficiently tackled using such meshes. Numerical results for steady‐state solutions of both the Stokes and the Navier–Stokes problems are presented. Theoretical bounds on the spectrum and the rate of convergence appear to be in agreement with the numerical experiments. Sensitivity analysis on different aspects of the structure of the preconditioner and the block decomposition strategies are also discussed. Copyright © 2011 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.     

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 domain decomposition method for modelling Stokes flow in porous materials

An algorithm is presented for solving the Stokes equation in large disordered two‐dimensional porous domains. In this work, it is applied to random packings of discs, but the geometry can be essentially arbitrary. The approach includes the subdivision of the domain and a subsequent application of boundary integral equations to the subdomains. This gives a block diagonal matrix with sparse off‐block components that arise from shared variables on internal subdomain boundaries. The global problem is solved using a biconjugate gradient routine with preconditioning. Results show that the effectiveness of the preconditioner is strongly affected by the subdomain structure, from which a methodology is proposed for the domain decomposition step. A minimum is observed in the solution time versus subdomain size, which is governed by the time required for preconditioning, the time for vector multiplications in the biconjugate gradient routine, the iterative convergence rate and issues related to memory allocation. The method is demonstrated on various domains including a random 1000‐particle domain. The solution can be used for efficient recovery of point velocities, which is discussed in the context of stochastic modelling of solute transport. Copyright © 2002 John Wiley & Sons, Ltd.     

PRECONDITIONED GAUSS-SEIDEL TYPE ITERATIVE METHOD FOR SOLVING LINEAR SYSTEMS

The preconditioned Gauss-Seidel type iterative method for solving linear systems, with the proper choice of the preconditioner, is presented. Convergence of the preconditioned method applied to Z-matrices is discussed. Also the optimal parameter is presented. Numerical results show that the proper choice of the preconditioner can lead to effective by the preconditioned Gauss-Seidel type iterative methods for solving linear systems.