Algorithms for the CMRH method for dense linear systems

The CMRH (Changing Minimal Residual method based on the Hessenberg process) method is a Krylov subspace method for solving large linear systems with non-symmetric coefficient matrices. CMRH generates a (non orthogonal) basis of the Krylov subspace through the Hessenberg process, and minimizes a quasi-residual norm. On dense matrices, the CMRH method is less expensive and requires less storage than other Krylov methods. In this work, we describe Matlab codes for the best of these implementations. Fortran codes for sequential and parallel implementations are also presented.     

A new implementation of the CMRH method for solving dense linear systems

The CMRH method [H. Sadok, Méthodes de projections pour les systèmes linéaires et non linéaires, Habilitation thesis, University of Lille1, Lille, France, 1994; H. Sadok, CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm, Numer. Algorithms 20 (1999) 303–321] is an algorithm for solving nonsymmetric linear systems in which the Arnoldi component of GMRES is replaced by the Hessenberg process, which generates Krylov basis vectors which are orthogonal to standard unit basis vectors rather than mutually orthogonal. The iterate is formed from these vectors by solving a small least squares problem involving a Hessenberg matrix. Like GMRES, this method requires one matrix–vector product per iteration. However, it can be implemented to require half as much arithmetic work and less storage. Moreover, numerical experiments show that this method performs accurately and reduces the residual about as fast as GMRES. With this new implementation, we show that the CMRH method is the only method with long-term recurrence which requires not storing at the same time the entire Krylov vectors basis and the original matrix as in the GMRES algorithm. A comparison with Gaussian elimination is provided.     

CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm

The Generalized Minimal Residual (GMRES) method and the Quasi-Minimal Residual (QMR) method are two Krylov methods for solving linear systems. The main difference between these methods is the generation of the basis vectors for the Krylov subspace. The GMRES method uses the Arnoldi process while QMR uses the Lanczos algorithm for constructing a basis of the Krylov subspace. In this paper we give a new method similar to QMR but based on the Hessenberg process instead of the Lanczos process. We call the new method the CMRH method. The CMRH method is less expensive and requires slightly less storage than GMRES. Numerical experiments suggest that it has behaviour similar to GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

A new look at CMRH and its relation to GMRES

CMRH is a Krylov subspace method which uses the Hessenberg process to produce a basis of a Krylov method, and minimizes a quasiresidual. This method produces convergence curves which are very close to those of GMRES, but using fewer operations and storage. In this paper we present new analysis which explains why CMRH has this good convergence behavior. Numerical examples illustrate the new bounds.     

The global Hessenberg and CMRH methods for linear systems with multiple right-hand sides

In this paper, we introduce two new methods for solving large sparse nonsymmetric linear systems with several right-hand sides. These methods are the global Hessenberg and global CMRH methods. Using the global Hessenberg process, these methods are less expensive than the global FOM and global GMRES methods [9]. Theoretical results about the new methods are given, and experimental results that show good performances of these new methods are presented.     

Krylov subspace methods of Hessenberg based for algebraic Riccati equation

In this paper, we propose a class of special Krylov subspace methods to solve continuous algebraic Riccati equation (CARE), i.e., the Hessenberg-based methods. The presented approaches can obtain efficiently the solution of algebraic Riccati equation to some extent. The main idea is to apply Kleinman-Newton"s method to transform the process of solving algebraic Riccati equation into Lyapunov equation at every inner iteration. Further, the Hessenberg process of pivoting strategy combined with Petrov-Galerkin condition and minimal norm condition is discussed for solving the Lyapunov equation in detail, then we get two methods, namely global generalized Hessenberg (GHESS) and changing minimal residual methods based on the Hessenberg process (CMRH) for solving CARE, respectively. Numerical experiments illustrate the efficiency of the provided methods.     

Necessary and sufficient conditions for GMRES complete and partial stagnation

In this paper we give necessary and sufficient conditions for the complete or partial stagnation of the GMRES iterative method for solving real linear systems. Our results rely on a paper by Arioli, Pták and Strakoš (1998), characterizing the matrices having a prescribed convergence curve for the residual norms. We show that we have complete stagnation if and only if the matrix A is orthonormally similar to an upper or lower Hessenberg matrix having a particular first row or column or a particular last row or column. Partial stagnation is characterized by a particular pattern of the matrix Q in the QR factorization of the upper Hessenberg matrix generated by the Arnoldi process.     

A method of congruent type for linear systems with conjugate-normal coefficient matrices

Minimal residual methods, such as MINRES and GMRES, are well-known iterative versions of direct procedures for reducing a matrix to special condensed forms. The method of reduction used in these procedures is a sequence of unitary similarity transformations, while the condensed form is a tridiagonal matrix (MINRES) or a Hessenberg matrix (GMRES). The algorithm CSYM proposed in the 1990s for solving systems with complex symmetric matrices was based on the tridiagonal reduction performed via unitary congruences rather than similarities. In this paper, we construct an extension of this algorithm to the entire class of conjugate-normal matrices. (Complex symmetric matrices are a part of this class.) Numerical results are presented. They show that, on many occasions, the proposed algorithm has a superior convergence rate compared to GMRES.     

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.     

