Modified Block SSOR Preconditioners for Symmetric Positive Definite Linear Systems

A class of modified block SSOR preconditioners is presented for the symmetric positive definite systems of linear equations, whose coefficient matrices come from the hierarchical-basis finite-element discretizations of the second-order self-adjoint elliptic boundary value problems. These preconditioners include a block SSOR iteration preconditioner, and two inexact block SSOR iteration preconditioners whose diagonal matrices except for the (1,1)-block are approximated by either point symmetric Gauss–Seidel iterations or incomplete Cholesky factorizations, respectively. The optimal relaxation factors involved in these preconditioners and the corresponding optimal condition numbers are estimated in details through two different approaches used by Bank, Dupont and Yserentant (Numer. Math. 52 (1988) 427–458) and Axelsson (Iterative Solution Methods (Cambridge University Press, 1994)). Theoretical analyses show that these modified block SSOR preconditioners are very robust, have nearly optimal convergence rates, and especially, are well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

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 NEW ILU PRECONDITIONER FOR BORDERED LINEAR SYSTEMS

Bordered linear systems arise from many industrial applications, such as reservoir simulation and structural engineering. Traditional ILU preconditioners which throw away the additional equations are often too crude for these systems. We describe a practical implementation of ILU preconditioners which are more accurate and more robust. The emphasis of this paper is on implementation rather than on theory.     

Preconditioning systems arising from the KKR Green function method using block-circulant matrices

Recently, a linearly scaling method for the calculation of the electronic structure based on the Korringa–Kohn–Rostoker Green function method has been proposed. The method uses the transpose free quasi minimal residual method (TFQMR) to solve linear systems with multiple right hand sides. These linear systems depend on the energy-level under consideration and the convergence rate deteriorates for some of these energy points. While traditional preconditioners like ILU are fairly useful for the problem, the computation of the preconditioner itself is often relatively hard to parallelize. To overcome these difficulties, we develop a new preconditioner that exploits the strong structure of the underlying systems. The resulting preconditioner is block-circulant and thus easy to compute, invert and parallelize. The resulting method yields a dramatic speedup of the computation compared to the unpreconditioned solver, especially for critical energy levels.     

On computing of block ILU preconditioner for block tridiagonal systems

We present the recurrence formulas for computing the approximate inverse factors of tridiagonal and pentadiagonal matrices using bordering technique. Resulting algorithms are used to approximate the inverse of pivot blocks needed for constructing block ILU preconditioners for solving the block tridiagonal linear systems, arising from discretization of partial differential equations. Resulting preconditioners are suitable for parallel implementation. Comparison with other methods are also included.     

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.     

Convergence of parallel multisplitting methods using ILU factorizations

In this paper, we study the convergence of both relaxed multisplitting method and nonstationary two-stage multisplitting method associated with a multisplitting which is obtained from the ILU factorizations for solving a linear system whose coefficient matrix is anH-matrix. Also, parallel performance results of nonstaionary two-stage multisplitting method using ILU factorizations as inner splittings on the IBM p690 supercomputer are provided to analyze theoretical results.     

Approximate factorizations with modified S/P consistently ordered M-factors

Preconditioned iterative methods are widely used to solve linear systems such as those arising from the finite element formulation of boundary value problems and approximate factorizations are widely used as preconditioners. The ordering of the unknowns is therefore an important issue because it has a strong influence on the convergence behaviour of the iteration method while it is also a decisive aspect for their parallel implementation. Consistent orderings are attractive for parallel implementations and it has been shown that some subclasses of these orderings also enhance the convergence behaviour of the associated iteration methods. This has in particular been shown for the so-called S/P consistent orderings. A wider definition of this class of orderings has recently been proposed and we investigate here how approximate factorizations should be implemented when using such more general orderings (still called S/P consistent) in order to keep their expected high convergence properties. A simple practical conclusion is suggested, supported by both theoretical and numerical arguments.     

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.     

Block ILU-preconditioners for problems of filtration of a multicomponent mixture in a porous medium

ILU class preconditioners (ILU(0), ILU(1), ILUT) employed for iterative algorithms for asymmetric linear systems with sparse matrices are considered. Test matrices used in this study originate from discretization of systems of partial differential equations describing a multicomponent fluid flow in porous media. New algorithms for block storage of matrices and block based ILU-factorization are described. This new integrated approach was tested on a wide range of matrices resulted from actual hydrodynamic simulations of oil fields in Western Siberia and had demonstrated significant reduction of computational time.     

ILU++: A new software package for solving sparse linear systems with iterative methods

ILU++ is a software package for solving sparse linear systems with iterative methods using state-of-the-art incomplete multilevel LU-factorisations as preconditioners. It implements several types of preprocessing (permuting and scaling both rows and columns prior to factorisation to make the matrix more suitable for LU-factorisation), different pivoting strategies and a number of dropping rules to ensure sparsity. ILU++ is available under the GNU public licence. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Block ILU Preconditioners for a Nonsymmetric Block-Tridiagonal M-Matrix

