ITERATIVE METHODS WITH PRECONDITIONERS FORINDEFINITE SYSTEMS

1.IntroductionSymmetricindefinitesystemsoflinearequationsariseinmailyareasofscientificcomputation.Inthispaper,wewiUdiscussthesolutionofsparseindefinitesystemoftheformwhereA6Rnxnisasymmetricpositivedefinitematrix,BERmxnhasfullrowrankmSn3CERmxmissymmetricpositivesemidefinte,fER"andgERm.Illthiscase,thelineaxequationshastheuniquesolution[8--ic].FOrsimplicity,wedenotetheequationsasKx~b.DiscretizationsoftheStokesequationsorotherPDEsproducethelinearequationsas(l).Inoptimization,whenbarrieror…     

An Incomplete Cholesky Factorization for Dense Symmetric Positive Definite Matrices

In this paper, we study the use of an incomplete Cholesky factorization (ICF) as a preconditioner for solving dense symmetric positive definite linear systems. This method is suitable for situations where matrices cannot be explicitly stored but each column can be easily computed. Analysis and implementation of this preconditioner are discussed. We test the proposed ICF on randomly generated systems and large matrices from two practical applications: semidefinite programming and support vector machines. Numerical comparison with the diagonal preconditioner is also presented.     

对称不定系统的一类预处理子的注记

由于对称正定系统已有很多有效的求解方法,因此将对称的、或者非对称的不定系统转化为对称正定系统就成为解决这类问题的方法之一构造了一类简洁有效的预处理子,将对称不定系统转化为对称正定型,研究了所得预处理系统的谱性质,估计了其谱条件数,推广了现有结论.     

Incomplete block factorization preconditioning for indefinite elliptic problems

Summary. The application of the finite difference method to approximate the solution of an indefinite elliptic problem produces a linear system whose coefficient matrix is block tridiagonal and symmetric indefinite. Such a linear system can be solved efficiently by a conjugate residual method, particularly when combined with a good preconditioner. We show that specific incomplete block factorization exists for the indefinite matrix if the mesh size is reasonably small, and that this factorization can serve as an efficient preconditioner. Some efforts are made to estimate the eigenvalues of the preconditioned matrix. Numerical results are also given. Received November 21, 1995 / Revised version received February 2, 1998 / Published online July 28, 1999     

Schur complement‐based domain decomposition preconditioners with low‐rank corrections

This paper introduces a robust preconditioner for general sparse matrices based on low‐rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low‐rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low‐rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach. Copyright © 2016 John Wiley & Sons, Ltd.     

Bilus: A block version of ilus factorization

ILUS factorization has many desirable properties such as its amenability to the skyline format, the ease with which stability may be monitored, and the possibility of constructing a preconditioner with symmetric structure. In this paper we introduce a new preconditioning technique for general sparse linear systems based on the ILUS factorization strategy. The resulting preconditioner has the same properties as the ILUS preconditioner. Some theoretical properties of the new preconditioner are discussed and numerical experiments on test matrices from the Harwell-Boeing collection are tested. Our results indicate that the new preconditioner is cheaper to construct than the ILUS preconditioner.     

Stability of the Matrix Factorization for Solving Block Tridiagonal Symmetric Indefinite Linear Systems

In this paper, we propose a new factorization method for block tridiagonal symmetric indefinite matrices. We also discuss the stability of the factorization method. As a measurement of stability, an effective condition number is derived by using backward error analysis and perturbation analysis. It shows that under some suitable assumptions, the solution obtained by this factorization method is acceptable. Numerical results demonstrate that the factorization is stable if its condition number is not too large. This revised version was published online in July 2006 with corrections to the Cover Date.     

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 comparative study of null‐space factorizations for sparse symmetric saddle point systems

Null‐space methods for solving saddle point systems of equations have long been used to transform an indefinite system into a symmetric positive definite one of smaller dimension. A number of independent works in the literature have identified that we can interpret a null‐space method as a matrix factorization. We review these findings, highlight links between them, and bring them into a unified framework. We also investigate the suitability of using null‐space factorizations to derive sparse direct methods and present numerical results for both practical and academic problems.     

Preordering saddle‐point systems for sparse LDLT factorization without pivoting

This paper focuses on efficiently solving large sparse symmetric indefinite systems of linear equations in saddle‐point form using a fill‐reducing ordering technique with a direct solver. Row and column permutations partition the saddle‐point matrix into a block structure constituting a priori pivots of order 1 and 2. The partitioned matrix is compressed by treating each nonzero block as a single entry, and a fill‐reducing ordering is applied to the corresponding compressed graph. It is shown that, provided the saddle‐point matrix satisfies certain criteria, a block LDL^T factorization can be computed using the resulting pivot sequence without modification. Numerical results for a range of problems from practical applications using a modern sparse direct solver are presented to illustrate the effectiveness of the approach.     

ILUCP: a Crout ILU preconditioner with pivoting

