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.     

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.     

Block factorized preconditioners for high‐order accurate in time approximation of the Navier‐Stokes equations

Computationally efficient solution methods for the unsteady Navier‐Stokes incompressible equations are mandatory in real applications of fluid dynamics. A typical strategy to reduce the computational cost is to split the original problem into subproblems involving the separate computation of velocity and pressure. The splitting can be carried out either at a differential level, like in the Chorin‐Temam scheme, or in an algebraic fashion, like in the algebraic reinterpretation of the Chorin‐Temam method, or in the Yosida scheme (see 1 and 19 ). These fractional step schemes indeed provide effective methods of solution when dealing with first order accurate time discretizations. Their extension to high order time discretization schemes is not trivial. To this end, in the present work we focus our attention on the adoption of inexact algebraic factorizations as preconditioners of the original problem. We investigate their properties and show that some particular choices of the approximate factorization lead to very effective schemes. In particular, we prove that performing a small number of preconditioned iterations is enough to obtain a time accurate solution, irrespective of the dimension of the system at hand. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 487–510, 2003     

Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation

The paper introduces the sweeping preconditioner, which is highly efficient for iterative solutions of the variable‐coefficient Helmholtz equation including very‐high‐frequency problems. The first central idea of this novel approach is to construct an approximate factorization of the discretized Helmholtz equation by sweeping the domain layer by layer, starting from an absorbing layer or boundary condition. Given this specific order of factorization, the second central idea is to represent the intermediate matrices in the hierarchical matrix framework. In two dimensions, both the construction and the application of the preconditioners are of linear complexity. The generalized minimal residual method (GMRES) solver with the resulting preconditioner converges in an amazingly small number of iterations, which is essentially independent of the number of unknowns. This approach is also extended to the three‐dimensional case with some success. Numerical results are provided in both two and three dimensions to demonstrate the efficiency of this new approach. © 2011 Wiley Periodicals, Inc.     

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 new approach for finding a basis for the splitting preconditioner for linear systems from interior point methods

The class of splitting preconditioners for the iterative solution of linear systems arising from Mehrotra’s predictor-corrector method for large scale linear programming problems needs to find a basis through a sophisticated process based on the application of a rectangular LU factorization. This class of splitting preconditioners works better near a solution of the linear programming problem when the matrices are highly ill-conditioned. In this study, we develop and implement a new approach to find a basis for the splitting preconditioner, based on standard rectangular LU factorization with partial permutation of the scaled transpose linear programming constraint matrix. In most cases, this basis is better conditioned than the existing one. In addition, we include a penalty parameter in Mehrotra’s predictor-corrector method in order to reduce ill-conditioning of the normal equations matrix. Computational experiments show a reduction in the average number of iterations of the preconditioned conjugate gradient method. Also, the increased efficiency and robustness of the new approach become evident by the performance profile.     

Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems

This paper is concerned with the numerical solution of a symmetric indefinite system which is a generalization of the Karush–Kuhn–Tucker system. Following the recent approach of Luk?an and Vl?ek, we propose to solve this system by a preconditioned conjugate gradient (PCG) algorithm and we devise two indefinite preconditioners with good theoretical properties. In particular, for one of these preconditioners, the finite termination property of the PCG method is stated. The PCG method combined with a parallel version of these preconditioners is used as inner solver within an inexact Interior‐Point (IP) method for the solution of large and sparse quadratic programs. The numerical results obtained by a parallel code implementing the IP method on distributed memory multiprocessor systems enable us to confirm the effectiveness of the proposed approach for problems with special structure in the constraint matrix and in the objective function. Copyright © 2002 John Wiley & Sons, Ltd.     

A family of constrained pressure residual preconditioners for parallel reservoir simulations

Large‐scale reservoir simulations are extremely time‐consuming because of the solution of large‐scale linear systems arising from the Newton or Newton–Raphson iterations. The problem becomes even worse when highly heterogeneous geological models are employed. This paper introduces a family of multi‐stage preconditioners for parallel black oil simulations, which are based on the famous constrained pressure residual preconditioner. Numerical experiments demonstrate that our preconditioners are robust, efficient, and scalable. Copyright © 2015 John Wiley & Sons, Ltd.     

A total least squares method for Toeplitz systems of equations

A Newton method to solve total least squares problems for Toeplitz systems of equations is considered. When coupled with a bisection scheme, which is based on an efficient algorithm for factoring Toeplitz matrices, global convergence can be guaranteed. Circulant and approximate factorization preconditioners are proposed to speed convergence when a conjugate gradient method is used to solve linear systems arising during the Newton iterations. The work of the second author was partially supported by a National Science Foundation Postdoctoral Research Fellowship.     

Multilevel approaches for FSAI preconditioning

