Recursive two-levelILU preconditioner for nonsymmetric M-matrices

We develop in this paper some preconditioners for sparse non-symmetric M-matrices, which combine a recursive two-level blockILU factorization with multigrid method, we compare these preconditioners on matrices arising from discretized convection-diffusion equations using upwind finite difference schemes and multigrid orderings, some comparison theorems and experiment results are demonstrated.     

A class of preconditioners based on matrix splitting for nonsymmetric linear systems

Given a general matrix splitting A=M-N where M is nonsingular, a new factorization scheme in terms of factorized and splitting matrices is given using the Sherman-Morrison formula. Theoretical analysis shows that the factorization can give an LDU decomposition of A under some special choices. We propose and implement a class of preconditioners based on this factorization combining with dropping rules. A number of numerical experiments from discrete convection diffusion equation and some practical problems show that the new preconditioner is efficient, and is comparable to existing preconditioners in term of storage requirement and computational cost.     

How to prove that a preconditioner cannot be superlinear

In the general case of multilevel Toeplitz matrices, we recently proved that any multilevel circulant preconditioner is not superlinear (a cluster it may provide cannot be proper). The proof was based on the concept of quasi-equimodular matrices, although this concept does not apply, for example, to the sine-transform matrices. In this paper, with a new concept of partially equimodular matrices, we cover all trigonometric matrix algebras widely used in the literature. We propose a technique for proving the non-superlinearity of certain frequently used preconditioners for some representative sample multilevel matrices. At the same time, we show that these preconditioners are, in a certain sense, the best among the sublinear preconditioners (with only a general cluster) for multilevel Toeplitz matrices.

     

Regularizing properties of a class of matrices including the optimal and the superoptimal preconditioners

In this work, given a positive definite matrix A, we introduce a class of matrices related to A, which is obtained by suitably combining projections of its powers onto algebras of matrices simultaneously diagonalized by a unitary transform. After a detailed theoretical study of some spectral properties of the matrices of this class, which suggests their use as regularizing preconditioners, we prove that such matrices can be cheaply computed when the matrix A has a Toeplitz structure. We provide numerical evidence of the advantages coming from the employment of the proposed preconditioners when used in regularizing procedures.     

Structured preconditioners for nonsingular matrices of block two-by-two structures

For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of practical and efficient structured preconditioners through matrix transformation and matrix approximations. For the specific versions such as modified block Jacobi-type, modified block Gauss-Seidel-type, and modified block unsymmetric (symmetric) Gauss-Seidel-type preconditioners, we precisely describe their concrete expressions and deliberately analyze eigenvalue distributions and positive definiteness of the preconditioned matrices. Also, we show that when these structured preconditioners are employed to precondition the Krylov subspace methods such as GMRES and restarted GMRES, fast and effective iteration solvers can be obtained for the large sparse systems of linear equations with block two-by-two coefficient matrices. In particular, these structured preconditioners can lead to efficient and high-quality preconditioning matrices for some typical matrices from the real-world applications.

     

The spectral properties of the preconditioned matrix for nonsymmetric saddle point problems

In this paper, on the basis of matrix splitting, two preconditioners are proposed and analyzed, for nonsymmetric saddle point problems. The spectral property of the preconditioned matrix is studied in detail. When the iteration parameter becomes small enough, the eigenvalues of the preconditioned matrices will gather into two clusters—one is near (0,0) and the other is near (2,0)—for the PPSS preconditioner no matter whether A is Hermitian or non-Hermitian and for the PHSS preconditioner when A is a Hermitian or real normal matrix. Numerical experiments are given, to illustrate the performances of the two preconditioners.     

Approximate inverse computation using Frobenius inner product

Parallel preconditioners are presented for the solution of general linear systems of equations. The computation of these preconditioners is achieved by orthogonal projections related to the Frobenius inner product. So, min_M∈??∥AM?I∥ _F and matrix M₀∈?? corresponding to this minimum (?? being any vectorial subspace of ??_n(?)) are explicitly computed using accumulative formulae in order to reduce computational cost when subspace ?? is extended to another one containing it. Every step, the computation is carried out taking advantage of the previous one, what considerably reduces the amount of work. These general results are illustrated with the subspace of matrices M such that AM is symmetric. The main application is developed for the subspace of matrices with a given sparsity pattern which may be constructed iteratively by augmenting the set of non‐zero entries in each column. Finally, the effectiveness of the sparse preconditioners is illustrated with some numerical experiments. Copyright © 2002 John Wiley & Sons, Ltd.     

