Parallelism in ILU-preconditioned GMRES

A parallel implementation of the preconditioned GMRES method is described. The method is used to solve the discretized incompressible Navier–Stokes equations. A parallel implementation of the inner product is given, which appears to be scalable on a massively parallel computer. The most difficult part to parallelize is the ILU-preconditioner. We parallelize the preconditioner using ideas proposed by Bastian and Horton (P. Bastian, G. Horton, SIAM. J. Stat. Comput. 12 (1991) 1457–1470). Contrary to some other parallel methods, the required number of iterations is independent of the number of processors used. A model is presented to predict the efficiency of the method. Experiments are done on the Cray T3D, computing the solution of a two-dimensional incompressible flow. Predictions of computing time show good correspondence with measurements.     

Two augmentation preconditioners for nonsymmetric and indefinite saddle point linear systems with singular (1, 1) blocks

In this paper, two preconditioners based on augmentation are introduced for the solution of large saddle point-type systems with singular (1, 1) blocks. We study the spectral characteristics of the preconditioners, show that all eigenvalues of preconditioned matrices are strongly clustered. Finally, numerical experiments are also reported for illustrating the efficiency of the presented preconditioners.     

Computing the null space of finite element problems

We present a method for computing the null space of finite element models, including models with equality constraints. The method is purely algebraic; it requires access to the element matrices, but not to the geometry or material properties of the model.Theoretical considerations show that under certain conditions, both the amount of computation and the amount of memory required by our method scale linearly with model size; memory scales linearly but computation scales quadratically with the dimension of the null space. Our experiments confirm this: the method scales extremely well on 3-dimensional model problems. In general, large industrial models do not satisfy all the conditions that the theoretical results assume; however, experimentally the method performs well and outperforms an established method on industrial models, including models with many equality constraints.The accuracy of the computed null vectors is acceptable, but the method is usually less accurate than a more naive (and computationally much more expensive) method.     

Block preconditioners with circulant blocks for general linear systems

Block preconditioner with circulant blocks (BPCB) has been used for solving linear systems with block Toeplitz structure since 1992 [R. Chan, X. Jin, A family of block preconditioners for block systems, SIAM J. Sci. Statist. Comput. (13) (1992) 1218–1235]. In this new paper, we use BPCBs to general linear systems (with no block structure usually). The BPCBs are constructed by partitioning a general matrix into a block matrix with blocks of the same size and then applying T. Chan’s optimal circulant preconditioner [T. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. (9) (1988) 766–771] to each block. These BPCBs can be viewed as a generalization of T. Chan’s preconditioner. It is well-known that the optimal circulant preconditioner works well for solving some structured systems such as Toeplitz systems by using the preconditioned conjugate gradient (PCG) method, but it is usually not efficient for solving general linear systems. Unlike T. Chan’s preconditioner, BPCBs used here are efficient for solving some general linear systems by the PCG method. Several basic properties of BPCBs are studied. The relations of the block partition with the cost per iteration and the convergence rate of the PCG method are discussed. Numerical tests are given to compare the cost of the PCG method with different BPCBs.     

预条件的平方Smith法求解大型Sylvester矩阵方程

提出了一种预条件的平方Smith算法求解大型连续Sylvester矩阵方程,该算法利用交替方向隐式迭代(ADI)来构造预条件算子,将原方程转换为非对称Stein方程,并在Krylov子空间中应用平方Smith法迭代产生低秩逼近解。数值实验表明,与已知的Jacobi迭代法等算法相比,该算法有更好的迭代效率和收敛精度。     

An efficient solver for the RANS equations and a one-equation turbulence model

A three-stage Runge-Kutta (RK) scheme with multigrid and an implicit preconditioner has been shown to be an effective solver for the fluid dynamic equations. Using the algebraic turbulence model of Baldwin and Lomax, this scheme has been used to solve the compressible Reynolds-averaged Navier–Stokes (RANS) equations for transonic and low-speed flows. In this paper we focus on the convergence of the RK/Implicit scheme when the effects of turbulence are represented by the one-equation model of Spalart and Allmaras. With the present scheme the RANS equations and the partial differential equation of the turbulence model are solved in a loosely coupled manner. This approach allows the convergence behavior of each system to be examined. Point symmetric Gauss-Seidel supplemented with local line relaxation is used to approximate the inverse of the implicit operator of the RANS solver. To solve the turbulence equation we consider three alternative methods: diagonally dominant alternating direction implicit (DDADI), symmetric line Gauss-Seidel (SLGS), and a two-stage RK scheme with implicit preconditioning. Computational results are presented for airfoil flows, and comparisons are made with experimental data. We demonstrate that the two-dimensional RANS equations and a transport-type equation for turbulence modeling can be efficiently solved with an indirectly coupled algorithm that uses RK/Implicit schemes.     

A symmetric positive definite preconditioner for saddle-point problems

For the classical saddle-point problem, we present precisely two intervals containing the positive and the negative eigenvalues of the preconditioned matrix, respectively, when the inexact version of the symmetric positive definite preconditioner introduced in Section 2.1 of Gill et al. [Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl. 13 (1992), pp. 292–311] is employed. The model of Stokes problem is used to test the effectiveness of the presented bounds as well as the quality of the symmetric positive definite preconditioner.     

Block constrained versus generalized Jacobi preconditioners for iterative solution of large-scale Biot’s FEM equations

Generalized Jacobi (GJ) diagonal preconditioner coupled with symmetric quasi-minimal residual (SQMR) method has been demonstrated to be efficient for solving the 2 × 2 block linear system of equations arising from discretized Biot’s consolidation equations. However, one may further improve the performance by employing a more sophisticated non-diagonal preconditioner. This paper proposes to employ a block constrained preconditioner P_c that uses the same 2 × 2 block matrix but its (1, 1) block is replaced by a diagonal approximation. Numerical results on a series of 3-D footing problems show that the SQMR method preconditioned by P_c is about 55% more efficient time-wise than the counterpart preconditioned by GJ when the problem size increases to about 180,000 degrees of freedom. Over the range of problem sizes studied, the P_c-preconditioned SQMR method incurs about 20% more memory than the GJ-preconditioned counterpart. The paper also addresses crucial computational and storage issues in constructing and storing P_c efficiently to achieve superior performance over GJ on the commonly available PC platforms.     

适用于GRAPES数值天气预报软件的ILU预条件子

探讨了一种适用于我国自主研发的数值天气预报模式软件GRAPES的不完全LU(ILU)分解预条件子.针对GRAPES模式所特有的具有对角优势结构的赫姆霍兹方程系数矩阵,提出了一种有效的ILU分解方案,并将分解得到的预条件子应用到模式核心的动力积分计算迭代算法中,从而达到加速算法收敛,提高模式软件整体性能的目的.     

Parameterized ABD preconditioning technique for time-periodic convection–diffusion problems

In this paper, a parameterized additive block diagonal (PABD) preconditioning technique is present for solving the nine-point approximations of the time-periodic convection–diffusion problems. The explicit expressions for the eigenvalues and eigenvectors of the corresponding preconditioned matrices are presented. The range of the optimal parameters is derived. Numerical experiments show that the generalized minimal residual method preconditioned by the PABD preconditioner with the experimental optimal parameters or some special values is effective for a wide range of problem sizes.