Performance of ILU factorization preconditioners based on multisplittings

Summary. In this paper, we study the convergence of multisplitting methods associated with a multisplitting which is obtained from the ILU factorizations of a general H-matrix, and then we propose parallelizable ILU factorization preconditioners based on multisplittings for a block-tridiagonal H-matrix. We also describe a parallelization of preconditioned Krylov subspace methods with the ILU preconditioners based on multisplittings on distributed memory computers such as the Cray T3E. Lastly, parallel performance results of the preconditioned BiCGSTAB are provided to evaluate the efficiency of the ILU preconditioners based on multisplittings on the Cray T3E. Mathematics Subject Classification (2000):65F10, 65Y05, 65F50This work was supported by Korea Research Foundation Grant (KRF-2001-015-DP0051)     

A comparison of preconditioned Krylov subspace methods for large‐scale nonsymmetric linear systems

Preconditioned Krylov subspace (KSP) methods are widely used for solving large‐scale sparse linear systems arising from numerical solutions of partial differential equations (PDEs). These linear systems are often nonsymmetric due to the nature of the PDEs, boundary or jump conditions, or discretization methods. While implementations of preconditioned KSP methods are usually readily available, it is unclear to users which methods are the best for different classes of problems. In this work, we present a comparison of some KSP methods, including GMRES, TFQMR, BiCGSTAB, and QMRCGSTAB, coupled with three classes of preconditioners, namely, Gauss–Seidel, incomplete LU factorization (including ILUT, ILUTP, and multilevel ILU), and algebraic multigrid (including BoomerAMG and ML). Theoretically, we compare the mathematical formulations and operation counts of these methods. Empirically, we compare the convergence and serial performance for a range of benchmark problems from numerical PDEs in two and three dimensions with up to millions of unknowns and also assess the asymptotic complexity of the methods as the number of unknowns increases. Our results show that GMRES tends to deliver better performance when coupled with an effective multigrid preconditioner, but it is less competitive with an ineffective preconditioner due to restarts. BoomerAMG with a proper choice of coarsening and interpolation techniques typically converges faster than ML, but both may fail for ill‐conditioned or saddle‐point problems, whereas multilevel ILU tends to succeed. We also show that right preconditioning is more desirable. This study helps establish some practical guidelines for choosing preconditioned KSP methods and motivates the development of more effective preconditioners.     

A variant of block incomplete factorization preconditioners for a symmetricH-matrix

We propose a variant of parallel block incomplete factorization preconditioners for a symmetric block-tridiagonalH-matrix. Theoretical properties of these block preconditioners are compared with those of block incomplete factorization preconditioners for the corresponding comparison matrix. Numerical results of the preconditioned CG(PCG) method using these block preconditioners are compared with those of PCG using other types of block incomplete factorization preconditioners. Lastly, parallel computations of the block incomplete factorization preconditioners are carried out on the Cray C90.     

Hermite collocation solution of partial differential equations via preconditioned Krylov methods

We are concerned with the numerical solution of partial differential equations (PDEs) in two spatial dimensions discretized via Hermite collocation. To efficiently solve the resulting systems of linear algebraic equations, we choose a Krylov subspace method. We implement two such methods: Bi‐CGSTAB [1] and GMRES [2]. In addition, we utilize two different preconditioners: one based on the Gauss–Seidel method with a block red‐black ordering (RBGS); the other based upon a block incomplete LU factorization (ILU). Our results suggest that, at least in the context of Hermite collocation, the RBGS preconditioner is superior to the ILU preconditioner and that the Bi‐CGSTAB method is superior to GMRES. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:120–136, 2001     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

Low frequency tangential filtering decomposition

For block‐tridiagonal systems of linear equations arising from the discretization of partial differential equations, a composite preconditioner is proposed and tested. It combines a classical ILU0 factorization for high frequencies with a tangential filtering preconditioner. The choice of the filtering vector is important: the test‐vector is the Ritz eigenvector corresponding to the approximate lowest eigenvalue, obtained after a limited number of iterations of a ILU0 preconditioned Krylov method. Numerical tests are carried out for this method. Copyright © 2006 John Wiley & Sons, Ltd.     

