The importance of structure in incomplete factorization preconditioners

In this paper, we consider level-based preconditioning, which is one of the basic approaches to incomplete factorization preconditioning of iterative methods. It is well-known that while structure-based preconditioners can be very useful, excessive memory demands can limit their usefulness. Here we present an improved strategy that considers the individual entries of the system matrix and restricts small entries to contributing to fewer levels of fill than the largest entries. Using symmetric positive-definite problems arising from a wide range of practical applications, we show that the use of variable levels of fill can yield incomplete Cholesky factorization preconditioners that are more efficient than those resulting from the standard level-based approach. The concept of level-based preconditioning, which is based on the structural properties of the system matrix, is then transferred to the numerical incomplete decomposition. In particular, the structure of the incomplete factorization determined in the symbolic factorization phase is explicitly used in the numerical factorization phase. Further numerical results demonstrate that our level-based approach can lead to much sparser but efficient incomplete factorization preconditioners.     

Displacement decomposition—incomplete factorization preconditioning techniques for linear elasticity problems

Two preconditioning techniques for the numerical solution of linear elasticity problems are described and studied. Both techniques are based on spectral equivalence approach. The first technique consists in an incomplete factorization of the separate displacement component part of the stiffness matrix. The second technique uses an incomplete factorization of the isotropic approximation to the stiffness matrix. Results concerning existence, stability and efficiency of these preconditioning techniques are presented. The efficiency and robustness of the described techniques are illustrated by numerical experiments.     

Effectiveness and robustness revisited for a preconditioning technique based on structured incomplete factorization

In this work, we provide new analysis for a preconditioning technique called structured incomplete factorization (SIF) for symmetric positive definite matrices. In this technique, a scaling and compression strategy is applied to construct SIF preconditioners, where off‐diagonal blocks of the original matrix are first scaled and then approximated by low‐rank forms. Some spectral behaviors after applying the preconditioner are shown. The effectiveness is confirmed with the aid of a type of two‐dimensional and three‐dimensional discretized model problems. We further show that previous studies on the robustness are too conservative. In fact, the practical multilevel version of the preconditioner has a robustness enhancement effect, and is unconditionally robust (or breakdown free) for the model problems regardless of the compression accuracy for the scaled off‐diagonal blocks. The studies give new insights into the SIF preconditioning technique and confirm that it is an effective and reliable way for designing structured preconditioners. The studies also provide useful tools for analyzing other structured preconditioners. Various spectral analysis results can be used to characterize other structured algorithms and study more general problems.     

On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, we present block SSOR and modified block SSOR iteration methods based on the special structures of the coefficient matrices. In each step of the block SSOR iteration, we employ the block LU factorization to solve the sub-systems of linear equations. We show that the block LU factorization is existent and stable when the coefficient matrices are block diagonally dominant of type-II by columns. Under suitable conditions, we establish convergence theorems for both block SSOR and modified block SSOR iteration methods. In addition, the block SSOR iteration and AF-ADI method are considered as preconditioners for the nonsymmetric systems of linear equations. Numerical experiments show that both block SSOR and modified block SSOR iterations are feasible iterative solvers and they are also effective for preconditioning Krylov subspace methods such as GMRES and BiCGSTAB when used to solve this class of systems of linear equations.     

On the semi-conjugate direction methods with dynamic preconditioning

The semi-conjugate residual methods and semi-conjugate gradient methods with dynamic preconditioners in Krylov subspaces are considered for solving the systems of linear algebraic equations whose matrices are not symmetric. Their orthogonal and variational properties are under study. New algorithms are proposed for choosing the inner iteration parameters in the preconditioning matrices corresponding to incomplete factorization methods. The efficiency of the resulting iterative processes is demonstrated by a set of numerical experiments for finite difference diffusion-convection equations.     

A class of multilevel recursive incomplete LU preconditioning techniques

We introduce a class of multilevel recursive incomplete LU preconditioning techniques (RILUM) for solving general sparse matrices. This technique is based on a recursive two by two block incomplete LU factorization on the coefficient matrix. The coarse level system is constructed as an (approximate) Schur complement. A dynamic preconditioner is obtained by solving the Schur complement matrix approximately. The novelty of the proposed techniques is to solve the Schur complement matrix by a preconditioned Krylov subspace method. Such a reduction process is repeated to yield a multilevel recursive preconditioner.     

Diagonally compensated reduction and related preconditioning methods

