Numerical experiments with two approximate inverse preconditioners

We present the results of numerical experiments aimed at comparing two recently proposed sparse approximate inverse preconditioners from the point of view of robustness, cost, and effectiveness. Results for a standard ILU preconditioner are also included. The numerical experiments were carried out on a Cray C98 vector processor. This work was partially supported by the GA AS CR under grant 2030706 and by the grant GA CR 205/96/0921.     

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)     

Diagonally-striped matrices and approximate inverse preconditioners

The inverse of a banded matrix is, in general, dense. If the structure of the original banded matrix is “striped”, that is, the non-zero diagonals are separated by one or more zero diagonals, the inverse may exhibit a similar striped structure. The motivation for studying inverses of striped matrices is to obtain efficient preconditioners for systems arising from radiation transport equations, whose matrices include dominant values along diagonal stripes. Linear systems whose system matrix has a striped inverse lend themselves to the use of a sparse approximate inverse (SPAI) preconditioner whose structure is derived from that of the actual inverse.     

A Class of Incomplete Orthogonal Factorization Methods. II: Implementation and Results

We present, implement and test several incomplete QR factorization methods based on Givens rotations for sparse square and rectangular matrices. For square systems, the approximate QR factors are used as right-preconditioners for GMRES, and their performance is compared to standard ILU techniques. For rectangular matrices corresponding to linear least-squares problems, the approximate R factor is used as a right-preconditioner for CGLS. A comprehensive discussion is given about the uses, advantages and shortcomings of the preconditioners. AMS subject classification (2000) 65F10, 65F25, 65F50.Received May 2002. Revised October 2004. Communicated by Åke Björck.     

Inexact constraint preconditioners for linear systems arising in interior point methods

Issues of indefinite preconditioning of reduced Newton systems arising in optimization with interior point methods are addressed in this paper. Constraint preconditioners have shown much promise in this context. However, there are situations in which an unfavorable sparsity pattern of Jacobian matrix may adversely affect the preconditioner and make its inverse representation unacceptably dense hence too expensive to be used in practice. A remedy to such situations is proposed in this paper. An approximate constraint preconditioner is considered in which sparse approximation of the Jacobian is used instead of the complete matrix. Spectral analysis of the preconditioned matrix is performed and bounds on its non-unit eigenvalues are provided. Preliminary computational results are encouraging.     

Preconditioners Based on Fit Techniques for the Iterative Regularization in the Image Deconvolution Problem

For large-scale image deconvolution problems, the iterative regularization methods can be favorable alternatives to the direct methods. We analyze preconditioners for regularizing gradient-type iterations applied to problems with 2D band Toeplitz coefficient matrix. For problems having separable and positive definite matrices, the fit preconditioner we have introduced in a previous paper has been shown to be effective in conjunction with CG. The cost of this preconditioner is of O(n²) operations per iteration, where n² is the pixels number of the image, whereas the cost of the circulant preconditioners commonly used for this type of problems is of O(n² log n) operations per iteration. In this paper the extension of the fit preconditioner to more general cases is proposed: namely the nonseparable positive definite case and the symmetric indefinite case. The major difficulty encountered in this extension concerns the factorization phase, where a further approximation is required. Three approximate factorizations are proposed. The preconditioners thus obtained have still a cost of O(n²) operations per iteration. A numerical experimentation shows that the fit preconditioners are competitive with the regularizing Chan preconditioner, both in the regularizing efficiency and the computational cost. AMS subject classification (2000) 65F10, 65F22.Received October 2003. Accepted December 2004. Communicated by Lars Eldén.     

稀疏近似逆与多层块ILU预条件技术

设计了一种求解一般稀疏线性方程组的健壮且有效的可并行化预条件子,这种预条件子涉及在多层块ILU预条件子(BILUM)中使用稀疏近似逆(AINV)技术．所得的预条件子保持了BILUM的健壮性,它比标准的BILUM预条件子有两点优势:控制稀疏性的能力和增强了并行性．数值例子显示了新预条件子的有效性和效率．     

A Comparative Study on Dynamic and Static Sparsity Patterns in Parallel Sparse Approximate Inverse Preconditioning

