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 note on constraint preconditioners for nonsymmetric saddle point problems

A class of constraint preconditioners for solving two‐by‐two block linear equations with the (1,2)‐block being the transpose of the (2,1)‐block and the (2,2)‐block being zero was investigated in a recent paper of Cao (Numer. Math. 2006; 103 :47–61). In this short note, we extend his idea by allowing the (1,2)‐block to be not equal to the transpose of the (2,1)‐block. Results concerning the spectrum, the form of the eigenvectors and the convergence behaviour of a Krylov subspace method, such as GMRES are presented. Copyright © 2007 John Wiley & Sons, Ltd.     

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.     

Constraint preconditioning for linear systems in elasticity

The mixed variational formulation of elastic deformation of a material body leads to a constraint minimisation (or saddle‐point) problem. Using the PEERS finite element space to discretise the problem one gets an indefinite system of linear equations. To solve this system, preconditioners with similar saddle‐point patterns will be applied. The results of numerical tests with this preconditioning strategy show its efficiency for linear systems with up to more than half a million unknowns.     

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.     

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).     

A backward stability analysis of diagonal pivoting methods for solving unsymmetric tridiagonal systems without interchanges

This paper concerns the LBM ^T factorization of unsymmetric tridiagonal matrices, where L and M are unit lower triangular matrices and B is block diagonal with 1×1 and 2×2 blocks. In some applications, it is necessary to form this factorization without row or column interchanges while the tridiagonal matrix is formed. Bunch and Kaufman proposed a pivoting strategy without interchanges specifically for symmetric tridiagonal matrices, and more recently, Bunch and Marcia proposed pivoting strategies that are normwise backward stable for linear systems involving such matrices. In this paper, we extend these strategies to the unsymmetric tridiagonal case and demonstrate that the proposed methods both exhibit bounded growth factors and are normwise backward stable. Copyright © 2009 John Wiley & Sons, Ltd.     

Preconditioning spectral element schemes for definite and indefinite problems

Spectral element schemes for the solution of elliptic boundary value problems are considered. Preconditioning methods based on finite difference and finite element schemes are implemented. Numerical experiments show that inverting the preconditioner by a single multigrid iteration is most efficient and that the finite difference preconditioner is superior to the finite element one for both definite and indefinite problems. A multigrid preconditioner is also derived from the finite difference preconditioner and is found suitable for the CGS acceleration method. It is pointed out that, for the finite difference and finite element preconditioners, CGS does not always converge to the accurate algebraic solution. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 535–543, 1999     

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.     

Weighted FOM and GMRES for solving nonsymmetric linear systems

This paper presents two new methods called WFOM and WGMRES, which are variants of FOM and GMRES, for solving large and sparse nonsymmetric linear systems. To accelerate the convergence, these new methods use a different inner product instead of the Euclidean one. Furthermore, at each restart, a different inner product is chosen. The weighted Arnoldi process is introduced for implementing these methods. After describing the weighted methods, we give the relations that link them to FOM and GMRES. Experimental results are presented to show the good performances of the new methods compared to FOM(m) and GMRES(m). This revised version was published online in August 2006 with corrections to the Cover Date.     

On the Odir iterative method for non‐symmetric indefinite linear systems

Several Krylov subspace iterative methods have been proposed for the approximation of the solution of general non‐symmetric linear systems. Odir is such a method. Here we study the restarted version of Odir for non‐symmetric indefinite linear systems and we prove convergence under certain conditions on the matrix of coefficients. These results hold for all the restarted Krylov methods equivalent to Odir. We also introduce a new truncated Odir method which is proved to converge for a large class of non‐symmetric indefinite linear systems. This new method requires one‐half of the storage of the standard Odir. Copyright © 2001 John Wiley & Sons, Ltd.     

Improving the stability and robustness of incomplete symmetric indefinite factorization preconditioners

Sparse symmetric indefinite linear systems of equations arise in numerous practical applications. In many situations, an iterative method is the method of choice but a preconditioner is normally required for it to be effective. In this paper, the focus is on a class of incomplete factorization algorithms that can be used to compute preconditioners for symmetric indefinite systems. A limited memory approach is employed that incorporates a number of new ideas with the goal of improving the stability, robustness, and efficiency of the preconditioner. These include the monitoring of stability as the factorization proceeds and the incorporation of pivot modifications when potential instability is observed. Numerical experiments involving test problems arising from a range of real‐world applications demonstrate the effectiveness of our approach.     

Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems

