Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones.     

Some theoretical comparisons of refined Ritz vectors and Ritz vectors

Refined projection methods proposed by the author have received attention internationally. We are concerned with a conventional projection method and its refined counterpart for computing approximations to a simple eigenpair (A, x) of a large matrix A. Given a subspace ω that contains an approximation to x, these two methods compute approximations (μ,x) and (μ,x) to (λ, x), respectively. We establish three results. First, the refined eigenvector approximation or simply the refined Ritz vector x is unique as the     

计算大规模矩阵最大最小奇异值和奇异向量的两个精化Lanczos算法

1.引言 在科学工程计算中经常需要计算大规模矩阵的少数最大或最小的奇异值及其所对应的奇异子空间。例如图像处理中要计算矩阵端部奇异值之比作为图像的分辨率,诸如此类的问题还存在于最小二乘问题、控制理论、量子化学中等等。然而大多实际问题中的矩阵是大型稀疏矩阵,且需要的是矩阵的部分奇异对。如果计算A的完全奇异值分解(SVD),则运算量和存储量极大,甚至不可能。因此必须寻求其它有效可靠的算法。 假设A的SVD为     

求解大规模非对称矩阵特征问题的精化双正交Lanczos算法

We combine Lanczos algorithm with the thought of the refined projection method using QR factorization and propose the refined biothogonalization Lanczos method for computing the desired eigenvalues of large unsymmetric matrix. With low cost of work space and flops the algorithm cures the disease that the Ritz vectors may not converge when the Ritz values converge usingthe Lanczos method. Numerical experiments show our algorithm is considerably more stable and efficient than its counterpart.     

On the convergence of Ritz pairs and refined Ritz vectors for quadratic eigenvalue problems

For a given subspace, the Rayleigh-Ritz method projects the large quadratic eigenvalue problem (QEP) onto it and produces a small sized dense QEP. Similar to the Rayleigh-Ritz method for the linear eigenvalue problem, the Rayleigh-Ritz method defines the Ritz values and the Ritz vectors of the QEP with respect to the projection subspace. We analyze the convergence of the method when the angle between the subspace and the desired eigenvector converges to zero. We prove that there is a Ritz value that converges to the desired eigenvalue unconditionally but the Ritz vector converges conditionally and may fail to converge. To remedy the drawback of possible non-convergence of the Ritz vector, we propose a refined Ritz vector that is mathematically different from the Ritz vector and is proved to converge unconditionally. We construct examples to illustrate our theory.     

Jacobi-Davidson方法中的修正方程和对应的精化方法

Jacobi-Davidson方法的核心之一是求解用以合理扩展投影子空间的线性修正方程组,众多文献均认为该方程是自然有解的.本文详细研究了修正方程,证明它可能无解,并给出了解存在的条件.同时,为克服近似特征向量的可能不收敛性,提出了精化的Jacobi-Davidson方法,建立了对应的修正方程.     

A refined iterative algorithm based on the block arnoldi process for large unsymmetric eigenproblems

When the matrix in question is unsymmetric, the approximate eigenvectors or Ritz vectors obtained by orthogonal projection methods including Arnoldi's method and the block Arnoldi method cannot be guaranteed to converge in theory even if the corresponding approximate eigenvalues or Ritz values do. In order to circumvent this danger, a new strategy has been proposed by the author for Arnoldi's method. The strategy used is generalized to the block Arnoldi method in this paper. It discards Ritz vectors and instead computes refined approximate eigenvectors by small-sized singular-value decompositions. It is proved that the new strategy can guarantee the convergence of refined approximate eigenvectors if the corresponding Ritz values do. The resulting refined iterative algorithm is realized by the block Arnoldi process. Numerical experiments show that the refined algorithm is much more efficient than the iterative block Arnoldi algorithm.     

Harmonic and refined Rayleigh–Ritz for the polynomial eigenvalue problem

After reviewing the harmonic Rayleigh–Ritz approach for the standard and generalized eigenvalue problem, we discuss several extraction processes for subspace methods for the polynomial eigenvalue problem. We generalize the harmonic and refined Rayleigh–Ritz approaches which lead to new approaches to extract promising approximate eigenpairs from a search space. We give theoretical as well as numerical results of the methods. In addition, we study the convergence of the Jacobi–Davidson method for polynomial eigenvalue problems with exact and inexact linear solves and discuss several algorithmic details. Copyright © 2008 John Wiley & Sons, Ltd.     

Some theoretical comparisons of refined Ritz vectors and Ritz vectors