A multilevel Crout ILU preconditioner with pivoting and row permutation

In this paper, we present a new incomplete LU factorization using pivoting by columns and row permutation. Pivoting by columns helps to avoid small pivots and row permutation is used to promote sparsity. This factorization is used in a multilevel framework as a preconditioner for iterative methods for solving sparse linear systems. In most multilevel incomplete ILU factorization preconditioners, preprocessing (scaling and permutation of rows and columns of the coefficient matrix) results in further improvements. Numerical results illustrate that these preconditioners are suitable for a wide variety of applications. Copyright © 2007 John Wiley & Sons, Ltd.     

An Algebraic Multigrid-Based Physical Factorization Preconditioner for the Multi-Group Radiation Diffusion Equations in Three Dimensions

The paper investigates the robustness and parallel scaling properties of a novel physical factorization preconditioner with algebraic multigrid subsolves in the iterative solution of a cell-centered finite volume discretization of the three-dimensional multi-group radiation diffusion equations. The key idea is to take advantage of a particular kind of block factorization of the resulting system matrix and approximate the left-hand block matrix selectively spurred by parallel processing considerations. The spectral property of the preconditioned matrix is then analyzed. The practical strategy is considered sequentially and in parallel. Finally, numerical results illustrate the numerical robustness, computational efficiency and parallel strong and weak scalabilities over the real-world structured and unstructured coupled problems, showing its competitiveness with many existing block preconditioners.     

Convergence of nonstationary multisplitting methods using ILU factorizations

In this paper, we first study convergence of nonstationary multisplitting methods associated with a multisplitting which is obtained from the ILU factorizations for solving a linear system whose coefficient matrix is a large sparse H-matrix. We next study a parallel implementation of the relaxed nonstationary two-stage multisplitting method (called Algorithm 2 in this paper) using ILU factorizations as inner splittings and an application of Algorithm 2 to parallel preconditioner of Krylov subspace methods. Lastly, we provide parallel performance results of both Algorithm 2 using ILU factorizations as inner splittings and the BiCGSTAB with a parallel preconditioner which is derived from Algorithm 2 on the IBM p690 supercomputer.     

Parallel block preconditioning based on SSOR and MILU

Two kinds of parallel preconditioners for the solution of large sparse linear systems which arise from the 2-D 5-point finite difference discretization of a convection-diffusion equation are introduced. The preconditioners are based on the SSOR or MILU preconditioners and can be implemented on parallel computers with distributed memories. One is the block preconditioner, in which the interface components of the coefficient matrix between blocks are ignored to attain parallelism in the forward-backward substitutions. The other is the modified block preconditioner, in which the block preconditioner is modified by taking the interface components into account. The effect of these preconditioners on the convergence of preconditioned iterative methods and timing results on the parallel computer (Cenju) are presented.     

Preconditioners for block Toeplitz systems based on circulant preconditioners

We study the numerical solution of a block system T _m,n x=b by preconditioned conjugate gradient methods where T _m,n is an m×m block Toeplitz matrix with n×n Toeplitz blocks. These systems occur in a variety of applications, such as two-dimensional image processing and the discretization of two-dimensional partial differential equations. In this paper, we propose new preconditioners for block systems based on circulant preconditioners. From level-1 circulant preconditioner we construct our first preconditioner q ₁(T _m,n ) which is the sum of a block Toeplitz matrix with Toeplitz blocks and a sparse matrix with Toeplitz blocks. By setting selected entries of the inverse of level-2 circulant preconditioner to zero, we get our preconditioner q ₂(T _m,n ) which is a (band) block Toeplitz matrix with (band) Toeplitz blocks. Numerical results show that our preconditioners are more efficient than circulant preconditioners.     

A class of generalized shift-splitting preconditioners for nonsymmetric saddle point problems