Factorized sparse approximate inverse (FSAI) preconditioners are robust algorithms for symmetric positive matrices, which are particularly attractive in a parallel computational environment because of their inherent and almost perfect scalability. Their parallel degree is even redundant with respect to the actual capabilities of the current computational architectures. In this work, we present two new approaches for FSAI preconditioners with the aim of improving the algorithm effectiveness by adding some sequentiality to the native formulation. The first one, denoted as block tridiagonal FSAI, is based on a block tridiagonal factorization strategy, whereas the second one, domain decomposition FSAI, is built by reordering the matrix graph according to a multilevel k‐way partitioning method followed by a bandwidth minimization algorithm. We test these preconditioners by solving a set of symmetric positive definite problems arising from different engineering applications. The results are evaluated in terms of performance, scalability, and robustness, showing that both strategies lead to faster convergent schemes regarding the number of iterations and total computational time in comparison with the native FSAI with no significant loss in the algorithmic parallel degree.     

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     

A special complementarity function revisited

ABSTRACT

Recently, a local framework of Newton-type methods for constrained systems of equations has been developed. Applied to the solution of Karush–Kuhn–Tucker (KKT) systems, the framework enables local quadratic convergence under conditions that allow nonisolated and degenerate KKT points. This result is based on a reformulation of the KKT conditions as a constrained piecewise smooth system of equations. It is an open question whether a comparable result can be achieved for other (not piecewise smooth) reformulations. It will be shown that this is possible if the KKT system is reformulated by means of the Fischer–Burmeister complementarity function under conditions that allow degenerate KKT points and nonisolated Lagrange multipliers. To this end, novel constrained Levenberg–Marquardt subproblems are introduced. They allow significantly longer steps for updating the multipliers. Based on this, a convergence rate of at least 1.5 is shown.     

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.     

Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems

An inexact Newton algorithm for large sparse equality constrained non-linear programming problems is proposed. This algorithm is based on an indefinitely preconditioned smoothed conjugate gradient method applied to the linear KKT system and uses a simple augmented Lagrangian merit function for Armijo type stepsize selection. Most attention is devoted to the termination of the CG method, guaranteeing sufficient descent in every iteration and decreasing the number of required CG iterations, and especially, to the choice of a suitable preconditioner. We investigate four preconditioners, which have 2 × 2 block structure, and prove theoretically their good properties. The efficiency of the inexact Newton algorithm, together with a comparison of various preconditioners and strategies, is demonstrated by using a large collection of test problems. © 1998 John Wiley & Sons, Ltd.     

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.     

Block preconditioners for linear systems arising from multiscale collocation with compactly supported RBFs

Symmetric collocation methods with RBFs allow approximation of the solution of a partial differential equation, even if the right‐hand side is only known at scattered data points, without needing to generate a grid. However, the benefit of a guaranteed symmetric positive definite block system comes at a high computational cost. This cost can be alleviated somewhat by considering compactly supported RBFs and a multiscale technique. But the condition number and sparsity will still deteriorate with the number of data points. Therefore, we study certain block diagonal and triangular preconditioners. We investigate ideal preconditioners and determine the spectra of the preconditioned matrices before proposing more practical preconditioners based on a restricted additive Schwarz method with coarse grid correction. Numerical results verify the effectiveness of the preconditioners. Copyright © 2015 John Wiley & Sons, Ltd.     

Diagonal threshold techniques in robust multi‐level ILU preconditioners for general sparse linear systems

This paper introduces techniques based on diagonal threshold tolerance when developing multi‐elimination and multi‐level incomplete LU (ILUM) factorization preconditioners for solving general sparse linear systems. Existing heuristics solely based on the adjacency graph of the matrices have been used to find independent sets and are not robust for matrices arising from certain applications in which the matrices may have small or zero diagonals. New heuristic strategies based on the adjacency graph and the diagonal values of the matrices for finding independent sets are introduced. Analytical bounds for the factorization and preconditioned errors are obtained for the case of a two‐level analysis. These bounds provide useful information in designing robust ILUM preconditioners. Extensive numerical experiments are conducted in order to compare robustness and efficiency of various heuristic strategies. Copyright © 1999 John Wiley & Sons, Ltd.     

Prim-based support-graph preconditioners for min-cost flow problems

Support-graph preconditioners have been shown to be a valuable tool for the iterative solution, via a Preconditioned Conjugate Gradient method, of the KKT systems that must be solved at each iteration of an Interior Point algorithm for the solution of Min Cost Flow problems. These preconditioners extract a proper triangulated subgraph, with “large” weight, of the original graph: in practice, trees and Brother-Connected Trees (BCTs) of depth two have been shown to be the most computationally efficient families of subgraphs. In the literature, approximate versions of the Kruskal algorithm for maximum-weight spanning trees have most often been used for choosing the subgraphs; Prim-based approaches have been used for trees, but no comparison have ever been reported. We propose Prim-based heuristics for BCTs, which require nontrivial modifications w.r.t. the previously proposed Kruskal-based approaches, and present a computational comparison of the different approaches, which shows that Prim-based heuristics are most often preferable to Kruskal-based ones. This paper has been partially supported by the UE Marie Curie Research Training Network no. 504438 ADONET.     

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.