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.     

Parallel implementation of a multiblock method with approximate subdomain solution

Solution of large linear systems encountered in computational fluid dynamics often naturally leads to some form of domain decomposition, especially when it is desired to use parallel machines. It has been proposed to use approximate solvers to obtain fast but rough solutions on the separate subdomains. In this paper approximate solutions via (1) an inner preconditioned GMRES iteration to fixed tolerance, and (2) incomplete factorization (RILU, restricted to the diagonal) are considered. Numerical experiments for a fundamental test problem are included which show speedups obtained on a cluster of workstations as well as on a distributed memory parallel computer. Additionally, the parallel implementation of GCR is addressed, with particular focus on communication costs associated with orthogonalization processes. This consideration brings up questions concerning the use of Householder reflections with GCR.     

Schwarz preconditioners for the spectral element discretization of the steady Stokes and Navier-Stokes equations

Summary. The - spectral element discretization of the Stokes equation gives rise to an ill-conditioned, indefinite, symmetric linear system for the velocity and pressure degrees of freedom. We propose a domain decomposition method which involves the solution of a low-order global, and several local problems, related to the vertices, edges, and interiors of the subdomains. The original system is reduced to a symmetric equation for the velocity, which can be solved with the conjugate gradient method. We prove that the condition number of the iteration operator is bounded from above by , where C is a positive constant independent of the degree N and the number of subdomains, and is the inf-sup condition of the pair -. We also consider the stationary Navier-Stokes equations; in each Newton step, a non-symmetric indefinite problem is solved using a Schwarz preconditioner. By using an especially designed low-order global space, and the solution of local problems analogous to those decribed above for the Stokes equation, we are able to present a complete theory for the method. We prove that the number of iterations of the GMRES method, at each Newton step, is bounded from above by . The constant C does not depend on the number of subdomains or N, and it does not deteriorate as the Newton iteration proceeds. Received March 2, 1998 / Revised version received October 12, 1999 / Published online March 20, 2001     

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.     

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.     

A new adaptive GMRES algorithm for achieving high accuracy

GMRES(k) is widely used for solving non-symmetric linear systems. However, it is inadequate either when it converges only for k close to the problem size or when numerical error in the modified Gram–Schmidt process used in the GMRES orthogonalization phase dramatically affects the algorithm performance. An adaptive version of GMRES(k) which tunes the restart value k based on criteria estimating the GMRES convergence rate for the given problem is proposed here. This adaptive GMRES(k) procedure outperforms standard GMRES(k), several other GMRES-like methods, and QMR on actual large scale sparse structural mechanics postbuckling and analog circuit simulation problems. There are some applications, such as homotopy methods for high Reynolds number viscous flows, solid mechanics postbuckling analysis, and analog circuit simulation, where very high accuracy in the linear system solutions is essential. In this context, the modified Gram–Schmidt process in GMRES, can fail causing the entire GMRES iteration to fail. It is shown that the adaptive GMRES(k) with the orthogonalization performed by Householder transformations succeeds whenever GMRES(k) with the orthogonalization performed by the modified Gram–Schmidt process fails, and the extra cost of computing Householder transformations is justified for these applications. © 1998 John Wiley & Sons, Ltd.     

A flexible CMRH algorithm for nonsymmetric linear systems

A flexible version of the CMRH algorithm is presented that allows varying preconditioning at every step of the algorithm. A consequence of the flexibility of this new variant is that any iterative methods can be incorporated as a preconditioner in the inner steps. Theoretical results that relate the residual norm of the new algorithm and the flexible GMRES, the new algorithm with CMRH itself, are given. Numerical experiments are carried out to illustrate the effectiveness of the proposed algorithm in comparison with the standard CMRH algorithm, ILU-preconditioned CMRH variants and the flexible GMRES algorithm.     

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.     

Generalizations and modifications of the GMRES iterative method

