The Use of Refined Harmonic Shifts in the Implicitly Restarted Refined Harmonic Arnoldi Method

This paper proposes a new shift scheme, called refined harmonic shifts, for use in the implicitly restarted refined harmonic Arnoldi method. Numerical experiments show that the implicitly restarted refined harmonic Arnoldi algorithm with refined harmonic shifts is better than the implicitly restarted harmonic Arnoldi algorithm with Morgan's harmonic shifts and the refined harmonic shifts are as efficient as Jia's refined shifts.     

A VARIATION ON THE BLOCK ARNOLDIMETHOD FOR LARGE UNSYMMETRIC MATRIX EIGENPROBLEMS

1.IntroductionLarge-scalematrixeigenproblemsariseinappliedsciencesandmanyengineeringapplications.Arnoldi'smethod[1'2]anditsblockversion[3--6]areverypopularforsolvingthem.Thesemethodshavebeenintensivelyinvestigatedsincethe1980s,bothintheoryandinalgorithms;wereferto[7--17]fordetails.WhenmstepsoftheblockArnoldiprocessareperformed,anorthonormalbasis{K}7=1oftheblockKrylovsubspaceK.(VI,A)spannedbyVI5AVI,'IAm--1VIisgenerated,whereVIisaninitialNxporthogonalmatrix,andtherestrictionofAtoKm(V…     

Embedded techniques for choosing the parameter in Tikhonov regularization

This paper introduces a new strategy for setting the regularization parameter when solving large‐scale discrete ill‐posed linear problems by means of the Arnoldi–Tikhonov method. This new rule is essentially based on the discrepancy principle, although no initial knowledge of the norm of the error that affects the right‐hand side is assumed; an increasingly more accurate approximation of this quantity is recovered during the Arnoldi algorithm. Some theoretical estimates are derived in order to motivate our approach. Many numerical experiments performed on classical test problems as well as image deblurring problems are presented. Copyright © 2014 John Wiley & Sons, Ltd.     

IMPROVING EIGENVECTORS IN ARNOLDI'S METHOD

1. IntroductionArnoldi's method [1, 12] is used for computing.,a few selected eigenpairs of largeunsymmetric matrices. It hajs been investigated since the 1980s; see, e-g., [3--15].It is well known that the m--step Arnoldi processt as described in detail in Section 2,generates an orthonormal basis {yi}7=1 of the Krylov subspace Km(vi, A) spanned byvil Avi,... 5 Am--'v,. Here yi is an initial unit norm vector. The projected matrix ofA onto Km(vi, A) is represented by an m x m upper Hessenb…     

On Restarting the Arnoldi Method for Large Nonsymmetric Eigenvalue Problems

The Arnoldi method computes eigenvalues of large nonsymmetric matrices. Restarting is generally needed to reduce storage requirements and orthogonalization costs. However, restarting slows down the convergence and makes the choice of the new starting vector difficult if several eigenvalues are desired. We analyze several approaches to restarting and show why Sorensen's implicit QR approach is generally far superior to the others. Ritz vectors are combined in precisely the right way for an effective new starting vector. Also, a new method for restarting Arnoldi is presented. It is mathematically equivalent to the Sorensen approach but has additional uses.

     

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.     

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 rank‐exploiting infinite Arnoldi algorithm for nonlinear eigenvalue problems

We consider the nonlinear eigenvalue problem M(λ)x = 0, where M(λ) is a large parameter‐dependent matrix. In several applications, M(λ) has a structure where the higher‐order terms of its Taylor expansion have a particular low‐rank structure. We propose a new Arnoldi‐based algorithm that can exploit this structure. More precisely, the proposed algorithm is equivalent to Arnoldi's method applied to an operator whose reciprocal eigenvalues are solutions to the nonlinear eigenvalue problem. The iterates in the algorithm are functions represented in a particular structured vector‐valued polynomial basis similar to the construction in the infinite Arnoldi method [Jarlebring, Michiels, and Meerbergen, Numer. Math., 122 (2012), pp. 169–195]. In this paper, the low‐rank structure is exploited by applying an additional operator and by using a more compact representation of the functions. This reduces the computational cost associated with orthogonalization, as well as the required memory resources. The structure exploitation also provides a natural way in carrying out implicit restarting and locking without the need to impose structure in every restart. The efficiency and properties of the algorithm are illustrated with two large‐scale problems. Copyright © 2016 John Wiley & Sons, Ltd.     

