Krylov subspace methods, biorthogonal polynomials and Padé-type approximants

It is shown that Krylov subspace methods for solving systems of linear equations can be based on formal biorthogonal polynomials and on Padé-type and Padé approximants. New algorithms for their implementation are derived. This revised version was published online in June 2006 with corrections to the Cover Date.     

A new family of global methods for linear systems with multiple right-hand sides

The global bi-conjugate gradient (Gl-BCG) method is an attractive matrix Krylov subspace method for solving nonsymmetric linear systems with multiple right-hand sides, but it often show irregular convergence behavior in many applications. In this paper, we present a new family of global A-biorthogonal methods by using short two-term recurrences and formal orthogonal polynomials, which contain the global bi-conjugate residual (Gl-BCR) algorithm and its improved version. Finally, numerical experiments illustrate that the proposed methods are highly competitive and often superior to originals.     

A new family of global methods for linear systems with multiple right-hand sides

The global bi-conjugate gradient (Gl-BCG) method is an attractive matrix Krylov subspace method for solving nonsymmetric linear systems with multiple right-hand sides, but it often show irregular convergence behavior in many applications. In this paper, we present a new family of global $A$-biorthogonal methods by using short two-term recurrences and formal orthogonal polynomials, which contain the global bi-conjugate residual (Gl-BCR) algorithm and its improved version. Finally, numerical experiments illustrate that the proposed methods are highly competitive and often superior to originals.     

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.     

Formal orthogonal polynomials and Hankel/Toeplitz duality

For classical polynomials orthogonal with respect to a positive measure supported on the real line, the moment matrix is Hankel and positive definite. The polynomials satisfy a three term recurrence relation. When the measure is supported on the complex unit circle, the moment matrix is positive definite and Toeplitz. Then they satisfy a coupled Szeg recurrence relation but also a three term recurrence relation. In this paper we study the generalization for formal polynomials orthogonal with respect to an arbitrary moment matrix and consider arbitrary Hankel and Toeplitz matrices as special cases. The relation with Padé approximation and with Krylov subspace iterative methods is also outlined.This research was supported by the National Fund for Scientific Research (NFWO), project Lanczos, grant #2.0042.93.     

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.     

Globally and superlinearly convergent inexact Newton–Krylov algorithms for solving nonsmooth equations

This paper presents some variants of the inexact Newton method for solving systems of nonlinear equations defined by locally Lipschitzian functions. These methods use variants of Newton's iteration in association with Krylov subspace methods for solving the Jacobian linear systems. Global convergence of the proposed algorithms is established under a nonmonotonic backtracking strategy. The local convergence based on the assumptions of semismoothness and BD‐regularity at the solution is characterized, and the way to choose an inexact forcing sequence that preserves the rapid convergence of the proposed methods is also indicated. Numerical examples are given to show the practical viability of these approaches. Copyright © 2009 John Wiley & Sons, Ltd.     

Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves

The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user‐defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix–vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.     

A Connection between Time Domain Model Order Reduction and Moment Matching

We investigate the time domain model order reduction (MOR) framework using general orthogonal polynomials by Jiang and Chen [4] and extend their idea by exploiting the structure of the corresponding linear system of equations. Identifying an equivalent Sylvester equation we show a connection to a rational Krylov subspace, and thus moment matching. This theoretical link between the MOR techniques is illustrated by one numerical example. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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 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.     

Approximation of the linear combination of $\varphi$-functions using the block shift-and-invert Krylov subspace method

In this paper, we develop an algorithm in which the block shift-and-invert Krylov subspace method can be employed for approximating the linear combination of the matrix exponential and related exponential-type functions. Such evaluation plays a major role in a class of numerical methods known as exponential integrators. We derive a low-dimensional matrix exponential to approximate the objective function based on the block shift-and-invert Krylov subspace methods. We obtain the error expansion of the approximation, and show that the variants of its first term can be used as reliable a posteriori error estimates and correctors. Numerical experiments illustrate that the error estimates are efficient and the proposed algorithm is worthy of further study.     

Analysis of the convergence of the minimal and the orthogonal residual methods

We consider two Krylov subspace methods for solving linear systems, which are the minimal residual method and the orthogonal residual method. These two methods are studied without referring to any particular implementations. By using the Petrov–Galerkin condition, we describe the residual norms of these two methods in terms of Krylov vectors, and the relationship between there two norms. We define the Ritz singular values, and prove that the convergence of these two methods is governed by the convergence of the Ritz singular values. AMS subject classification 65F10     

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     

An extension of the conjugate residual method to nonsymmetric linear systems

The Conjugate Gradient (CG) method and the Conjugate Residual (CR) method are Krylov subspace methods for solving symmetric (positive definite) linear systems. To solve nonsymmetric linear systems, the Bi-Conjugate Gradient (Bi-CG) method has been proposed as an extension of CG. Bi-CG has attractive short-term recurrences, and it is the basis for the successful variants such as Bi-CGSTAB. In this paper, we extend CR to nonsymmetric linear systems with the aim of finding an alternative basic solver. Numerical experiments show that the resulting algorithm with short-term recurrences often gives smoother convergence behavior than Bi-CG. Hence, it may take the place of Bi-CG for the successful variants.     

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.     

Numerical methods for A-optimal designs with a sparsity constraint for ill-posed inverse problems

We consider the problem of experimental design for linear ill-posed inverse problems. The minimization of the objective function in the classic A-optimal design is generalized to a Bayes risk minimization with a sparsity constraint. We present efficient algorithms for applications of such designs to large-scale problems. This is done by employing Krylov subspace methods for the solution of a subproblem required to obtain the experiment weights. The performance of the designs and algorithms is illustrated with a one-dimensional magnetotelluric example and an application to two-dimensional super-resolution reconstruction with MRI data.     

A New Matrix Approach For Solving Second-Order Linear Matrix Partial Differential Equations

The basic aim of this article is to present a novel efficient matrix approach for solving the second-order linear matrix partial differential equations (MPDEs) under given initial conditions. For imposing the given initial conditions to the main MPDEs, the associated matrix integro-differential equations (MIDEs) with partial derivatives are obtained from direct integration with regard to the spatial variable x and time variable t. Hence, operational matrices of differentiation and integration together with the completeness of Bernoulli polynomials are used to reduce the obtained MIDEs to the corresponding algebraic Sylvester equations. Using two well-known subspace Krylov iterative methods (i.e., GMRES(10) and Bi-CGSTAB) we provide two algorithms for solving the mentioned Sylvester equations. A numerical example is provided to show the efficiency and accuracy of the presented approach.

     

New look-ahead Lanczos-type algorithms for linear systems

Summary. A breakdown (due to a division by zero) can arise in the algorithms for implementing Lanczos' method because of the non-existence of some formal orthogonal polynomials or because the recurrence relationship used is not appropriate. Such a breakdown can be avoided by jumping over the polynomials involved. This strategy was already used in some algorithms such as the MRZ and its variants. In this paper, we propose new implementations of the recurrence relations of these algorithms which only need the storage of a fixed number of vectors, independent of the length of the jump. These new algorithms are based on Horner's rule and on a different way for computing the coefficients of the recurrence relationships. Moreover, these new algorithms seem to be more stable than the old ones and they provide better numerical results. Numerical examples and comparisons with other algorithms will be given. Received September 2, 1997 / Revised version received July 24, 1998     

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.