In this paper, a class of generalized shift-splitting preconditioners with two shift parameters are implemented for nonsymmetric saddle point problems with nonsymmetric positive definite (1, 1) block. The generalized shift-splitting (GSS) preconditioner is induced by a generalized shift-splitting of the nonsymmetric saddle point matrix, resulting in an unconditional convergent fixed-point iteration. By removing the shift parameter in the (1, 1) block of the GSS preconditioner, a deteriorated shift-splitting (DSS) preconditioner is presented. Some useful properties of the DSS preconditioned saddle point matrix are studied. Finally, numerical experiments of a model Navier–Stokes problem are presented to show the effectiveness of the proposed preconditioners.     

Numerical study on incomplete orthogonal factorization preconditioners

We design, analyse and test a class of incomplete orthogonal factorization preconditioners constructed from Givens rotations, incorporating some dropping strategies and updating tricks, for the solution of large sparse systems of linear equations. Comprehensive accounts about how the preconditioners are coded, what storage is required and how the computation is executed for a given accuracy are presented. A number of numerical experiments show that these preconditioners are competitive with standard incomplete triangular factorization preconditioners when they are applied to accelerate Krylov subspace iteration methods such as GMRES and BiCGSTAB.     

Block‐triangular preconditioners for PDE‐constrained optimization

In this paper we investigate the possibility of using a block‐triangular preconditioner for saddle point problems arising in PDE‐constrained optimization. In particular, we focus on a conjugate gradient‐type method introduced by Bramble and Pasciak that uses self‐adjointness of the preconditioned system in a non‐standard inner product. We show when the Chebyshev semi‐iteration is used as a preconditioner for the relevant matrix blocks involving the finite element mass matrix that the main drawback of the Bramble–Pasciak method—the appropriate scaling of the preconditioners—is easily overcome. We present an eigenvalue analysis for the block‐triangular preconditioners that gives convergence bounds in the non‐standard inner product and illustrates their competitiveness on a number of computed examples. Copyright © 2010 John Wiley & Sons, Ltd.     

An improved block splitting preconditioner for complex symmetric indefinite linear systems

In this paper, an improved block splitting preconditioner for a class of complex symmetric indefinite linear systems is proposed. By adopting two iteration parameters and the relaxation technique, the new preconditioner not only remains the same computational cost with the block preconditioners but also is much closer to the original coefficient matrix. The theoretical analysis shows that the corresponding iteration method is convergent under suitable conditions and the preconditioned matrix can have well-clustered eigenvalues around (0,1) with a reasonable choice of the relaxation parameters. An estimate concerning the dimension of the Krylov subspace for the preconditioned matrix is also obtained. Finally, some numerical experiments are presented to illustrate the effectiveness of the presented preconditioner.     

几乎各向同性的高维空间分数阶扩散方程的分块快速正则Hermite分裂预处理方法

一类空间分数阶扩散方程经过有限差分离散后所得到的离散线性方程组的系数矩阵是两个对角矩阵与Toeplitz型矩阵的乘积之和.在本文中,对于几乎各向同性的二维或三维空间分数阶扩散方程的离散线性方程组,采用预处理Krylov子空间迭代方法,我们利用其系数矩阵的特殊结构和具体性质构造了一类分块快速正则Hermite分裂预处理子.通过理论分析,我们证明了所对应的预处理矩阵的特征值大部分都聚集于1的附近.数值实验也表明,这类分块快速正则Hermite分裂预处理子可以明显地加快广义极小残量(GMRES)方法和稳定化的双共轭梯度(BiCGSTAB)方法等Krylov子空间迭代方法的收敛速度.     

Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics

This paper presents a class of limited memory preconditioners (LMP) for solving linear systems of equations with symmetric indefinite matrices and multiple right‐hand sides. These preconditioners based on limited memory quasi‐Newton formulas require a small number k of linearly independent vectors and may be used to improve an existing first‐level preconditioner. The contributions of the paper are threefold. First, we derive a formula to characterize the spectrum of the preconditioned operator. A spectral analysis of the preconditioned matrix shows that the eigenvalues are all real and that the LMP class is able to cluster at least k eigenvalues at 1. Secondly, we show that the eigenvalues of the preconditioned matrix enjoy interlacing properties with respect to the eigenvalues of the original matrix provided that the k linearly independent vectors have been prior projected onto the invariant subspaces associated with the eigenvalues of the original matrix in the open right and left half‐plane, respectively. Third, we focus on theoretical properties of the Ritz‐LMP variant, where Ritz information is used to determine the k vectors. Finally, we illustrate the numerical behaviour of the Ritz limited memory preconditioners on realistic applications in structural mechanics that require the solution of sequences of large‐scale symmetric saddle‐point systems. Numerical experiments show the relevance of the proposed preconditioner leading to a significant decrease in terms of computational operations when solving such sequences of linear systems. A saving of up to 43% in terms of computational effort is obtained on one of these applications. Copyright © 2016 John Wiley & Sons, Ltd.     