Refined projection methods proposed by the author have received attention internationally. We are concerned with a conventional projection method and its refined counterpart for computing approximations to a simple eigenpair (λ, ϰ) of a large matrix A. Given a subspace W that contains an approximation to ϰ, these two methods compute approximations (μ\(\tilde x\)) and (μ\(\hat x\)) to (λ, ϰ), respectively. We establish three results. First, the refined eigenvector approximation or simply the refined Ritz vector \(\hat x\) is unique as the deviation of ϰ from W approaches zero if λ is simple. Second, in terms of residual norm of the refined approximate eigenpair (μ, \(\hat x\)), we derive lower and upper bounds for the sine of the angle between the Ritz vector \(\tilde x\) and the refined eigenvector approximation \(\hat x\), and we prove that \(\tilde x \ne \hat x\) unless \(\hat x = x\). Third, we establish relationships between the residual norm \(\left\| {A\tilde x - \mu \tilde x} \right\|\) of the conventional methods and the residual norm \(\left\| {A\hat x - \mu \hat x} \right\|\) of the refined methods, and we show that the latter is always smaller than the former if (μ, \(\hat x\)) is not an exact eigenpair of A, indicating that the refined projection method is superior to the corresponding conventional counterpart.

     

The convergence of harmonic Ritz values, harmonic Ritz vectors, and refined harmonic Ritz vectors

This paper concerns a harmonic projection method for computing an approximation to an eigenpair of a large matrix . Given a target point and a subspace that contains an approximation to , the harmonic projection method returns an approximation to . Three convergence results are established as the deviation of from approaches zero. First, the harmonic Ritz value converges to if a certain Rayleigh quotient matrix is uniformly nonsingular. Second, the harmonic Ritz vector converges to if the Rayleigh quotient matrix is uniformly nonsingular and remains well separated from the other harmonic Ritz values. Third, better error bounds for the convergence of are derived when converges. However, we show that the harmonic projection method can fail to find the desired eigenvalue --in other words, the method can miss if it is very close to . To this end, we propose to compute the Rayleigh quotient of with respect to and take it as a new approximate eigenvalue. is shown to converge to once tends to , no matter how is close to . Finally, we show that if the Rayleigh quotient matrix is uniformly nonsingular, then the refined harmonic Ritz vector, or more generally the refined eigenvector approximation introduced by the author, converges. We construct examples to illustrate our theory.

     

Ritz and harmonic Ritz values and the convergence of FOM and GMRES

The Ritz and harmonic Ritz values are approximate eigenvalues, which can be computed cheaply within the FOM and GMRES Krylov subspace iterative methods for solving non‐symmetric linear systems. They are also the zeros of the residual polynomials of FOM and GMRES, respectively. In this paper we show that the Walker–Zhou interpretation of GMRES enables us to formulate the relation between the harmonic Ritz values and GMRES in the same way as the relation between the Ritz values and FOM. We present an upper bound for the norm of the difference between the matrices from which the Ritz and harmonic Ritz values are computed. The differences between the Ritz and harmonic Ritz values enable us to describe the breakdown of FOM and stagnation of GMRES. Copyright © 1999 John Wiley & Sons, Ltd.     

A QUASI-REFINED ITERATIVE ALGORITHM BASED ON THE LANCZOS BIORTHOGONALIZATION PROCEDURE FOR LARGE EIGENPROBLEMS

The two-sided Lanczos method is popular for computing a few selected eigentriplets of large non-Hermitian matrices. However, it has been revealed that theRitz vectors gained by this method may not converge even if the subspaces are good enough and the associated eigenvalues converge. In order to remedy this drawback, a novel method is proposed which is based on the refined strategy, the quasi-refined ideaand the Lanczos biothogonalization procedure, the resulting algorithm is presented. Therelationship between the new method and the classical oblique projection technique isalso established. We report some numericalwith the conventional one, the results showthe latter.experiments and compare the new algorithmthat the former is often more powerful than     

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…     

Generalized block Lanczos methods for large unsymmetric eigenproblems

Generalized block Lanczos methods for large unsymmetric eigenproblems are presented, which contain the block Arnoldi method, and the block Arnoldi algorithms are developed. The convergence of this class of methods is analyzed when the matrix A is diagonalizable. Upper bounds for the distances between normalized eigenvectors and a block Krylov subspace are derived, and a priori theoretical error bounds for Ritz elements are established. Compared with generalized Lanczos methods, which contain Arnoldi's method, the convergence analysis shows that the block versions have two advantages: First, they may be efficient for computing clustered eigenvalues; second, they are able to solve multiple eigenproblems. However, a deep analysis exposes that the approximate eigenvectors or Ritz vectors obtained by general orthogonal projection methods including generalized block methods may fail to converge theoretically for a general unsymmetric matrix A even if corresponding approximate eigenvalues or Ritz values do, since the convergence of Ritz vectors needs more sufficient conditions, which may be impossible to satisfy theoretically, than that of Ritz values does. The issues of how to restart and to solve multiple eigenproblems are addressed, and some numerical examples are reported to confirm the theoretical analysis. Received July 7, 1994 / Revised version received March 1, 1997     

