A parallel implementation of the CMRH method for dense linear systems

This paper presents an implementation of the CMRH (Changing Minimal Residual method based on the Hessenberg process) iterative method suitable for parallel architectures. CMRH is an alternative to GMRES and QMR, the well-known Krylov methods for solving linear systems with non-symmetric coefficient matrices. CMRH generates a (non orthogonal) basis of the Krylov subspace through the Hessenberg process. On dense matrices, it requires less storage than GMRES. Parallel numerical experiments on a distributed memory computer with up to 16 processors are shown on some applications related to the solution of dense linear systems of equations. A comparison with the GMRES method is also provided on those test examples.     

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.     

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.     

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.     

Using implicitly filtered RKS for generalised eigenvalue problems

The rational Krylov sequence (RKS) method can be seen as a generalisation of Arnoldi's method. It projects a matrix pencil onto a smaller subspace; this projection results in a small upper Hessenberg pencil. As for the Arnoldi method, RKS can be restarted implicitly, using the QR decomposition of a Hessenberg matrix. This restart comes with a projection of the subspace using a rational function. In this paper, it is shown how the restart can be worked out in practice. In a second part, it is shown when the filtering of the subspace basis can fail and how this failure can be handled by deflating a converged eigenvector from the subspace, using a Schur-decomposition.     

Rational Krylov sequence methods for eigenvalue computation

Algorithms to solve large sparse eigenvalue problems are considered. A new class of algorithms which is based on rational functions of the matrix is described. The Lanczos method, the Arnoldi method, the spectral transformation Lanczos method, and Rayleigh quotient iteration all are special cases, but there are also new algorithms which correspond to rational functions with several poles. In the simplest case a basis of a rational Krylov subspace is found in which the matrix eigenvalue problem is formulated as a linear matrix pencil with a pair of Hessenberg matrices.     

Extended Hamiltonian Hessenberg Matrices arise in Projection based Model Order Reduction

We show that extended Hamiltonian Hessenberg matrices arise naturally in projection-based model order reduction. Therefore we reduce a large dynamical system by projecting it on an extended Krylov subspace. The eigenvalues of the reduced order model can then be computed directly by applying the extended Hamiltonian QR algorithm. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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     

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.     

A REVERSE ORDER IMPLICIT Q-THEOREM AND THE ARNOLDI PROCESS

Let A be a real square matrix and VTAV = G be an upper Hessenberg matrix with positive subdiagonal entries, where V is an orthogonal matrix. Then the implicit Q-theorem states that once the first column of V is given then V and G are uniquely determined. In this paper, three results are established. First, it holds a reverse order implicit Q-theorem: once the last column of V is given, then V and G are uniquely determined too. Second, it is proved that for a Krylov subspace two formulations of the Arnoldi process are equivalent and in one to one correspondence. Finally, by the equivalence relation and the reverse order implicit Q-theorem, it is proved that for the Krylov subspace, if the last vector of vector sequence generated by the Arnoldi process is given, then the vector sequence and resulting Hessenberg matrix are uniquely determined.     

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.     

Fast preconditioned iterative methods for finite volume discretization of steady-state space-fractional diffusion equations

We consider the preconditioned Krylov subspace method for linear systems arising from the finite volume discretization method of steady-state variable-coefficient conservative space-fractional diffusion equations. We propose to use a scaled-circulant preconditioner to deal with such Toeplitz-like discretization matrices. We show that the difference between the scaled-circulant preconditioner and the coefficient matrix is equal to the sum of a small-norm matrix and a low-rank matrix. Numerical tests are conducted to show the effectiveness of the proposed method for one- and two-dimensional steady-state space-fractional diffusion equations and demonstrate that the preconditioned Krylov subspace method converges very quickly.     

Roundoff error analysis of algorithms based on Krylov subspace methods

We study the roundoff error propagation in an algorithm which computes the orthonormal basis of a Krylov subspace with Householder orthonormal matrices. Moreover, we analyze special implementations of the classical GMRES algorithm, and of the Full Orthogonalization Method. These techniques approximate the solution of a large sparse linear system of equations on a sequence of Krylov subspaces of small dimension. The roundoff error analyses show upper bounds for the error affecting the computed approximated solutions.This work was carried out with the financial contribution of the Human Capital and Mobility Programme of the European Union grant ERB4050PL921378.     

Respectively scaled HSS iteration methods for solving discretized spatial fractional diffusion equations