Incomplete blockwise factorizations of (block) H-matrices

The use of incomplete blockwise factorizations as preconditioners in conjugate gradient like methods has become more and more popular in recent years. Most of the theory concerning existence and applicability of these factorizations has been limited to M-matrices so far. Here we introduce a more general definition of block H-matrices (Robert [8]) and we extend the theory to this class of matrices.     

Robust incomplete factorization for nonsymmetric matrices

In this paper, a new incomplete LU factorization preconditioner for nonsymmetric matrices is being considered which is also breakdown-free (no zero pivots occurs) for positive definite matrices. To construct this preconditioner, only the information of matrix A is used and just one of the factors of the AINV process is computed. The L factor is extracted as a by-product of the AINV process. The pivots of the AINV process are used as diagonal entries of U. The new preconditioner has left and right-looking versions. To improve the efficiency of the preconditioner, we have used the inverse-based dropping strategies for both L and U factors. Numerical experiments show that the left-looking version of the preconditioner is significantly faster than its right-looking version in terms of preconditioning time and both are equally effective to reduce the number of iterations. Comparisons of the new preconditioner with AINV and ILUT preconditioners are also presented.     

Spectral discretizations of 3-D elliptic problems and fast domain decomposition methods

An important for applications, the class of hp discretizations of second-order elliptic equations consists of discretizations based on spectral finite elements. The development of fast domain decomposition algorithms for them was restrained by the absence of fast solvers for the basic components of the method, i.e., for local interior problems on decomposition subdomains and their faces. Recently, the authors have established that such solvers can be designed using special factorized preconditioners. In turn, factorized preconditioners are constructed using an important analogy between the stiffness matrices of spectral and hierarchical basis hp-elements (coordinate functions of the latter are defined as tensor products of integrated Legendre polynomials). Due to this analogy, for matrices of spectral elements, fast solvers can be developed that are similar to those for matrices of hierarchical elements. Based on these facts and previous results on the preconditioning of other components, fast domain decomposition algorithms for spectral discretizations are obtained.     

Chebyshev-type methods and preconditioning techniques

Recently, a Newton’s iterative method is attracting more and more attention from various fields of science and engineering. This method is generally quadratically convergent. In this paper, some Chebyshev-type methods with the third order convergence are analyzed in detail and used to compute approximate inverse preconditioners for solving the linear system Ax = b. Theoretic analysis and numerical experiments show that Chebyshev’s method is more effective than Newton’s one in the case of constructing approximate inverse preconditioners.     

A Korovkin-type theory for finite Toeplitz operators via matrix algebras

Preconditioned conjugate gradients (PCG) are widely and successfully used methods for solving a Toeplitz linear system [59,9,20,5,34,62,6,10,28,45,44,46,49]. Frobenius-optimal preconditioners are chosen in some proper matrix algebras and are defined by minimizing the Frobenius distance from . The convergence features of these PCG have been naturally studied by means of the Weierstrass–Jackson Theorem [17,36,45], owing to the profound relationship between the spectral features of the matrices , generated by the Fourier coefficients of a continuous function f, and the analytical properties of the symbol f itself. In this paper, we capsize this point of view by showing that the optimal preconditioners can be used to define both new and just known linear positive operators uniformly approximating the function f. On the other hand, by modifying the Korovkin Theorem to study the Frobenius-optimal preconditioning problem, we provide a new and unifying tool for analyzing all Frobenius-optimal preconditioners in any generic matrix algebra related to trigonometric transforms. Finally, the multilevel case is sketched and discussed by showing that a Korovkin-type Theory also holds in a multivariate sense. Received October 1, 1996 / Revised version received May 7, 1998     

BTTB preconditioners for BTTB least squares problems

In this paper, we consider solving the least squares problem min_x‖b-Tx‖₂ by using preconditioned conjugate gradient (PCG) methods, where T is a large rectangular matrix which consists of several square block-Toeplitz-Toeplitz-block (BTTB) matrices and b is a column vector. We propose a BTTB preconditioner to speed up the PCG method and prove that the BTTB preconditioner is a good preconditioner. We then discuss the construction of the BTTB preconditioner. Numerical examples, including image restoration problems, are given to illustrate the efficiency of our BTTB preconditioner. Numerical results show that our BTTB preconditioner is more efficient than the well-known Level-1 and Level-2 circulant preconditioners.     