A Convergence Result for Some Krylov–Tikhonov Methods in Hilbert Spaces

In this paper, we present a convergence result for some Krylov projection methods when applied to the Tikhonov minimization problem in its general form. In particular, we consider the method based on the Arnoldi algorithm and the one based on the Lanczos bidiagonalization process.     

An Arnoldi-type algorithm for computing page rank

We consider the problem of computing PageRank. The matrix involved is large and cannot be factored, and hence techniques based on matrix-vector products must be applied. A variant of the restarted refined Arnoldi method is proposed, which does not involve Ritz value computations. Numerical examples illustrate the performance and convergence behavior of the algorithm. AMS subject classification (2000) 65F15, 65C40     

解大型非对称特征问题的精化块不完全正交化算法

0引言 块Arnoldi方法~[5]是解大型非对称特征值问题的正交投影方法，然而Jia~[3]的分析表     

A rational Arnoldi process with applications

The rational Arnoldi process is a popular method for the computation of a few eigenvalues of a large non‐Hermitian matrix and for the approximation of matrix functions. The method is particularly attractive when the rational functions that determine the process have only few distinct poles , because then few factorizations of matrices of the form A ? z_jI have to be computed. We discuss recursion relations for orthogonal bases of rational Krylov subspaces determined by rational functions with few distinct poles. These recursion formulas yield a new implementation of the rational Arnoldi process. Applications of the rational Arnoldi process to the approximation of matrix functions as well as to the computation of eigenvalues and pseudospectra of A are described. The new implementation is compared to several available implementations.     

IRAM‐based method for eigenpairs and their derivatives of large matrix‐valued functions

Based on the implicitly restarted Arnoldi method for eigenpairs of large matrix, a new method is presented for the computation of a few eigenpairs and their derivatives of large matrix‐valued functions. Eigenpairs and their derivatives are calculated simultaneously. Equation systems that are solved for eigenvector derivatives are greatly reduced from the original matrix size. The left eigenvectors are not required. Hence, the computational cost is saved. The convergence theory of the proposed method is established. Finally, numerical experiments are given to illustrate the efficiency of the proposed method. Copyright © 2010 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.     

调和Arnoldi方法的一种变形

讨论求解大规模非对称矩阵内部特征问题的一种方法,与标准的调和A rnold i方法相比,该方法仍用调和R itz值作为特征值的近似,而在近似特征向量选取方面,我们充分利用A rnold i过程所提供的最末一个基向量的信息,在多1维K ry lov子空间中选取一个向量-称之为改进的调和R itz向量-作为所求的特征向量的近似.理论分析和数值试验均表明这种变形的调和A rnold i方法的可行性和有效性.     

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.     

An Implicitly Restarted Block Arnoldi Method in a Vector-Wise Fashion

In this paper, we develop an implicitly restarted block Arnoldi algorithm in a vector-wise fashion. The vector-wise construction greatly simplifies both the detection of necessary deflation and the actual deflation itself, so it is preferable to the block-wise construction. The numerical experiment shows that our algorithm is effective.     

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 Arnoldi-based methods for large scale discrete-time algebraic Riccati equations

In the present paper, we present block Arnoldi-based methods for the computation of low rank approximate solutions of large discrete-time algebraic Riccati equations (DARE). The proposed methods are projection methods onto block or extended block Krylov subspaces. We give new upper bounds for the norm of the error obtained by applying these block Arnoldi-based processes. We also introduce the Newton method combined with the block Arnoldi algorithm and present some numerical experiments with comparisons between these methods.     

Nested Lanczos: implicitly restarting an unsymmetric Lanczos algorithm

In this text, we present a generalization of the idea of the Implicitly Restarted Arnoldi method to the unsymmetric Lanczos algorithm, using the two-sided Gram-Schmidt process or using a full Lanczos tridiagonalization. The resulting implicitly restarted Lanczos method is called Nested Lanczos. Nested Lanczos can be combined with an implicit filter. It can also be used in case of breakdown and offers an alternative for look-ahead. This revised version was published online in August 2006 with corrections to the Cover Date.