We propose block ILU (incomplete LU) factorization preconditioners for a nonsymmetric block-tridiagonal M-matrix whose computation can be done in parallel based on matrix blocks. Some theoretical properties for these block ILU factorization preconditioners are studied and then we describe how to construct them effectively for a special type of matrix. We also discuss a parallelization of the preconditioner solver step used in nonstationary iterative methods with the block ILU preconditioners. Numerical results of the right preconditioned BiCGSTAB method using the block ILU preconditioners are compared with those of the right preconditioned BiCGSTAB using a standard ILU factorization preconditioner to see how effective the block ILU preconditioners are.     

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     

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.     

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.     

Preconditioning Indefinite Systems in Interior Point Methods for Optimization

Every Newton step in an interior-point method for optimization requires a solution of a symmetric indefinite system of linear equations. Most of today's codes apply direct solution methods to perform this task. The use of logarithmic barriers in interior point methods causes unavoidable ill-conditioning of linear systems and, hence, iterative methods fail to provide sufficient accuracy unless appropriately preconditioned. Two types of preconditioners which use some form of incomplete Cholesky factorization for indefinite systems are proposed in this paper. Although they involve significantly sparser factorizations than those used in direct approaches they still capture most of the numerical properties of the preconditioned system. The spectral analysis of the preconditioned matrix is performed: for convex optimization problems all the eigenvalues of this matrix are strictly positive. Numerical results are given for a set of public domain large linearly constrained convex quadratic programming problems with sizes reaching tens of thousands of variables. The analysis of these results reveals that the solution times for such problems on a modern PC are measured in minutes when direct methods are used and drop to seconds when iterative methods with appropriate preconditioners are used.     

Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems

Two classes of incomplete factorization preconditioners are considered for nonsymmetric linear systems arising from second order finite difference discretizations of non-self-adjoint elliptic partial differential equations. Analytic and experimental results show that relaxed incomplete factorization methods exhibit numerical instabilities of the type observed with other incomplete factorizations, and the effects of instability are characterized in terms of the relaxation parameter. Several stabilized incomplete factorizations are introduced that are designed to avoid numerically unstable computations. In experiments with two-dimensional problems with variable coefficients and on nonuniform meshes, the stabilized methods are shown to be much more robust than standard incomplete factorizations.The work presented in this paper was supported by the National Science Foundation under grants DMS-8607478, CCR-8818340, and ASC-8958544, and by the U.S. Army Research Office under grant DAAL-0389-K-0016.     

A New Class AOR Preconditioner for $L$-Matrices

Hadjidimos(1978) proposed a classical accelerated overrelaxation(AOR) iterative method to solve the system of linear equations, and discussed its convergence under the conditions that the coefficient matrices are irreducible diagonal dominant, L-matrices, and consistently orders matrices. Several preconditioned AOR methods have been proposed to solve system of linear equations Ax = b, where A ∈ R~(n×n) is an L-matrix. In this work, we introduce a new class preconditioners for solving linear systems and give a comparison result and some convergence result for this class of preconditioners. Numerical results for corresponding preconditioned GMRES methods are given to illustrate the theoretical results.     

SPAI Preconditioners for HPC Applications

Iterative methods to solve systems of linear equations Ax = b usually require preconditioners M to speed convergence. But the calculation of many preconditioners can be notoriously sequential. The sparse approximate inverse preconditioner (SPAI) has particular potential for high performance computing [1]. We have ported the SPAI algorithm to graphical processing units (GPUs) within NVIDIA's CUSP library [2] for sparse linear algebra. GPUs perform well on dense linear algebra problems where data resides for long periods on the device. Since the underlying minimization problems are independent, they are mapped to separate thread-blocks, and an optimized QR algorithm implemented using NVIDIA's CUBLAS library is employed on each. Traditionally the challenge has been to determine a sparsity pattern Sp( M ) of the preconditioner dynamically [3], which reduces the condition number of MA to a degree where a preconditioned iterative solver such as GMRES becomes computationally viable. Due to the extremely high performance of the GPU, it is possible to consider initial sparsity patterns much denser than have been previously considered. We therefore consider a fixed sparsity patterns to simplify the GPU implementation. We evaluate the performance of the resulting preconditioner on a standard set of sparse matrices, and compare SPAI to other preconditioners. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Circulant-block preconditioners for solving ordinary differential equations

Boundary value methods for solving 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 circulant-block preconditioner is proposed to speed up the convergence rate of the GMRES method. Theoretical and practical arguments are given to show that this preconditioner is more efficient than some other circulant-type preconditioners in some cases. A class of waveform relaxation methods is also proposed to solve the linear systems.