Skew-symmetric methods for nonsymmetric linear systems with multiple right-hand sides

By transforming nonsymmetric linear systems to the extended skew-symmetric ones, we present the skew-symmetric methods for solving nonsymmetric linear systems with multiple right-hand sides. These methods are based on the block and global Arnoldi algorithm which is formed by implementing orthogonal projections of the initial matrix residual onto a matrix Krylov subspace. The algorithms avoid the tediously long Arnoldi process and highly reduce expensive storage. Numerical experiments show that these algorithms are effective and give better practical performances than global GMRES for solving nonsymmetric linear systems with multiple right-hand sides.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

A generalized global Arnoldi method for ill-posed matrix equations

This paper discusses the solution of large-scale linear discrete ill-posed problems with a noise-contaminated right-hand side. Tikhonov regularization is used to reduce the influence of the noise on the computed approximate solution. We consider problems in which the coefficient matrix is the sum of Kronecker products of matrices and present a generalized global Arnoldi method, that respects the structure of the equation, for the solution of the regularized problem. Theoretical properties of the method are shown and applications to image deblurring are described.     

A rational Arnoldi approach for ill-conditioned linear systems

For the solution of full-rank ill-posed linear systems a new approach based on the Arnoldi algorithm is presented. Working with regularized systems, the method theoretically reconstructs the true solution by means of the computation of a suitable function of matrix. In this sense, the method can be referred to as an iterative refinement process. Numerical experiments arising from integral equations and interpolation theory are presented. Finally, the method is extended to work in connection with the standard Tikhonov regularization with the right-hand side contaminated by noise.     

Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems

Summary. The convergence rate of Krylov subspace methods for the solution of nonsymmetric systems of linear equations, such as GMRES or FOM, is studied. Bounds on the convergence rate are presented which are based on the smallest real part of the field of values of the coefficient matrix and of its inverse. Estimates for these quantities are available during the iteration from the underlying Arnoldi process. It is shown how these bounds can be used to study the convergence properties, in particular, the dependence on the mesh-size and on the size of the skew-symmetric part, for preconditioners for finite element discretizations of nonsymmetric elliptic boundary value problems. This is illustrated for the hierarchical basis and multilevel preconditioners which constitute popular preconditioning strategies for such problems. Received May 3, 1996     

Convergence acceleration of preconditioned conjugate gradient solver based on error vector sampling for a sequence of linear systems

In this article, we focus on solving a sequence of linear systems that have identical (or similar) coefficient matrices. For this type of problem, we investigate subspace correction (SC) and deflation methods, which use an auxiliary matrix (subspace) to accelerate the convergence of the iterative method. In practical simulations, these acceleration methods typically work well when the range of the auxiliary matrix contains eigenspaces corresponding to small eigenvalues of the coefficient matrix. We develop a new algebraic auxiliary matrix construction method based on error vector sampling in which eigenvectors with small eigenvalues are efficiently identified in the solution process. We use the generated auxiliary matrix for convergence acceleration in the following solution step. Numerical tests confirm that both SC and deflation methods with the auxiliary matrix can accelerate the solution process of the iterative solver. Furthermore, we examine the applicability of our technique to the estimation of the condition number of the coefficient matrix. We also present the algorithm of the preconditioned conjugate gradient method with condition number estimation.     

New GMRES(k)-Type Algorithms with Explicit Restarts and the Analysis of Their Convergence Properties Based on Matrix Relations in QR Form

The paper considers the problem of constructing a basic iterative scheme for solving systems of linear algebraic equations with unsymmetric and indefinite coefficient matrices. A new GMRES-type algorithm with explicit restarts is suggested. When restarting, this algorithm takes into account the spectral/singular data transferred using orthogonal matrix relations in the so-called QR form, which arise when performing inner iterations of Arnoldi type. The main idea of the algorithm developed is to organize inner iterations and the filtering of directions before restarting in such a way that, from one restart to another, matrix relations effectively accumulate information concerning the current approximate solution and, simultaneously, spectral/singular data, which allow the algorithm to converge with a rate comparable with that of the GMRES algorithm without restarts. Convergence theory is provided for the case of nonsingular, unsymmetric, and indefinite matrices. A bound for the rate of decrease of the residual in the course of inner Arnoldi-type iterations is obtained. This bound depends on the spectral/singular characterization of the subspace spanned by the directions retained upon filtering and is used in developing efficient filtering procedures. Numerical results are provided. Bibliography: 9 titles.     

