一种新型压缩预处理CGS算法

CGS算法是求解大型非对称线性方程组的常用算法，然而该算法无极小残差性质，因此它常因出现较大的中间剩余向量而出现典型的不规则收敛行为．本根据IRA方法提出了一种压缩预处理CGS方法，数值实验表明这种算法在一定程度上减小了迭代算法在收敛过程中的剩余问题，从而使得算法具有更好的稳定性，该法构造简单，减少了收敛次数，加快了收敛速度．     

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.     

On preconditioned MHSS iteration methods for complex symmetric linear systems

We propose a preconditioned variant of the modified HSS (MHSS) iteration method for solving a class of complex symmetric systems of linear equations. Under suitable conditions, we prove the convergence of the preconditioned MHSS (PMHSS) iteration method and discuss the spectral properties of the PMHSS-preconditioned matrix. Numerical implementations show that the resulting PMHSS preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as GMRES and its restarted variants. In particular, both the stationary PMHSS iteration and PMHSS-preconditioned GMRES show meshsize-independent and parameter-insensitive convergence behavior for the tested numerical examples.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

关于具优势对称部分的不定线性代数方程组的分裂极小残量算法

１．引 言 考虑大型稀疏线性代数方程组 为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销，Ｋｒｙｌｏｖ子空间迭代算法［１，１６，２３］及其预处理变型［６，８，１３，１８，１９］通常是求解（１）的有效而实用的方法．当系数矩阵对称正定时，共轭梯度法（ＣＧ（     

On SSOR‐like preconditioners for non‐Hermitian positive definite matrices

We construct, analyze, and implement SSOR‐like preconditioners for non‐Hermitian positive definite system of linear equations when its coefficient matrix possesses either a dominant Hermitian part or a dominant skew‐Hermitian part. We derive tight bounds for eigenvalues of the preconditioned matrices and obtain convergence rates of the corresponding SSOR‐like iteration methods as well as the corresponding preconditioned GMRES iteration methods. Numerical implementations show that Krylov subspace iteration methods such as GMRES, when accelerated by the SSOR‐like preconditioners, are efficient solvers for these classes of non‐Hermitian positive definite linear systems. Copyright © 2015 John Wiley & Sons, Ltd.     

几乎各向同性的高维空间分数阶扩散方程的分块快速正则Hermite分裂预处理方法

一类空间分数阶扩散方程经过有限差分离散后所得到的离散线性方程组的系数矩阵是两个对角矩阵与Toeplitz型矩阵的乘积之和.在本文中,对于几乎各向同性的二维或三维空间分数阶扩散方程的离散线性方程组,采用预处理Krylov子空间迭代方法,我们利用其系数矩阵的特殊结构和具体性质构造了一类分块快速正则Hermite分裂预处理子.通过理论分析,我们证明了所对应的预处理矩阵的特征值大部分都聚集于1的附近.数值实验也表明,这类分块快速正则Hermite分裂预处理子可以明显地加快广义极小残量(GMRES)方法和稳定化的双共轭梯度(BiCGSTAB)方法等Krylov子空间迭代方法的收敛速度.     

Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices

For a class of block two-by-two systems of linear equations with certain skew-Hamiltonian coefficient matrices, we construct additive block diagonal preconditioning matrices and discuss the eigen-properties of the corresponding preconditioned matrices. The additive block diagonal preconditioners can be employed to accelerate the convergence rates of Krylov subspace iteration methods such as MINRES and GMRES. Numerical experiments show that MINRES preconditioned by the exact and the inexact additive block diagonal preconditioners are effective, robust and scalable solvers for the block two-by-two linear systems arising from the Galerkin finite-element discretizations of a class of distributed control problems.     

A Class of Nested Iteration Schemes for Linear Systems with a Coefficient Matrix with a Dominant Positive Definite Symmetric Part

We present a class of nested iteration schemes for solving large sparse systems of linear equations with a coefficient matrix with a dominant symmetric positive definite part. These new schemes are actually inner/outer iterations, which employ the classical conjugate gradient method as inner iteration to approximate each outer iterate, while each outer iteration is induced by a convergent and symmetric positive definite splitting of the coefficient matrix. Convergence properties of the new schemes are studied in depth, possible choices of the inner iteration steps are discussed in detail, and numerical examples from the finite-difference discretization of a second-order partial differential equation are used to further examine the effectiveness and robustness of the new schemes over GMRES and its preconditioned variant. Also, we show that the new schemes are, at least, comparable to the variable-step generalized conjugate gradient method and its preconditioned variant.     

Upper bounds for convergence rates of acceleration methods with initial iterations

GMRES(n,k), a version of GMRES for the solution of large sparse linear systems, is introduced. A cycle of GMRES(n,k) consists of n Richardson iterations followed by k iterations of GMRES. Such cycles can be repeated until convergence is achieved. The advantage in this approach is in the opportunity to use moderate k, which results in time and memory saving. Because the number of inner products among the vectors of iteration is about k^2/2, using a moderate k is particularly attractive on message-passing parallel architectures, where inner products require expensive global communication. The present analysis provides tight upper bounds for the convergence rates of GMRES(n,k) for problems with diagonalizable coefficient matrices whose spectra lie in an ellipse in 0. The advantage of GMRES(n,k) over GMRES(k) is illustrated numerically.     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

