Experimental study of ILU preconditioners for indefinite matrices

Incomplete LU factorization preconditioners have been surprisingly successful for many cases of general nonsymmetric and indefinite matrices. However, their failure rate is still too high for them to be useful as black-box library software for general matrices. Besides fatal breakdowns due to zero pivots, the major causes of failure are inaccuracy, and instability of the triangular solves. When there are small pivots, both these problems can occur, but these problems can also occur without small pivots. Through examples from actual problems, this paper shows how these problems evince themselves, how these problems can be detected, and how these problems can sometimes be circumvented through pivoting, reordering, scaling, perturbing diagonal elements, and preserving symmetric structure. The goal of this paper is to gain a better practical understanding of ILU preconditioners and help improve their reliability.     

Compressed sensing with preconditioning for sparse recovery with subsampled matrices of Slepian prolate functions

Efficient recovery of smooth functions which are s-sparse with respect to the basis of so-called prolate spheroidal wave functions from a small number of random sampling points is considered. The main ingredient in the design of both the algorithms we propose here consists in establishing a uniform L ^∞ bound on the measurement ensembles which constitute the columns of the sensing matrix. Such a bound provides us with the restricted isometry property for this rectangular random matrix, which leads to either the exact recovery property or the “best s-term approximation” of the original signal by means of the ? ¹ minimization program. The first algorithm considers only a restricted number of columns for which the L ^∞ holds as a consequence of the fact that eigenvalues of the Bergman’s restriction operator are close to 1 whereas the second one allows for a wider system of PSWF by taking advantage of a preconditioning technique. Numerical examples are spread throughout the text to illustrate the results.     

Constraint preconditioning for nonsymmetric indefinite linear systems

This paper introduces and presents theoretical analyses of constraint preconditioning via a Schilders'‐like factorization for nonsymmetric saddle‐point problems. We extend the Schilders' factorization of a constraint preconditioner to a nonsymmetric matrix by using a different factorization. The eigenvalue and eigenvector distributions of the preconditioned matrix are determined. The choices of the parameter matrices in the extended Schilders' factorization and the implementation of the preconditioning step are discussed. An upper bound on the degree of the minimum polynomial for the preconditioned matrix and the dimension of the corresponding Krylov subspace are determined, as well as the convergence behavior of a Krylov subspace method such as GMRES. Numerical experiments are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

Some interlacing results for indefinite Hermitian matrices

A classical theorem of Cauchy states that the eigenvalues of a principal submatrix A₀ of a Hermitian matrix A interlace the eigenvalues of A. We consider the case of a matrix A which is Hermitian with respect to an indefinite inner product.     

Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.     

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     

A note for preconditioning nonsymmetric matrices

In this paper, we consider preconditioners for generalized saddle point systems with a nonsymmetric coefficient matrix. A constraint preconditioner for this systems is constructed, and some spectral properties of the preconditioned matrix are given. Our results extend the corresponding ones in [3] and [4].     

A power sparse approximate inverse preconditioning procedure for large sparse linear systems

Motivated by the Cayley–Hamilton theorem, a novel adaptive procedure, called a Power Sparse Approximate Inverse (PSAI) procedure, is proposed that uses a different adaptive sparsity pattern selection approach to constructing a right preconditioner M for the large sparse linear system Ax=b. It determines the sparsity pattern of M dynamically and computes the n independent columns of M that is optimal in the Frobenius norm minimization, subject to the sparsity pattern of M. The PSAI procedure needs a matrix–vector product at each step and updates the solution of a small least squares problem cheaply. To control the sparsity of M and develop a practical PSAI algorithm, two dropping strategies are proposed. The PSAI algorithm can capture an effective approximate sparsity pattern of A^?1 and compute a good sparse approximate inverse M efficiently. Numerical experiments are reported to verify the effectiveness of the PSAI algorithm. Numerical comparisons are made for the PSAI algorithm and the adaptive SPAI algorithm proposed by Grote and Huckle as well as for the PSAI algorithm and three static Sparse Approximate Inverse (SAI) algorithms. The results indicate that the PSAI algorithm is at least comparable to and can be much more effective than the adaptive SPAI algorithm and it often outperforms the static SAI algorithms very considerably and is more robust and practical than the static ones for general problems. Copyright © 2008 John Wiley & Sons, Ltd.     

Determinantal formulae for matrices with sparse inverses

The determinant of a matrix is expressed in terms of certain of its principal minors by a formula which can be “read off” from the graph of the inverse of the matrix. The only information used is the zero pattern of the inverse, and each zero pattern yields one or more corresponding formulae for the determinant.     

Solving the eigenvalue problem for sparse matrices

A modification of the Danilewski method is presented, permitting the solution of the eigenvalue problem for a constant sparse matrix of large order to be reduced to the solution of the same problem for a polynomial matrix of lower order. Certain solution algorithms are proposed for a partial eigenvalue problem for the polynomial matrix. Questions of the realization of the algorithms on a model PRORAB computer are examined.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 58, pp. 92–110, 1976.     

Multilevel preconditioning for perturbed finite element matrices