When solving linear algebraic equations with large and sparse coefficient matrices, arising, for instance, from the discretization of partial differential equations, it is quite common to use preconditioning to accelerate the convergence of a basic iterative scheme. Incomplete factorizations and sparse approximate inverses can provide efficient preconditioning methods but their existence and convergence theory is based mostly on M-matrices (H-matrices). In some application areas, however, the arising coefficient matrices are not H-matrices. This is the case, for instance, when higher-order finite element approximations are used, which is typical for structural mechanics problems. We show that modification of a symmetric, positive definite matrix by reduction of positive offdiagonal entries and diagonal compensation of them leads to an M-matrix. This diagonally compensated reduction can take place in the whole matrix or only at the current pivot block in a recursive incomplete factorization method. Applications for constructing preconditioning matrices for finite element matrices are described.     

Combination of numerical and structured approaches to the construction of a second-order incomplete triangular factorization in parallel preconditioning methods

Parallel versions of the stabilized second-order incomplete triangular factorization conjugate gradient method in which the reordering of the coefficient matrix corresponding to the ordering based on splitting into subdomains with separators are considered. The incomplete triangular factorization is organized using the truncation of fill-in “by value” at internal nodes of subdomains, and “by value” and ‘by positions” on the separators. This approach is generalized for the case of constructing a parallel version of preconditioning the second-order incomplete LU factorization for nonsymmetric diagonally dominant matrices with. The reliability and convergence rate of the proposed parallel methods is analyzed. The proposed algorithms are implemented using MPI, results of solving benchmark problems with matrices from the collection of the University of Florida are presented.     

On some versions of incomplete block-matrix factorization iterative methods

Various forms of preconditioning matrices for iterative acceleration methods are discussed. The preconditioning is based on two versions of incomplete block-matrix factorization.     

On parallel solution of linear elasticity problems: Part I: theory

The discretized linear elasticity problem is solved by the preconditioned conjugate gradient (pcg) method. Mainly we consider the linear isotropic case but we also comment on the more general linear orthotropic problem. The preconditioner is based on the separate displacement component (sdc) part of the equations of elasticity. The preconditioning system consists of two or three subsystems (in two or three dimensions) also called inner systems, each of which is solved by the incomplete factorization pcg-method, i.e., we perform inner iterations. A finite element discretization and node numbering giving a high degree of partial parallelism with equal processor load for the solution of these systems by the MIC(0) pcg method is presented. In general, the incomplete factorization requires an M-matrix. This property is studied for the elasticity problem. The rate of convergence of the pcg-method is analysed for different preconditionings based on the sdc-part of the elasticity equations. In the following two parts of this trilogy we will focus more on parallelism and implementation aspects. © 1998 John Wiley & Sons, Ltd.     

An incomplete-factorization preconditioning using repeated red-black ordering

Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, repeated red-black ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.     

On truncated incomplete decompositions

In the present paper we introduce truncated incomplete decompositions (TrILU) for constant coefficient matrices. This new ILU variant saves most of the memory and work usually needed to compute and store the factorization. Further it improves the smoothing and preconditioning properties of standard ILU-decompositions. Besides describing the algorithm, we give theoretical results concerning stability and convergence as well as the smoothing property and robustness for TrILU smoothing in a multi-grid method. Further, we add numerical results of TrILU as smoother in a multi-grid method and as preconditioner in a pcg-method fully confirming the theoretical results.This work was supported by Deutsche Forschungsgemeinschaft.     

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.     

An implicit preconditioning strategy for large-scale generalized Sylvester equations

Large-scale generalized Sylvester equations appear in several important applications. Although the involved operator is linear, solving them requires specialized techniques. Different numerical methods have been designed to solve them, including direct factorization methods suitable for small size problems, and Krylov-type iterative methods for large-scale problems. For these iterative schemes, preconditioning is always a difficult task that deserves to be addressed. We present and analyze an implicit preconditioning strategy specially designed for solving generalized Sylvester equations that uses a preconditioned residual direction at every iteration. The advantage is that the preconditioned direction is built implicitly, avoiding the explicit knowledge of the given matrices. Only the effect of the matrix-vector product with the given matrices is required. We present encouraging numerical experiments for a set of different problems coming from several applications.     

Incomplete block factorization methods for complex-structure matrices