For the discrete linear systems resulted from the discretization of the one‐dimensional anisotropic spatial fractional diffusion equations of variable coefficients with the shifted finite‐difference formulas of the Grünwald–Letnikov type, we propose a class of respectively scaled Hermitian and skew‐Hermitian splitting iteration method and establish its asymptotic convergence theory. The corresponding induced matrix splitting preconditioner, through further replacements of the involved Toeplitz matrices with certain circulant matrices, leads to an economic variant that can be executed by fast Fourier transforms. Both theoretical analysis and numerical implementations show that this fast respectively scaled Hermitian and skew‐Hermitian splitting preconditioner can significantly improve the computational efficiency of the Krylov subspace iteration methods employed as effective linear solvers for the target discrete linear systems.     

Flexible and multi‐shift induced dimension reduction algorithms for solving large sparse linear systems

We give two generalizations of the induced dimension reduction (IDR) approach for the solution of linear systems. We derive a flexible and a multi‐shift quasi‐minimal residual IDR variant. These variants are based on a generalized Hessenberg decomposition. We present a new, more stable way to compute basis vectors in IDR. Numerical examples are presented to show the effectiveness of these new IDR variants and the new basis compared with existing ones and to other Krylov subspace methods. Copyright © 2014 John Wiley & Sons, Ltd.     

Compress‐and‐restart block Krylov subspace methods for Sylvester matrix equations

Block Krylov subspace methods (KSMs) comprise building blocks in many state‐of‐the‐art solvers for large‐scale matrix equations as they arise, for example, from the discretization of partial differential equations. While extended and rational block Krylov subspace methods provide a major reduction in iteration counts over polynomial block KSMs, they also require reliable solvers for the coefficient matrices, and these solvers are often iterative methods themselves. It is not hard to devise scenarios in which the available memory, and consequently the dimension of the Krylov subspace, is limited. In such scenarios for linear systems and eigenvalue problems, restarting is a well‐explored technique for mitigating memory constraints. In this work, such restarting techniques are applied to polynomial KSMs for matrix equations with a compression step to control the growing rank of the residual. An error analysis is also performed, leading to heuristics for dynamically adjusting the basis size in each restart cycle. A panel of numerical experiments demonstrates the effectiveness of the new method with respect to extended block KSMs.     

Rational approximation to trigonometric operators

We consider the approximation of trigonometric operator functions that arise in the numerical solution of wave equations by trigonometric integrators. It is well known that Krylov subspace methods for matrix functions without exponential decay show superlinear convergence behavior if the number of steps is larger than the norm of the operator. Thus, Krylov approximations may fail to converge for unbounded operators. In this paper, we propose and analyze a rational Krylov subspace method which converges not only for finite element or finite difference approximations to differential operators but even for abstract, unbounded operators. In contrast to standard Krylov methods, the convergence will be independent of the norm of the operator and thus of its spatial discretization. We will discuss efficient implementations for finite element discretizations and illustrate our analysis with numerical experiments. AMS subject classification (2000)  65F10, 65L60, 65M60, 65N22     

Product-type skew-Hermitian triangular splitting iteration methods for strongly non-Hermitian positive definite linear systems

By further generalizing the modified skew-Hermitian triangular splitting iteration methods studied in [L. Wang, Z.-Z. Bai, Skew-Hermitian triangular splitting iteration methods for non-Hermitian positive definite linear systems of strong skew-Hermitian parts, BIT Numer. Math. 44 (2004) 363-386], in this paper, we present a new iteration scheme, called the product-type skew-Hermitian triangular splitting iteration method, for solving the strongly non-Hermitian systems of linear equations with positive definite coefficient matrices. We discuss the convergence property and the optimal parameters of this method. Moreover, when it is applied to precondition the Krylov subspace methods, the preconditioning property of the product-type skew-Hermitian triangular splitting iteration is analyzed in detail. Numerical results show that the product-type skew-Hermitian triangular splitting iteration method can produce high-quality preconditioners for the Krylov subspace methods for solving large sparse positive definite systems of linear equations of strong skew-Hermitian parts.     

Functions of a matrix and Krylov matrices

For a given nonderogatory matrix A, formulas are given for functions of A in terms of Krylov matrices of A. Relations between the coefficients of a polynomial of A and the generating vector of a Krylov matrix of A are provided. With the formulas, linear transformations between Krylov matrices and functions of A are introduced, and associated algebraic properties are derived. Hessenberg reduction forms are revisited equipped with appropriate inner products and related properties and matrix factorizations are given.