A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations

Summary We present here a new hybrid method for the iterative solution of large sparse nonsymmetric systems of linear equations, say of the formAx=b, whereA ^{N, N} , withA nonsingular, andb ^N are given. This hybrid method begins with a limited number of steps of the Arnoldi method to obtain some information on the location of the spectrum ofA, and then switches to a Richardson iterative method based on Faber polynomials. For a polygonal domain, the Faber polynomials can be constructed recursively from the parameters in the Schwarz-Christoffel mapping function. In four specific numerical examples of non-normal matrices, we show that this hybrid algorithm converges quite well and is approximately as fast or faster than the hybrid GMRES or restarted versions of the GMRES algorithm. It is, however, sensitive (as other hybrid methods also are) to the amount of information on the spectrum ofA acquired during the first (Arnoldi) phase of this procedure.     

A framework of the harmonic Arnoldi method for evaluating <Emphasis Type="Italic">φ</Emphasis>-functions with applications to exponential integrators

In recent years, a great deal of attention has been focused on exponential integrators. The important ingredient to the implementation of exponential integrators is the efficient and accurate evaluation of the so called φ-functions on a given vector. The Krylov subspace method is an important technique for this problem. For this type of method, however, restarts become essential for the sake of storage requirements or due to computational complexities of evaluating matrix function on a reduced matrix of growing size. Another problem in computing φ-functions is the lack of a clear residual notion. The contribution of this work is threefold. First, we introduce a framework of the harmonic Arnoldi method for φ-functions, which is based on the residual and the oblique projection technique. Second, we establish the relationship between the harmonic Arnoldi approximation and the Arnoldi approximation, and compare the harmonic Arnoldi method and the Arnoldi method from a theoretical point of view. Third, we apply the thick-restarting strategy to the harmonic Arnoldi method, and propose a thick-restarted harmonic Arnoldi algorithm for evaluating φ-functions. An advantage of the new algorithm is that we can compute several φ-functions simultaneously in the same search subspace after restarting. The relationship between the error and the residual of the harmonic Arnoldi approximation is also investigated. Numerical experiments show the superiority of our new algorithm over many state-of-the-art algorithms for computing φ-functions.     

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.     

On the Krylov subspace methods based on tensor format for positive definite Sylvester tensor equations

This paper deals with studying some of well‐known iterative methods in their tensor forms to solve a Sylvester tensor equation. More precisely, the tensor form of the Arnoldi process and full orthogonalization method are derived by using a product between two tensors. Then tensor forms of the conjugate gradient and nested conjugate gradient algorithms are also presented. Rough estimation of the required number of operations for the tensor form of the Arnoldi process is obtained, which reveals the advantage of handling the algorithms based on tensor format over their classical forms in general. Some numerical experiments are examined, which confirm the feasibility and applicability of the proposed algorithms in practice. Copyright © 2016 John Wiley & Sons, Ltd.     

Non‐recursive solution of sparse block Hessenberg systems

A double‐phase algorithm, based on the block recursive LU decomposition, has been recently proposed to solve block Hessenberg systems with sparsity properties. In the first phase the information related to the factorization of A and required to solve the system, is computed and stored. The solution of the system is then computed in the second phase. In the present paper the algorithm is modified: the two phases are merged into a one‐phase version having the same computational cost and allowing a saving of storage. Moreover, the corresponding non‐recursive version of the new algorithm is presented, which is especially suitable to solve infinite systems where the coefficient matrix dimension is not a priori fixed and a subsequent size enlargement technique is used. A special version of the algorithm, well suited to deal with block Hessenberg matrices having also a block band structure, is presented. Theoretical asymptotic bounds on the computational costs are proved. They indicate that, under suitable sparsity conditions, the proposed algorithms outperform Gaussian elimination. Numerical experiments have been carried out, showing the effectiveness of the algorithms when the size of the system is of practical interest. Copyright © 2004 John Wiley & Sons, Ltd.     

Estimation of uTƒ(A)v for large‐scale unsymmetric matrices