Two classes of SSOR-type incomplete block factorization methods are proposed for preconditioning of linear algebraic systems of equations with block banded matrices of complex structure. Correctness conditions are derived for these methods in application to M-matrices and their efficiency is demonstrated by numerical experiments with linear algebraic systems obtained by discretization of the three-dimensional Poisson equation using quadratic and cubic serendipity finite elements. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 159, pp. 5–22, 1987.     

Numerical comparison of preconditionings for large sparse finite element problems

A numerical study of the efficiency of the modified conjugate gradients (MCG) is performed using different preconditioning schemes. The MCG behavior is evaluated in connection with the solution of large linear sets of symmetric positive definite (p.d.) equations, arising from the finite element (f.e.) integration of partial differential equations of parabolic and elliptic type and the analysis of the leftmost eingenspectrum of the corresponding matrices. A simple incomplete Cholesky factorization ICCG(O) having the same sparsity pattern as the original problem is compared with a more complex technique ICAJ (Ψ) where the triangular factor is allowed to progressively fill in depending on a rejection parameter Ψ. The performance of the preconditioning algorithms is explored on finite element equations whose size N ranges between 150 and 2300. The results show that an optimal Ψ_opt may be found which minimizes the overall CPU time for the solution of both the linear system and the eigenproblem. The comparison indicates that ICAJ (Ψ_opt) is not significantly more efficient than ICCG(O), which therefore appears to be a simple, robust, and reliable method for the preconditioning of large sparse finite element models.     

Parallel Algorithms for Orthotropic Problems

Finite element meshes and node-numberings suitable for parallel solution with equally loaded processors are presented for linear orthotropic elliptic partial differential equations. These problems are of great importance, for instance in the oil and airfoil industries. The linear systems of equations are solved by the conjugate gradient method preconditioned by modified incomplete factorization, MIC. The basic method presented, is based on fronts of uncoupled nodes and unlike earlier methods it has the advantage of no requirement of a specific orientation of the mesh. This method is however, in general, restricted to small degree of anisotropy in the differential equation. Another method, which does not suffer from this limitation, uses rotation of the differential equation and spectral equivalence. The rotation is made in such a way that in the new co-ordinate system, the basic method is applicable. The spectral equivalence property is used for estimation of the condition number of the preconditioned system. Both methods are suitable for implementation on parallel computers. The computer architecture could be single instruction multiple data (SIMD) as well as multiple instruction multiple data (MIMD) with shared or distributed memory. Implementation of the basic method on a shared memory parallel computer shows a significant improvement by use of the MIC method compared with the diagonal scaling preconditioning method.     

On the preconditioning of matrices with skew-symmetric splittings

The rates of convergence of iterative methods with standard preconditioning techniques usually degrade when the skew-symmetric part S of the matrix is relatively large. In this paper, we address the issue of preconditioning matrices with such large skew-symmetric parts. The main idea of the preconditioner is to split the matrix into its symmetric and skew-symmetric parts and to invert the (shifted) skew-symmetric matrix. Successful use of the method requires the solution of a linear system with matrix I+S. An efficient method is developed using the normal equations, preconditioned by an incomplete orthogonal factorization.Numerical experiments on various systems arising in physics show that the reduction in terms of iteration count compensates for the additional work per iteration when compared to standard preconditioners.     

An Adaptive CGNR Algorithm for Solving Large Linear Systems

In this paper, an adaptive algorithm based on the normal equations for solving large nonsymmetric linear systems is presented. The new algorithm is a hybrid method combining polynomial preconditioning with the CGNR method. Residual polynomial is used in the preconditioning to estimate the eigenvalues of the s.p.d. matrix A ^T A, and the residual polynomial is generated from several steps of CGNR by recurrence. The algorithm is adaptive during its implementation. The robustness is maintained, and the iteration convergence is speeded up. A numerical test result is also reported.     

New breakdown-free variant of AINV method for nonsymmetric positive definite matrices

This paper proposes a new breakdown-free preconditioning technique, called SAINV-NS, of the AINV method of Benzi and Tuma for nonsymmetric positive definite matrices. The resulting preconditioner which is an incomplete factorization of the inverse of a nonsymmetric matrix will be used as an explicit right preconditioner for QMR, BiCGSTAB and GMRES(m) methods. The preconditoner is reliable (pivot breakdown can not occur) and effective at reducing the number of iterations. Some numerical experiments on test matrices are presented to show the efficiency of the new method and comparing to the AINV-A algorithm.