For solving nonsymmetric linear systems, the well-known GMRES method is considered to be a stable method; however, the work per iteration increases as the number of iterations increases. We consider two new iterative methods GGMRES and MGMRES, which are a generalization and a modification of the GMRES method, respectively. Instead of using a minimization condition as in the derivation of GGMRES, we use a Galerkin condition to derive the MGMRES method. We also introduce another new iterative method, LAN/MGMRES, which is designed to combine the reliability of GMRES with the reduced work of a Lanczos-type method. A computer program has been written based on the use of the LAN/MGMRES algorithm for solving nonsymmetric linear systems arising from certain elliptic problems. Numerical tests are presented comparing this algorithm with some other commonly used iterative algorithms. These preliminary tests of the LAN/MGMRES algorithm show that it is comparable in terms of both the approximate number of iterations and the overall convergence behavior. This revised version was published online in June 2006 with corrections to the Cover Date.     

CGS/GMRES(k): AN ADAPTIVE PRECONDITIONED CGS ALGORITHM FOR NONSYMMETRIC LINEAR SYSTEMS

Recently Y. Saad proposed a flexible inner-outer preconditioned GMRES algorithm for nonsymmetric linear systems [4]. Following their ideas, we suggest an adaptive preconditioned CGS method, called CGS/GMRES (k), in which the preconditioner is constructed in the iteration step of CGS, by several steps of GMRES(k). Numerical experiments show that the residual of the outer iteration decreases rapidly. We also found the interesting residual behaviour of GMRES for the skewsymmetric linear system Ax = b, which gives a convergence result for restarted GMRES (k). For convenience, we discuss real systems.     

一种灵活的混合GMRES算法

1　引　　言考虑线性方程组Ax =b (1 .1 )其中 A∈RN× N是非奇异的 .求解方程组 (1 .1 )的很多迭代方法都可归类于多项式法 ,即满足x(n) =x(0 ) +qn- 1 (A) r(0 ) ,degqn- 1 ≤ n -1这里 x(n) ,n≥ 0为第 n步迭代解 ,r(n) =b-Ax(n) 是对应的迭代残量 .等价地 ,r(n) =pn(A) r(0 ) ,degpn≤ n;pn(0 ) =1 (1 .2 )其中 pn(z) =1 -zqn- 1 (z)称为残量多项式 .或有r(n) -r(0 ) ∈ AKn(r(0 ) ,A)其中 Kn(v,A)≡span{ Aiv} n- 1 i=0 是对应于 v,A的 Krylov子空间 .对于非对称问题 ,可以用正交性条件r(n)⊥ AKn(r(0 ) ,A)来确定 (1 .2 )中的…     

Linear and nonlinear substructured Restricted Additive Schwarz iterations and preconditioning

Iterative substructuring Domain Decomposition (DD) methods have been extensively studied, and they are usually associated with nonoverlapping decompositions. It is less known that classical overlapping DD methods can also be formulated in substructured form, i.e., as iterative methods acting on variables defined exclusively on the interfaces of the overlapping domain decomposition. We call such formulations substructured domain decomposition methods. We introduce here a substructured version of Restricted Additive Schwarz (RAS) which we call SRAS. We show that RAS and SRAS are equivalent when used as iterative solvers, as they produce the same iterates, while they are substantially different when used as preconditioners for GMRES. We link the volume and substructured Krylov spaces and show that the iterates are different by deriving the least squares problems solved at each GMRES iteration. When used as iterative solvers, SRAS presents computational advantages over RAS, as it avoids computations with matrices and vectors at the volume level. When used as preconditioners, SRAS has the further advantage of allowing GMRES to store smaller vectors and perform orthogonalization in a lower dimensional space. We then consider nonlinear problems, and we introduce SRASPEN (Substructured Restricted Additive Schwarz Preconditioned Exact Newton), where SRAS is used as a preconditioner for Newton’s method. In contrast to the linear case, we prove that Newton’s method applied to the preconditioned volume and substructured formulation produces the same iterates in the nonlinear case. Next, we introduce two-level versions of nonlinear SRAS and SRASPEN. Finally, we validate our theoretical results with numerical experiments.

     