Eigenvalue estimates for preconditioned saddle point matrices

New accurate eigenvalue bounds for symmetric matrices of saddle point form are derived and applied for both unpreconditioned and preconditioned versions of the matrices. The estimates enable a better understanding of how preconditioners should be chosen. The preconditioners provide efficient iterative solution of the corresponding linear systems with, for some important applications, an optimal order of computational complexity. The methods are applied for Stokes problem and for linear elasticity problems. Copyright © 2005 John Wiley & Sons, Ltd.     

The optimal preconditioner of strictly diagonally dominant <Emphasis Type="Italic">Z</Emphasis>-matrix

In this paper, we present a series of new preconditioners with parameters of strictly diagonally dominant Z-matrix, which contain properly two kinds of known preconditioners as special cases. Moreover, we prove the monotonicity of spectral radiuses of iterative matrices with respect to the parameters and some comparison theorems. The results obtained show that the bigger the parameter k is（i.e., we select the more upper right diagonal elements to be the preconditioner）, the less the spectral radius of iterative matrix is. A numerical example generated randomly is provided to illustrate the theoretical results.     

Local preconditioners for two‐level non‐overlapping domain decomposition methods

We consider additive two‐level preconditioners, with a local and a global component, for the Schur complement system arising in non‐overlapping domain decomposition methods. We propose two new parallelizable local preconditioners. The first one is a computationally cheap but numerically relevant alternative to the classical block Jacobi preconditioner. The second one exploits all the information from the local Schur complement matrices and demonstrates an attractive numerical behaviour on heterogeneous and anisotropic problems. We also propose two implementations based on approximate Schur complement matrices that are cheaper alternatives to construct the given preconditioners but that preserve their good numerical behaviour. Through extensive computational experiments we study the numerical scalability and the robustness of the proposed preconditioners and compare their numerical performance with well‐known robust preconditioners such as BPS and the balancing Neumann–Neumann method. Finally, we describe a parallel implementation on distributed memory computers of some of the proposed techniques and report parallel performances. Copyright © 2001 John Wiley & Sons, Ltd.     

Two‐level preconditioners for serendipity finite element matrices

In this paper an approach to construct algebraic multilevel preconditioners for serendipity finite element matrices is presented. Two‐level preconditioners constructed in the paper allow to obtain multilevel preconditioners in serendipity case using multilevel preconditioners for linear finite element matrices. Copyright © 2006 John Wiley & Sons, Ltd.     

Fast transforms for tridiagonal linear equations

In this paper we study the use of the Fourier, Sine and Cosine Transform for solving or preconditioning linear systems, which arise from the discretization of elliptic problems. Recently, R. Chan and T. Chan considered circulant matrices for solving such systems. Instead of using circulant matrices, which are based on the Fourier Transform, we apply the Fourier and the Sine Transform directly. It is shown that tridiagonal matrices arising from the discretization of an onedimensional elliptic PDE are connected with circulant matrices by congruence transformations with the Fourier or the Sine matrix. Therefore, we can solve such linear systems directly, using only Fast Fourier Transforms and the Sherman-Morrison-Woodbury formula. The Fast Fourier Transform is highly parallelizable, and thus such an algorithm is interesting on a parallel computer. Moreover, similar relations hold between block tridiagonal matrices and Block Toeplitz-plus-Hankel matrices of ordern ²×n ² in the 2D case. This can be used to define in some sense natural approximations to the given matrix which lead to preconditioners for solving such linear systems.     

Recursive self preconditioning method based on Schur complement for Toeplitz matrices

In this paper, we propose to solve the Toeplitz linear systems T _n x?=?b by a recursive-based method. The method is based on repeatedly dividing the original problem into two subproblems that involve the solution of systems containing the Schur complement of the leading principal submatrix of the previous level. The idea is to solve the linear systems S _m y?=?d, where S _m is the Schur complement of T _2m (the principal submatrix of T _n ), by using a self preconditioned iterative methods. The preconditioners, which are the approximate inverses of S _m , are constructed based on famous Gohberg–Semencul formula. All occurring matrices are represented by proper generating vectors of their displacement rank characterization. We show that, for well conditioned problems, the proposed method is efficient and robust. For ill-conditioned problems, by using some iterative refinement method, the new method would be efficient and robust. Numerical experiments are presented to show the effectiveness of our new method.     

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.