Multilevel preconditioning methods for finite element matricesfor the approximation of second-order elliptic problems areconsidered. Using perturbations of the local finite elementmatrices by zero-order terms it is shown that one can controlthe smallest eigenvalues. In this way in a multilevel methodone can reach a final coarse mesh, where the remaining problemto be solved has a condition number independent of the totaldegrees of freedom, much earlier than if no perturbations wereused. Hence, there is no need in a method of optimal computationalcomplexity to carry out the recursion in the multilevel methodto a coarse mesh with a fixed number of degrees of freedom.     

On approximated ILU and UGS preconditioning methods for linearized discretized steady incompressible Navier-Stokes equations

When the artificial compressibility method in conjunction with high-order upwind compact finite difference schemes is employed to discretize the steady-state incompressible Navier-Stokes equations, in each pseudo-time step we need to solve a structured system of linear equations approximately by, for example, a Krylov subspace method such as the preconditioned GMRES. In this paper, based on the special structure and concrete property of the linear system we construct a structured preconditioner for its coefficient matrix and estimate eigenvalue bounds of the correspondingly preconditioned matrix. Numerical examples are given to illustrate the effectiveness of the proposed preconditioning methods.     

A residual based sparse approximate inverse preconditioning procedure for large sparse linear systems

We propose a residual based sparse approximate inverse (RSAI) preconditioning procedure, for the large sparse linear system A x =b . Different from the SParse Approximate Inverse (SPAI) algorithm proposed by Grote and Huckle (SIAM Journal on Scientific Computing, 18 (1997), pp. 838–853.), RSAI uses only the dominant other than all the information on the current residual and augments sparsity patterns adaptively during loops. In order to control the sparsity of M , we develop two practical algorithms RSAI(f i x ) and RSAI(t o l ). RSAI(f i x ) retains the prescribed number of large nonzero entries and adjusts their positions in each column of M among all available ones, in which the number of large entries is increased by a fixed number at each loop. In contrast, the existing indices of M by SPAI are untouched in subsequent loops and a few most profitable indices are added to each column of M from the new candidates in the next loop. RSAI(t o l ) is a tolerance based dropping algorithm and retains all large entries by dynamically dropping small ones below some tolerances, and it better suits for the problem where the numbers of large entries in the columns of A ^?1 differ greatly. When the two preconditioners M have almost the same or comparable numbers of nonzero entries, the numerical experiments on real‐world problems demonstrate that RSAI(f i x ) is highly competitive with SPAI and can outperform the latter for some problems. We also make comparisons of RSAI(f i x ), RSAI(t o l ), and power sparse approximate inverse(t o l ) proposed Jia and Zhu (Numerical Linear Algebra with Applications, 16 (2009), pp.259–299.) and incomplete LU factorization type methods and draw some general conclusions.     

New results for EP matrices in indefinite inner product spaces

In this paper we study J-EP matrices, as a generalization of EP-matrices in indefinite inner product spaces, with respect to indefinite matrix product. We give some properties concerning EP and J-EP matrices and find connection between them. Also, we present some results for reverse order law for Moore-Penrose inverse in indefinite setting. Finally, we deal with the star partial ordering and improve some results given in the “EP matrices in indefinite inner product spaces” (2012), by relaxing some conditions.     

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)     

A hierarchical algorithm for making sparse matrices sparser

IfA is the (sparse) coefficient matrix of linear equality constraints, for what nonsingularT is ≡TA as sparse as possible, and how can it be efficiently computed? An efficient algorithm for thisSparsity Problem (SP) would be a valuable pre-processor for linearly constrained optimization problems. In this paper we develop a two-pass approach to solve SP. Pass 1 builds a combinatorial structure on the rows ofA which hierarchically decomposes them into blocks. This determines the structure of the optimal transformation matrixT. In Pass 2, we use the information aboutT as a road map to do block-wise partial Gauss-Jordan elimination onA. Two block-aggregation strategies are also suggested that could further reduce the time spend in Pass 2. Computational results indicate that this approach to increasing sparsity produces significant net reductions in simplex solution time.     

on hybrid preconditioning methods for large sparse saddle-point problems

Based on the block-triangular product approximation to a 2-by-2 block matrix, a class of hybrid preconditioning methods is designed for accelerating the MINRES method for solving saddle-point problems. The appropriate values for the parameters involved in the new preconditioners are estimated, so that the numerical conditioning and the spectral property of the saddle-point matrix of the linear system can be substantially improved. Several practical hybrid preconditioners and the corresponding preconditioning iterative methods are constructed and studied, too.     

The rank of sparse random matrices

We determine the asymptotic normalized rank of a random matrix $\mathit{A}$ over an arbitrary field with prescribed numbers of nonzero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conjecture of Lelarge (2013). The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that diminishes the number of short linear relations.     

A spectral algorithm for envelope reduction of sparse matrices

The problem of reordering a sparse symmetric matrix to reduce its envelope size is considered. A new spectral algorithm for computing an envelope-reducing reordering is obtained by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. This Laplacian eigenvector solves a continuous relaxation of a discrete problem related to envelope minimization called the minimum 2-sum problem. The permutation vector computed by the spectral algorithm is a closest permutation vector to the specified Laplacian eigenvector. Numerical results show that the new reording algorithm usually computes smaller envelope sizes than those obtained from the current standards such as the Gibbs—Poole—Stockmeyer (GPS) algorithm or the reverse Cuthill—McKee (RCM) algorithm in SPARSPAK, in some cases reducing the envelope by more than a factor of two.