Fast algorithms, based on the unsymmetric look‐ahead Lanczos and the Arnoldi process, are developed for the estimation of the functional Φ(?)= u ^T?(A) v for fixed u , v and A, where A∈??^n×n is a large‐scale unsymmetric matrix. Numerical results are presented which validate the comparable accuracy of both approaches. Although the Arnoldi process reaches convergence more quickly in some cases, it has greater memory requirements, and may not be suitable for especially large applications. Copyright © 2003 John Wiley & Sons, Ltd.     

An inexact shift‐and‐invert Arnoldi algorithm for Toeplitz matrix exponential

We revisit the shift‐and‐invert Arnoldi method proposed in [S. Lee, H. Pang, and H. Sun. Shift‐invert Arnoldi approximation to the Toeplitz matrix exponential, SIAM J. Sci. Comput., 32: 774–792, 2010] for numerical approximation to the product of Toeplitz matrix exponential with a vector. In this approach, one has to solve two large‐scale Toeplitz linear systems in advance. However, if the desired accuracy is high, the cost will be prohibitive. Therefore, it is interesting to investigate how to solve the Toeplitz systems inexactly in this method. The contribution of this paper is in three regards. First, we give a new stability analysis on the Gohberg–Semencul formula (GSF) and define the GSF condition number of a Toeplitz matrix. It is shown that when the size of the Toeplitz matrix is large, our result is sharper than the one given in [M. Gutknecht and M. Hochbruck. The stability of inversion formulas for Toeplitz matrices, Linear Algebra Appl., 223/224: 307–324, 1995]. Second, we establish a relation between the error of Toeplitz systems and the residual of Toeplitz matrix exponential. We show that if the GSF condition number of the Toeplitz matrix is medium‐sized, then the Toeplitz systems can be solved in a low accuracy. Third, based on this relationship, we present a practical stopping criterion for relaxing the accuracy of the Toeplitz systems and propose an inexact shift‐and‐invert Arnoldi algorithm for the Toeplitz matrix exponential problem. Numerical experiments illustrate the numerical behavior of the new algorithm and show the effectiveness of our theoretical results. Copyright © 2015 John Wiley & Sons, Ltd.     

A reflection on the implicitly restarted Arnoldi method for computing eigenvalues near a vertical line

In this article, we will study the link between a method for computing eigenvalues closest to the imaginary axis and the implicitly restarted Arnoldi method. The extension to computing eigenvalues closest to a vertical line is straightforward, by incorporating a shift. Without loss of generality we will restrict ourselves here to computing eigenvalues closest to the imaginary axis.In a recent publication, Meerbergen and Spence discussed a new approach for detecting purely imaginary eigenvalues corresponding to Hopf bifurcations, which is of interest for the stability of dynamical systems. The novel method is based on inverse iteration (inverse power method) applied on a Lyapunov-like eigenvalue problem. To reduce the computational overhead significantly a projection was added.This method can also be used for computing eigenvalues of a matrix pencil near a vertical line in the complex plane. We will prove in this paper that the combination of inverse iteration with the projection step is equivalent to Sorensen’s implicitly restarted Arnoldi method utilizing well-chosen shifts.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

Block Krylov Subspace Methods for Solving Large Sylvester Equations

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX–XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.     

Equilibrium attractivity of Krylov-W-methods for nonlinear stiff ODEs

Since implicit integration schemes for differential equations which use Krylov methods for the approximate solution of linear systems depend nonlinearly on the actual solution a classical stability analysis is difficult to perform. A different, weaker property of autonomous dissipative systemsy′=f(y) is that the norm ‖f(y(t))‖ decreases for any solutiony(t). This property can also be analysed for W-methods using a Krylov-Arnoldi approximation. We discuss different additional assumptions onf and conditions on the Arnoldi process that imply this kind of attractivity to equilibrium points for the numerical solution. One assumption is general enough to cover quasilinear parabolic problems. This work was supported by Deutsche Forschungsgemeinschaft.     

Computing the determinants of matrix Padé approximation

This paper is devoted to a computational problem of two special determinants which appear in the construction of generalized inverse matrix Padé approximants of type [n/2k] for the given power series with matrix coefficients. The main tools to be used are well-known Schur complement theorem and Arnoldi process for skew-symmetric systems.