We introduce a new preconditioner, ILUCP, to be used with an iterative method for solving sparse linear systems. It is based on an incomplete LU factorization combining Crout's formulation of Gaussian elimination with pivoting by columns. It is usually faster than ILUTP, which is based on a delayed update version of Gaussian elimination with pivoting, but requires more memory. For applications where memory is not a primary concern, ILUCP can be an attractive alternative to ILUTP. Copyright © 2005 John Wiley & Sons, Ltd.     

Solving symmetric indefinite systems in an interior-point method for linear programming

We describe an implementation of a primal—dual path following method for linear programming that solves symmetric indefinite augmented systems directly by Bunch—Parlett factorization, rather than reducing these systems to the positive definite normal equations that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.This work has been supported in part by National Science Foundation grants DDM-8908818 (Fourer) and CCR-8810107 (Mehrotra), and by a grant from GTE Laboratories (Mehrotra).     

Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming

This study analyzes the influence of sparse matrix reordering on the solution of linear systems arising from interior point methods for linear programming. In particular, such linear systems are solved by the conjugate gradient method with a two-phase hybrid preconditioner that uses the controlled Cholesky factorization during the initial iterations and later adopts the splitting preconditioner. This approach yields satisfactory computational results for the solution of linear systems with symmetric positive-definite matrices. Three reordering heuristics are analyzed in this study: the reverse Cuthill–McKee heuristic, the Sloan algorithm, and the minimum degree heuristic. Through numerical experiments, it was observed that these heuristics can be advantageous in terms of accelerating the convergence of the conjugate gradient method and reducing the processing time.     

Convergences of splitting iterative methods for symmetric indefinite linear systems

In this paper, we generalize the saddle point problem to general symmetric indefinite systems, we also present a kind of convergent splitting iterative methods for the symmetric indefinite systems. A special divergent splitting is introduced. The sufficient condition is discussed that the eigenvalues of the iteration matrix are real. The spectral radius of the iteration matrix is discussed in detail, the convergence theories of the splitting iterative methods for the symmetric indefinite systems are obtained. Finally, we present a preconditioner and discuss the eigenvalues of preconditioned matrix.     

An algebraic multifrontal preconditioner that exploits the low‐rank property

We present an algebraic structured preconditioner for the iterative solution of large sparse linear systems. The preconditioner is based on a multifrontal variant of sparse LU factorization used with nested dissection ordering. Multifrontal factorization amounts to a partial factorization of a sequence of logically dense frontal matrices, and the preconditioner is obtained if structured factorization is used instead. This latter exploits the presence of low numerical rank in some off‐diagonal blocks of the frontal matrices. An algebraic procedure is presented that allows to identify the hierarchy of the off‐diagonal blocks with low numerical rank based on the sparsity of the system matrix. This procedure is motivated by a model problem analysis, yet numerical experiments show that it is successful beyond the model problem scope. Further aspects relevant for the algebraic structured preconditioner are discussed and illustrated with numerical experiments. The preconditioner is also compared with other solvers, including the corresponding direct solver. Copyright © 2015 John Wiley & Sons, Ltd.     

Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods

We devise a hybrid approach for solving linear systems arising from interior point methods applied to linear programming problems. These systems are solved by preconditioned conjugate gradient method that works in two phases. During phase I it uses a kind of incomplete Cholesky preconditioner such that fill-in can be controlled in terms of available memory. As the optimal solution of the problem is approached, the linear systems becomes highly ill-conditioned and the method changes to phase II. In this phase a preconditioner based on the LU factorization is found to work better near a solution of the LP problem. The numerical experiments reveal that the iterative hybrid approach works better than Cholesky factorization on some classes of large-scale problems.     

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.     

A parallel balance scheme for banded linear systems

A parallel algorithm is proposed for the solution of narrow banded non‐symmetric linear systems. The linear system is partitioned into blocks of rows with a small number of unknowns common to multiple blocks. Our technique yields a reduced system defined only on these common unknowns which can then be solved by a direct or iterative method. A projection based extension to this approach is also proposed for computing the reduced system implicitly, which gives rise to an inner–outer iteration method. In addition, the product of a vector with the reduced system matrix can be computed efficiently on a multiprocessor by concurrent projections onto subspaces of block rows. Scalable implementations of the algorithm can be devized for hierarchical parallel architectures by exploiting the two‐level parallelism inherent in the method. Our experiments indicate that the proposed algorithm is a robust and competitive alternative to existing methods, particularly for difficult problems with strong indefinite symmetric part. Copyright © 2001 John Wiley & Sons, Ltd.     

大型对称不定箭形线性方程组的分解方法

1 引言 首先考虑2×2矩阵 显然当k>1/2时,矩阵K是对称正定的,且K可以分解成Cholesky因子:当k=1/2时,K为奇异矩阵;而当k<1/2时,K为对称不定矩阵,这时K有广义Cholesky分解式:并且这种分解是稳定的,一般地我们给出定义 定义1.1 设有矩阵K∈R~((m+n)×(m+n)),若总存在排列矩阵P∈R~((m+n)×(m+n))和对称正定矩阵H∈R~(m×n)、G∈R(m×m)使得则称矩阵K为对称拟定(Symmetric quasidefinite)矩阵。     

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.