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.     

On a novel mode-solver and beam propagation method based on Galerkin approach and Arnoldi iteration technique

In this work, a modified Galerkin method is used to study the modal and propagation behaviour of generic integrated optical structures. The paraxial propagation equation is solved through non-linear mapping of the transverse plane and subsequent Galerkin approach. The differential equation is thus transformed into a specific finite-dimension linear problem. The field evolution is then calculated step-wise by approximating the exponential propagator through an Arnoldi iterative procedure. A similar approach is applied to the corresponding eigenproblem.     

Arnoldi-Riccati method for large eigenvalue problems

This paper describes a method for computing the dominant/right-most eigenvalues of large matrices. The method consists of refining the approximate eigenelements of a large matrix obtained by classical methods such as Arnoldi. The refinement process leads to a Riccati equation to be solved approximately. Numerical evidence of the improvements achieved by using the proposed approach is reported.Part of this work was done while visiting CERFACS (France) in Sept–Oct 1995 under contract HCM # ERBCHRXCT930420.     

Updating the QR decomposition of block tridiagonal and block Hessenberg matrices

We present an efficient block-wise update scheme for the QR decomposition of block tridiagonal and block Hessenberg matrices. For example, such matrices come up in generalizations of the Krylov space solvers MinRes, SymmLQ, GMRes, and QMR to block methods for linear systems of equations with multiple right-hand sides. In the non-block case it is very efficient (and, in fact, standard) to use Givens rotations for these QR decompositions. Normally, the same approach is also used with column-wise updates in the block case. However, we show that, even for small block sizes, block-wise updates using (in general, complex) Householder reflections instead of Givens rotations are far more efficient in this case, in particular if the unitary transformations that incorporate the reflections determined by a whole block are computed explicitly. Naturally, the bigger the block size the bigger the savings. We discuss the somewhat complicated algorithmic details of this block-wise update, and present numerical experiments on accuracy and timing for the various options (Givens vs. Householder, block-wise vs. column-wise update, explicit vs. implicit computation of unitary transformations). Our treatment allows variable block sizes and can be adapted to block Hessenberg matrices that do not have the special structure encountered in the above mentioned block Krylov space solvers.     

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     

Implicitly restarted Arnoldi with purification for the shift-invert transformation

The need to determine a few eigenvalues of a large sparse generalised eigenvalue problem with positive semidefinite arises in many physical situations, for example, in a stability analysis of the discretised Navier-Stokes equation. A common technique is to apply Arnoldi's method to the shift-invert transformation, but this can suffer from numerical instabilities as is illustrated by a numerical example. In this paper, a new method that avoids instabilities is presented which is based on applying the implicitly restarted Arnoldi method with the semi-inner product and a purification step. The paper contains a rounding error analysis and ends with brief comments on some extensions.

     

The power and Arnoldi methods in an algebra of circulants

Circulant matrices play a central role in a recently proposed formulation of three‐way data computations. In this setting, a three‐way table corresponds to a matrix where each ‘scalar’ is a vector of parameters defining a circulant. This interpretation provides many generalizations of results from matrix or vector‐space algebra. These results and algorithms are closely related to standard decoupling techniques on block‐circulant matrices using the fast Fourier transform. We derive the power and Arnoldi methods in this algebra. In the course of our derivation, we define inner products, norms, and other notions. These extensions are straightforward in an algebraic sense, but the implications are dramatically different from the standard matrix case. For example, the number of eigenpairs may exceed the dimension of the matrix, although it is still polynomial in it. It is thus necessary to take an extra step and carefully select a smaller, canonical set of size equal to the dimension of the matrix from which all possible eigenpairs can be formed. Copyright © 2012 John Wiley & Sons, Ltd.     

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 restarted Krylov method with inexact inversions

In this paper, we present a new type of restarted Krylov method for calculating the smallest eigenvalues of a symmetric positive definite matrix G. The new framework avoids the Lanczos tridiagonalization process and the use of polynomial filtering. This simplifies the restarting mechanism and allows the introduction of several modifications. Convergence is assured by a monotonicity property that pushes the eigenvalues toward their limits. Another innovation is the use of inexact inversions of G to generate the Krylov matrices. In this approach, the inverse of G is approximated by using an iterative method to solve the related linear system. Numerical experiments illustrate the usefulness of the proposed approach.     

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.