SOLVING SYMMETRIC MONOTONE LINEAR VARIATIONAL INEQUALITIES BY SOME MODIFIED LEVITIN-POLYAK PROJECTION METHODS

Some modified Levitin-Polyak projection methods are proposed in this paper for solving monotone linear variational inequality x∈Ω，（x′-x)^T(Hx c)≤0，for any x′∈Ω.It is pointed out that there are similar methods for solving a general linear variational inequality.     

A-posteriori residual bounds for Arnoldi’s methods for nonsymmetric eigenvalue problems

Convergence of the implicitly restarted Arnoldi (IRA) method for nonsymmetric eigenvalue problems has often been studied by deriving bounds for the angle between a desired eigenvector and the Krylov projection subspace. Bounds for residual norms of approximate eigenvectors have been less studied and this paper derives a new a-posteriori residual bound for nonsymmetric matrices with simple eigenvalues. The residual vector is shown to be a linear combination of exact eigenvectors and a residual bound is obtained as the sum of the magnitudes of the coefficients of the eigenvectors. We numerically illustrate that the convergence of the residual norm to zero is governed by a scalar term, namely the last element of the wanted eigenvector of the projected matrix. Both cases of convergence and non-convergence are illustrated and this validates our theoretical results. We derive an analogous result for implicitly restarted refined Arnoldi (IRRA) and for this algorithm, we numerically illustrate that convergence is governed by two scalar terms appearing in the linear combination which drives the residual norm to zero. We provide a set of numerical results that validate the residual bounds for both variants of Arnoldi methods.     

L p -dual Quermassintegral sums

In this paper, we first introduce a concept of L _p -dual Quermassintegral sum function of convex bodies and establish the polar projection Minkowski inequality and the polar projection Aleksandrov-Fenchel inequality for L _p -dual Quermassintegral sums. Moreover, by using Lutwak’s width-integral of index i, we establish the L _p -Brunn-Minkowski inequality for the polar mixed projection bodies. As applications, we prove some interrelated results. This work was partially supported by the National Natural Science Foundation of China (Grant No. 10271071), Zhejiang Provincial Natural Science Foundation of China (Grant No. Y605065) and Foundation of the Education Department of Zhejiang Province of China (Grant No. 20050392)     

On IGMRES: An incomplete generalized minimal residual method for large unsymmetric linear systems

The truncated version of the generalized minimal residual method (GMRES), the incomplete generalized minimal residual method (IGMRES), is studied. It is based on an incomplete orthogonalization of the Krylov vectors in question, and gives an approximate or quasi-minimum residual solution over the Krylov subspace. A convergence analysis of this method is given, showing that in the non-restarted version IGMRES can behave like GMRES once the basis vectors of Krylov subspace generated by the incomplete orthogonalization are strongly linearly independent. Meanwhile, some relationships between the residual norms for IOM and IGMRES are established. Numerical experiments are reported to show convergence behavior of IGMRES and of its restarted version IGMRES(m). Project supported by the China State Key Basic Researches, the National Natural Science Foundation of China (Grant No. 19571014), the Doctoral Program (97014113), the Foundation of Returning Scholars of China and the Natural Science Foundation of Liaoning Province.     

Discrete time mean-variance analysis with singular second moment matrixes and an exogenous liability

We apply the dynamic programming methods to compute the analytical solution of the dynamic mean-variance optimization problem affected by an exogenous liability in a multi-periods market model with singular second moment matrixes of the return vector of assets. We use orthogonai transformations to overcome the difficulty produced by those singular matrixes, and the analytical form of the efficient frontier is obtained. As an application, the explicit form of the optimal mean-variance hedging strategy is also obtained for our model.     

Restarted generalized Krylov subspace methods for solving large-scale polynomial eigenvalue problems

In this paper, we introduce a generalized Krylov subspace based on a square matrix sequence {A _j } and a vector sequence {u _j }. Next we present a generalized Arnoldi procedure for generating an orthonormal basis of . By applying the projection and the refined technique, we derive a restarted generalized Arnoldi method and a restarted refined generalized Arnoldi method for solving a large-scale polynomial eigenvalue problem (PEP). These two methods are applied to solve the PEP directly. Hence they preserve essential structures and properties of the PEP. Furthermore, restarting reduces the storage requirements. Some theoretical results are presented. Numerical tests report the effectiveness of these methods. Yimin Wei is supported by the National Natural Science Foundation of China and Shanghai Education Committee.