Solution of linear systems from an optimal control problem arising in wind simulation

Several solution strategies for a class of large, sparse linear systems with a block 2 × 2 structure arising from the finite element discretization of an optimal control problem in wind simulation are introduced and analyzed. Block preconditioners and a sparse direct solver on the original coupled system are compared with a preconditioned GMRES iteration applied to a reduced system (Schur complement). Theoretical and experimental results demonstrate the effectiveness of the reduced system approach. Copyright © 2009 John Wiley & Sons, Ltd.     

Preconditioned iterative methods for coupled discretizations of fluid flow problems

Computational fluid dynamics, where simulations require largecomputation times, is one of the areas of application of highperformance computing. Schemes such as the SIMPLE (semi-implicitmethod for pressure-linked equations) algorithm are often usedto solve the discrete Navier-Stokes equations. Generally theseschemes take a short time per iteration but require a largenumber of iterations. For simple geometries (or coarser grids)the overall CPU time is small. However, for finer grids or morecomplex geometries the increase in the number of iterationsmay be a drawback and the decoupling of the differential equationsinvolved implies a slow convergence of rotationally dominatedproblems that can be very time consuming for realistic applications.So we analyze here another approach, DIRECTO, that solves theequations in a coupled way. With recent advances in hardwaretechnology and software design, it became possible to solvecoupled Navier-Stokes systems, which are more robust but implyincreasing computational requirements (both in terms of memoryand CPU time). Two approaches are described here (band blockLU factorization and preconditioned GMRES) for the linear solverrequired by the DIRECTO algorithm that solves the fluid flowequations as a coupled system. Comparisons of the effectivenessof incomplete factorization preconditioners applied to the GMRES(generalized minimum residual) method are shown. Some numericalresults are presented showing that it is possible to minimizeconsiderably the CPU time of the coupled approach so that itcan be faster than the decoupled one.     

A simpler GMRES

The generalized minimal residual (GMRES) method is widely used for solving very large, nonsymmetric linear systems, particularly those that arise through discretization of continuous mathematical models in science and engineering. By shifting the Arnoldi process to begin with Ar₀ instead of r₀, we obtain simpler Gram–Schmidt and Householder implementations of the GMRES method that do not require upper Hessenberg factorization. The Gram–Schmidt implementation also maintains the residual vector at each iteration, which allows cheaper restarts of GMRES(m) and may otherwise be useful.     

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.

     

Multistep matrix splitting iteration preconditioning for singular linear systems

Multistep matrix splitting iterations serve as preconditioning for Krylov subspace methods for solving singular linear systems. The preconditioner is applied to the generalized minimal residual (GMRES) method and the flexible GMRES (FGMRES) method. We present theoretical and practical justifications for using this approach. Numerical experiments show that the multistep generalized shifted splitting (GSS) and Hermitian and skew-Hermitian splitting (HSS) iteration preconditioning are more robust and efficient compared to standard preconditioners for some test problems of large sparse singular linear systems.     

Strang‐type preconditioners applied to ordinary and neutral differential‐algebraic equations

This paper deals with boundary‐value methods (BVMs) for ordinary and neutral differential‐algebraic equations. Different from what has been done in Lei and Jin (Lecture Notes in Computer Science, vol. 1988. Springer: Berlin, 2001; 505–512), here, we directly use BVMs to discretize the equations. The discretization will lead to a nonsymmetric large‐sparse linear system, which can be solved by the GMRES method. In order to accelerate the convergence rate of GMRES method, two Strang‐type block‐circulant preconditioners are suggested: one is for ordinary differential‐algebraic equations (ODAEs), and the other is for neutral differential‐algebraic equations (NDAEs). Under some suitable conditions, it is shown that the preconditioners are invertible, the spectra of the preconditioned systems are clustered, and the solution of iteration converges very rapidly. The numerical experiments further illustrate the effectiveness of the methods. Copyright © 2011 John Wiley & Sons, Ltd.     

A note on preconditioned GMRES for solving singular linear systems

For solving a singular linear system Ax=b by GMRES, it is shown in the literature that if A is range-symmetric, then GMRES converges safely to a solution. In this paper we consider preconditioned GMRES for solving a singular linear system, we construct preconditioners by so-called proper splittings, which can ensure that the coefficient matrix of the preconditioned system is range-symmetric.     

Sine transform based preconditioning techniques for space fractional diffusion equations

We study the preconditioned iterative methods for the linear systems arising from the numerical solution of the multi-dimensional space fractional diffusion equations. A sine transform based preconditioning technique is developed according to the symmetric and skew-symmetric splitting of the Toeplitz factor in the resulting coefficient matrix. Theoretical analyses show that the upper bound of relative residual norm of the GMRES method when applied to the preconditioned linear system is mesh-independent which implies the linear convergence. Numerical experiments are carried out to illustrate the correctness of the theoretical results and the effectiveness of the proposed preconditioning technique.