Deflated GMRES for systems with multiple shifts and multiple right-hand sides

We consider solution of multiply shifted systems of nonsymmetric linear equations, possibly also with multiple right-hand sides. First, for a single right-hand side, the matrix is shifted by several multiples of the identity. Such problems arise in a number of applications, including lattice quantum chromodynamics where the matrices are complex and non-Hermitian. Some Krylov iterative methods such as GMRES and BiCGStab have been used to solve multiply shifted systems for about the cost of solving just one system. Restarted GMRES can be improved by deflating eigenvalues for matrices that have a few small eigenvalues. We show that a particular deflated method, GMRES-DR, can be applied to multiply shifted systems.In quantum chromodynamics, it is common to have multiple right-hand sides with multiple shifts for each right-hand side. We develop a method that efficiently solves the multiple right-hand sides by using a deflated version of GMRES and yet keeps costs for all of the multiply shifted systems close to those for one shift. An example is given showing this can be extremely effective with a quantum chromodynamics matrix.     

A simpler GMRES and its adaptive variant for shifted linear systems

A variant of the simpler GMRES method is developed for solving shifted linear systems (SGMRES‐Sh), exhibiting almost the same advantage of the simpler GMRES method over the regular GMRES method. Because the remedy adapted by GMRES‐Sh is no longer feasible for SGMRES‐Sh due to the differences between simpler GMRES and GMRES for constructing the residual vectors of linear systems, we take an alternative strategy to force the residual vectors of the add system also be orthogonal to the subspaces, to which the residual vectors of the seed system are orthogonal when the seed system is solved with the simpler GMRES method. In addition, a seed selection strategy is also employed for solving the rest non‐converged linear systems. Furthermore, an adaptive version of SGMRES‐Sh is presented for the purpose of improving the stability of SGMRES‐Sh based on the technique of the adaptive choice of the Krylov subspace basis developed for the adaptive simpler GMRES. Numerical experiments demonstrate the benefits of the presented methods.     

Conjugate gradient and minimal residual methods for solving symmetric indefinite systems

Norm-minimizing-type methods for solving large sparse linear systems with symmetric and indefinite coefficient matrices are considered. The Krylov subspace can be generated by either the Lanczos approach, such as the methods MINRES, GMRES and QMR, or by a conjugate-gradient approach. Here, we propose an algorithm based on the latter approach. Some relations among the search directions and the residuals, and how the search directions are related to the Krylov subspace are investigated. Numerical experiments are reported to verify the convergence properties.     

Imposing symmetry in augmented linear systems

This paper discusses the methods of imposing symmetry in the augmented system formulation (ASF) for least‐squares (LS) problems. A particular emphasis is on upper Hessenberg problems, where the challenge lies in leaving all zero‐by‐definition elements of the LS matrix unperturbed. Analytical solutions for optimal perturbation matrices are given, including upper Hessenberg matrices. Finally, the upper Hessenberg LS problems represented by unsymmetric ASF that indicate a normwise backward stability of the problem (which is not the case in general) are identified. It is observed that such problems normally arise from Arnoldi factorization (for example, in the generalized minimal residual (GMRES) algorithm). The problem is illustrated with a number of practical (arising in the GMRES algorithm) and some ‘purpose‐built’ examples. Copyright © 2014 John Wiley & Sons, Ltd.     

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.

     

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.     

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.     

Matrix Krylov subspace methods for linear systems with multiple right-hand sides

In this paper, we first give a result which links any global Krylov method for solving linear systems with several right-hand sides to the corresponding classical Krylov method. Then, we propose a general framework for matrix Krylov subspace methods for linear systems with multiple right-hand sides. Our approach use global projection techniques, it is based on the Global Generalized Hessenberg Process (GGHP) – which use the Frobenius scalar product and construct a basis of a matrix Krylov subspace – and on the use of a Galerkin or a minimizing norm condition. To accelerate the convergence of global methods, we will introduce weighted global methods. In these methods, the GGHP uses a different scalar product at each restart. Experimental results are presented to show the good performances of the weighted global methods. AMS subject classification 65F10     

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.     

A minimal residual method for linear polynomials in unitary matrices

A minimal residual method, called MINRES-N2, that is based on the use of unconventional Krylov subspaces was previously proposed by the authors for solving a system of linear equations Ax = b with a normal coefficient matrix whose spectrum belongs to an algebraic second-degree curve Γ. However, the computational scheme of this method does not cover matrices of the form A = αU + βI, where U is an arbitrary unitary matrix; for such matrices, Γ is a circle. Systems of this type are repeatedly solved when the eigenvectors of a unitary matrix are calculated by inverse iteration. In this paper, a modification of MINRES-N2 suitable for linear polynomials in unitary matrices is proposed. Numerical results are presented demonstrating the significant superiority of the modified method over GMRES as applied to systems of this class.     

Inexact Perturbed Newton Methods and Applications to a Class of Krylov Solvers

Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system (Ref. 1). The local convergence theory given by the authors of Ref. 1 and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals. We extend this local convergence theory to the general case, characterizing the rate of convergence in terms of the perturbations and residuals.The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton–Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton–Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method. At the end of the paper, the theoretical results are verified on some numerical examples.