Sparse approximate inverse (SAI) techniques have recently emerged as a new class of parallel preconditioning techniques for solving large sparse linear systems on high performance computers. The choice of the sparsity pattern of the SAI matrix is probably the most important step in constructing an SAI preconditioner. Both dynamic and static sparsity pattern selection approaches have been proposed by researchers. Through a few numerical experiments, we conduct a comparable study on the properties and performance of the SAI preconditioners using the different sparsity patterns for solving some sparse linear systems. This revised version was published online in July 2006 with corrections to the Cover Date.     

Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics

We investigate the use of sparse approximate inverse preconditioners for the iterative solution of linear systems with dense complex coefficient matrices arising in industrial electromagnetic problems. An approximate inverse is computed via a Frobenius norm approach with a prescribed nonzero pattern. Some strategies for determining the nonzero pattern of an approximate inverse are described. The results of numerical experiments suggest that sparse approximate inverse preconditioning is a viable approach for the solution of large-scale dense linear systems on parallel computers. This revised version was published online in August 2006 with corrections to the Cover Date.     

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.     

Parallel preconditioners for large scale partial difference equation systems

We propose a new preconditioner DASP (discrete approximate spectral preconditioner), based on the existing well-known preconditioners and our computational experience. Parallel preconditioning strategies for large scale partial difference equation systems arising from partial differential equations are investigated. Numerical results are given to show the efficiency and effectiveness of the new preconditioners for both model problems and real applications in petroleum reservoir simulation.     

Parallel preconditioned conjugate gradient algorithm on GPU

We propose a parallel implementation of the Preconditioned Conjugate Gradient algorithm on a GPU platform. The preconditioning matrix is an approximate inverse derived from the SSOR preconditioner. Used through sparse matrix–vector multiplication, the proposed preconditioner is well suited for the massively parallel GPU architecture. As compared to CPU implementation of the conjugate gradient algorithm, our GPU preconditioned conjugate gradient implementation is up to 10 times faster (8 times faster at worst).     

Factorized sparse approximate inverse preconditionings. III. Iterative construction of preconditioners

This paper presents new results of the theoretical study of factorized sparse approximate inverse (FSAI) preconditionings. In particular, the effect of the a posteriori Jacobi scaling and the possibility of constructing FSAI preconditioners iteratively are analyzed. A simple stopping criterion for the termination of local iterations in constructing approximate FSAI preconditioners using the PCG method is proposed. The results of numerical experiments with 3D finite-element problems from linear elasticity are presented. Bibliography21 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 248, 1998, pp. 17–48. Translated by L. Yu. Kolotilina.     

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.     

A convergence analysis for a sweeping preconditioner for block tridiagonal systems of linear equations

We study sweeping preconditioners for symmetric and positive definite block tridiagonal systems of linear equations. The algorithm provides an approximate inverse that can be used directly or in a preconditioned iterative scheme. These algorithms are based on replacing the Schur complements appearing in a block Gaussian elimination direct solve by hierarchical matrix approximations with reduced off‐diagonal ranks. This involves developing low rank hierarchical approximations to inverses. We first provide a convergence analysis for the algorithm for reduced rank hierarchical inverse approximation. These results are then used to prove convergence and preconditioning estimates for the resulting sweeping preconditioner. Copyright © 2014 John Wiley & Sons, Ltd.     

Preconditioner based on the Sherman-Morrison formula for regularized least squares problems

We propose a sparse approximate inverse preconditioner based on the Sherman-Morrison formula for Tikhonov regularized least square problems. Theoretical analysis shows that, the factorization method can take the advantage of the symmetric property of the coefficient matrix and be implemented cheaply. Combined with dropping rules, the incomplete factorization leads to a preconditioner for Krylov iterative methods to solve regularized least squares problems. Numerical experiments show that our preconditioner is competitive compared to existing methods, especially for ill-conditioned and rank deficient least squares problems.     

Convergence of inexact inverse iteration with application to preconditioned iterative solves

In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results. AMS subject classification (2000)  65F15, 65F10     

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.     

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.     

A robust AINV‐type method for constructing sparse approximate inverse preconditioners in factored form

This paper suggests a new method, called AINV‐A, for constructing sparse approximate inverse preconditioners for positive‐definite matrices, which can be regarded as a modification of the AINV method proposed by Benzi and Túma. Numerical results on SPD test matrices coming from different applications demonstrate the robustness of the AINV‐A method and its superiority to the original AINV approach. Copyright © 2001 John Wiley & Sons, Ltd.