A variant of balancing domain decomposition method by constraints (BDDC) is proposed for solving a class of indefinite systems of linear equations of the form (K?σ²M)u=f, which arise from solving eigenvalue problems when an inverse shifted method is used and also from the finite element discretization of Helmholtz equations. Here, both K and M are symmetric positive definite. The proposed BDDC method is closely related to the previous dual–primal finite element tearing and interconnecting method (FETI‐DP) for solving this type of problems (Appl. Numer. Math. 2005; 54 :150–166), where a coarse level problem containing certain free‐space solutions of the inherent homogeneous partial differential equation is used in the algorithm to accelerate the convergence. Under the condition that the diameters of the subdomains are small enough, the convergence rate of the proposed algorithm is established, which depends polylogarithmically on the dimension of the individual subdomain problems and which improves with a decrease of the subdomain diameters. These results are supported by numerical experiments of solving a two‐dimensional problem. Copyright © 2009 John Wiley & Sons, Ltd.     

A simplified pivoting strategy for symmetric tridiagonal matrices

The pivoting strategy of Bunch and Marcia for solving systems involving symmetric indefinite tridiagonal matrices uses two different methods for solving 2 × 2 systems when a 2 × 2 pivot is chosen. In this paper, we eliminate this need for two methods by adding another criterion for choosing a 1 × 1 pivot. We demonstrate that all the results from the Bunch and Marcia pivoting strategy still hold. Copyright © 2006 John Wiley & Sons, Ltd.     

A pivoting strategy for symmetric tridiagonal matrices

The LBL^T factorization of Bunch for solving linear systems involving a symmetric indefinite tridiagonal matrix T is a stable, efficient method. It computes a unit lower triangular matrix L and a block 1 × 1 and 2 × 2 matrix B such that T=LBL^T. Choosing the pivot size requires knowing a priori the largest element σ of T in magnitude. In some applications, it is required to factor T as it is formed without necessarily knowing σ. In this paper, we present a modification of the Bunch algorithm that can satisfy this requirement. We demonstrate that this modification exhibits the same bound on the growth factor as the Bunch algorithm and is likewise normwise backward stable. Copyright © 2005 John Wiley & Sons, Ltd.     

A class of constraint preconditioners for nonsymmetric saddle point matrices

We consider the use of a class of constraint preconditioners for the application of the Krylov subspace iterative method to the solution of large nonsymmetric, indefinite linear systems. The eigensolution distribution of the preconditioned matrix is determined and the convergence behavior of a Krylov subspace method such as GMRES is described. The choices of the parameter matrices and the implementation of the preconditioning step are discussed. Numerical experiments are presented. This work is supported by NSFC Projects 10171021 and 10471027.     

Real valued iterative methods for solving complex symmetric linear systems

Complex valued systems of equations with a matrix R + 1S where R and S are real valued arise in many applications. A preconditioned iterative solution method is presented when R and S are symmetric positive semi‐definite and at least one of R, S is positive definite. The condition number of the preconditioned matrix is bounded above by 2, so only very few iterations are required. Applications when solving matrix polynomial equation systems, linear systems of ordinary differential equations, and using time‐stepping integration schemes based on Padé approximation for parabolic and hyperbolic problems are also discussed. Numerical comparisons show that the proposed real valued method is much faster than the iterative complex symmetric QMR method. Copyright © 2000 John Wiley & Sons, Ltd.     

Solving linear systems using wavelet compression combined with Kronecker product approximation

Discrete wavelet transform approximation is an established means of approximating dense linear systems arising from discretization of differential and integral equations defined on a one-dimensional domain. For higher dimensional problems, approximation with a sum of Kronecker products has been shown to be effective in reducing storage and computational costs. We have combined these two approaches to enable solution of very large dense linear systems by an iterative technique using a Kronecker product approximation represented in a wavelet basis. Further approximation of the system using only a single Kronecker product provides an effective preconditioner for the system. Here we present our methods and illustrate them with some numerical examples. This technique has the potential for application in a range of areas including computational fluid dynamics, elasticity, lubrication theory and electrostatics. AMS subject classification 65F10, 65T60, 65F30 Judith M. Ford: This author was supported by EPSRC Postdoctoral Research Fellowship ref: GR/R95982/01. Current address: Royal Liverpool Children's NHS Trust, Liverpool, L12 2AP. Eugene E. Tyrtyshnikov: This author was supported by the Russian Fund of Basic Research (grant 02-01-00590) and Science Support Foundation.     

具有不定位势的渐近线性p-Laplacian Dirichlet问题

利用山路引理及极小作用原理,证明了当非线性项在无穷远处满足一定的渐近线性条件时,具有不定位势的渐近线性p-Laplacian Dirichlet问题,存在非平凡解.