GMRES方法的收敛率

1 引 言 GMRES方法是目前求解大型稀疏非对称线性方程组 Ax=b,A∈R~(n×n);x,b∈R~n (1)最为流行的方法之一.设x~((0))是(1)解的初始估计,r~((0))=b-Ax~((0))是初始残量,K_k=span{r~((0)),Ar~((0)),…A~(k-1)r~((0))}为由r~((0))和A产生的Krylov子空间.GMRES方法的第k步     

A coarse–fine‐mesh stabilization for an alternating Schwarz domain decomposition method

Domain decomposition methods can be solved in various ways. In this paper, domain decomposition in strips is used. It is demonstrated that a special version of the Schwarz alternating iteration method coupled with coarse–fine‐mesh stabilization leads to a very efficient solver, which is easy to implement and has a behavior nearly independent of mesh and problem parameters. The novelty of the method is the use of alternating iterations between odd‐ and even‐numbered subdomains and the replacement of the commonly used coarse‐mesh stabilization method with coarse–fine‐mesh stabilization.     

Adaptive version of Simpler GMRES

In this paper we propose a stable variant of Simpler GMRES. It is based on the adaptive choice of the Krylov subspace basis at a given iteration step using the intermediate residual norm decrease criterion. The new direction vector is chosen as in the original implementation of Simpler GMRES or it is equal to the normalized residual vector as in the GCR method. We show that such an adaptive strategy leads to a well-conditioned basis of the Krylov subspace and we support our theoretical results with illustrative numerical examples.     

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.     

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.     

The preconditioned GMRES method for systems of coupled FEM-BEM equations

We analyze the generalized minimal residual method (GMRES) as a solver for coupled finite element and boundary element equations. To accelerate the convergence of GMRES we apply a hierarchical basis block preconditioner for piecewise linear finite elements and piecewise constant boundary elements. It is shown that the number of iterations which is necessary to reach a given accuracy grows only poly-logarithmically with the number of unknowns. This revised version was published online in June 2006 with corrections to the Cover Date.     

Deflated and Augmented Krylov Subspace Techniques

We present a general framework for a number of techniques based on projection methods on ‘augmented Krylov subspaces’. These methods include the deflated GMRES algorithm, an inner–outer FGMRES iteration algorithm, and the class of block Krylov methods. Augmented Krylov subspace methods often show a significant improvement in convergence rate when compared with their standard counterparts using the subspaces of the same dimension. The methods can all be implemented with a variant of the FGMRES algorithm. © 1997 by John Wiley & Sons, Ltd.     

Evaluation of the performance of inexact GMRES

The inexact GMRES algorithm is a variant of the GMRES algorithm where matrix-vector products are performed inexactly, either out of necessity or deliberately, as part of a trading of accuracy for speed. Recent studies have shown that relaxing matrix-vector products in this way can be justified theoretically and experimentally. Research, so far, has focused on decreasing the workload per iteration without significantly affecting the accuracy. But relaxing the accuracy per iteration is liable to increase the number of iterations, thereby increasing the overall runtime, which could potentially end up being greater than that of the exact GMRES if there were not enough savings in the matrix-vector products. In this paper, we assess the benefit of the inexact approach in terms of actual CPU time derived from realistic problems, and we provide cases that provide instructive insights into results affected by the build-up of the inexactness. Such information is of vital importance to practitioners who need to decide whether switching their workflow to the inexact approach is worth the effort and the risk that might come with it. Our assessment is drawn from extensive numerical experiments that gauge the effectiveness of the inexact scheme and its suitability for use in addressing certain problems, depending on how much inexactness is allowed in the matrix-vector products.