A comparison of abstract versions of deflation,balancing and additive coarse grid correction preconditioners

In this paper we consider various preconditioners for the conjugate gradient (CG) method to solve large linear systems of equations with symmetric positive definite system matrix. We continue the comparison between abstract versions of the deflation, balancing and additive coarse grid correction preconditioning techniques started in (SIAM J. Numer. Anal. 2004; 42 :1631–1647; SIAM J. Sci. Comput. 2006; 27 :1742–1759). There the deflation method is compared with the abstract additive coarse grid correction preconditioner and the abstract balancing preconditioner. Here, we close the triangle between these three methods. First of all, we show that a theoretical comparison of the condition numbers of the abstract additive coarse grid correction and the condition number of the system preconditioned by the abstract balancing preconditioner is not possible. We present a counter example, for which the condition number of the abstract additive coarse grid correction preconditioned system is below the condition number of the system preconditioned with the abstract balancing preconditioner. However, if the CG method is preconditioned by the abstract balancing preconditioner and is started with a special starting vector, the asymptotic convergence behavior of the CG method can be described by the so‐called effective condition number with respect to the starting vector. We prove that this effective condition number of the system preconditioned by the abstract balancing preconditioner is less than or equal to the condition number of the system preconditioned by the abstract additive coarse grid correction method. We also provide a short proof of the relationship between the effective condition number and the convergence of CG. Moreover, we compare the A‐norm of the errors of the iterates given by the different preconditioners and establish the orthogonal invariants of all three types of preconditioners. Copyright © 2008 John Wiley & Sons, Ltd.     

On parallel solution of linear elasticity problems. Part II: Methods and some computer experiments

This is the second part of a trilogy on parallel solution of the linear elasticity problem. We consider the plain case of the problem with isotropic material, including discontinuous coefficients, and with homogeneous Dirichlet boundary condition. The discretized problem is solved by the preconditioned conjugate gradient (pcg) method. In the first part of the trilogy block‐diagonal preconditioners based on the separate displacement component part of the elasticity equations were analysed. The preconditioning systems were solved by the pcg‐method, i.e. inner iterations were performed. As preconditioner, we used modified incomplete factorization MIC(0), where possibly the element matrices were modified in order to give M‐matrices, i.e. in order to guarantee the existence of the MIC(0) factorization. In the present paper, the second part, full block incomplete factorization preconditioners are presented and analysed. In order to avoid inner/outer iterations we also study a variant of the block‐diagonal method and of the full block method, where the matrices of the inner systems are just replaced by their MIC(0)‐factors. A comparison is made between the various methods with respect to rate of convergence and work per unknown. The fastest methods are implemented by message passing utilizing the MPI system. In the third part of the trilogy, we will focus on the use of higher‐order finite elements. Copyright © 2002 John Wiley & Sons, Ltd.     

Kaporin-Kon’shin’s method of parallel implementation of block preconditioners for asymmetric matrices in problems of filtration of a multicomponent mixture in a porous medium

The ILU class preconditioners (ILU(0), ILU(1), ILUT) employed for iterative algorithms for non-symmetrical linear sparse matrix systems are considered. Test matrices used in this study originate from discretization of systems of partial differential equations describing multicomponent fluid flows in porous media. A new parallel algorithm for block ILU factorization is suggested. This algorithm demonstrates a good convergence and significant speed-up in comparison with sequential algorithms. New integrated approach was tested on the wide range of matrices resulted from real hydrodynamic simulations of oil fields of Western Siberia and demonstrated significant reduction in computational time.