Finding the Maximal Eigenpair for a Large,Dense,Symmetric Matrix based on Mufa Chen's Algorithm

A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require only the maximal one.In a series of papers,efficient algorithms have been developed by Mufa Chen for computing the maximal eigenpairs of tridiagonal matrices with positive off-diagonal elements.The key idea is to explicitly construet effective initial guess of the maximal eigenpair and then to employ a self-closed iterative algorithm.In this paper we will extend Mufa Chen's algorithm to find maximal eigenpair for a large scale,dense,symmetric matrix.Our strategy is to first convert the underlying matrix into the tridiagonal form by using similarity transformations.We then handle the cases that prevent us from applying Chen's algorithm directly,e.g.,the cases with zero or negative super-or sub-diagonal elements.Serval numerical experiments are carried out to demonstrate the efficiency of the proposed hybrid method.     

Improved global algorithms for maximal eigenpair

This paper is a continuation of our previous paper [Front. Math. China, 2017, 12(5): 1023{1043] where global algorithms for computing the maximal eigenpair were introduced in a rather general setup. The efficiency of the global algorithms is improved in this paper in terms of a good use of power iteration and two quasi-symmetric techniques. Finally, the new algorithms are applied to Hua's economic optimization model.     

Efficient initials for computing maximal eigenpair

This paper introduces some efficient initials for a well-known algorithm (an inverse iteration) for computing the maximal eigenpair of a class of real matrices. The initials not only avoid the collapse of the algorithm but are also unexpectedly efficient. The initials presented here are based on our analytic estimates of the maximal eigenvalue and a mimic of its eigenvector for many years of accumulation in the study of stochastic stability speed. In parallel, the same problem for computing the next to the maximal eigenpair is also studied.     

由三个特征对构造正定Jacobi矩阵

本文研究了由三个特征对构造正定Jacobi矩阵的问题,给出了这个问题有唯一解的充要条件及解的表达式,并给出了问题的数值算法.     

A convergence analysis of the inexact Rayleigh quotient iteration and simplified Jacobi-Davidson method for the large Hermitian matrix eigenproblem

The inexact Rayleigh quotient iteration (RQI) is used for computing the smallest eigenpair of a large Hermitian matrix. Under certain condition, the method was proved to converge quadratically in literature. However, it is shown in this paper that under the original given condition the inexact RQI may not quadratically converge to the desired eigenpair and even may misconverge to some other undesired eigenpair. A new condition, called the uniform positiveness condition, is given that can fix misconvergence problem and ensure the quadratic convergence of the inexact RQI. An alternative to the inexact RQI is the Jacobi-Davidson (JD) method without subspace acceleration. A new proof of its linear convergence is presented and a sharper bound is established in the paper. All the results are verified and analyzed by numerical experiments. This work was supported by the National Natural Science Foundation of China (Grant Nos. 10471074, 10771116) and the Doctoral Program of the Ministry of Education of China (Grant No. 20060003003)     

Superlinear convergence rates for the Lanczos method applied to elliptic operators

Summary. This paper investigates the convergence of the Lanczos method for computing the smallest eigenpair of a selfadjoint elliptic differential operator via inverse iteration (without shifts). Superlinear convergence rates are established, and their sharpness is investigated for a simple model problem. These results are illustrated numerically for a more difficult problem. Received March 8, 1996     

A new iterative method for many eigenpair partial derivatives

A new iterative method is proposed for computing partial derivatives of many eigenpairs. This method simultaneously computes a few eigenpair partial derivatives. For each origin shift, partial derivatives of eigenpairs whose eigenvalues are closest to the origin shift can be computed. Hence, this method may be used for partial derivatives of all eigenpairs. Convergence of the proposed method is established. Finally numerical experiments are given to show the effectiveness of the proposed method.     

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     

Shifted power method for computing tensor H‐eigenpairs

In this paper, we propose a shifted symmetric higher‐order power method for computing the H‐eigenpairs of a real symmetric even‐order tensor. The local convergence of the method is proved. In addition, by utilizing the fixed‐point analysis, we can characterize exactly which H‐eigenpairs can be found and which cannot be found by the method. Numerical examples are presented to illustrate the performance of the method. Copyright © 2016 John Wiley & Sons, Ltd.     

Subspace correction multi‐level methods for elliptic eigenvalue problems

In this work, we apply the ideas of domain decomposition and multi‐grid methods to PDE‐based eigenvalue problems represented in two equivalent variational formulations. To find the lowest eigenpair, we use a “subspace correction” framework for deriving the multiplicative algorithm for minimizing the Rayleigh quotient of the current iteration. By considering an equivalent minimization formulation proposed by Mathew and Reddy, we can use the theory of multiplicative Schwarz algorithms for non‐linear optimization developed by Tai and Espedal to analyse the convergence properties of the proposed algorithm. We discuss the application of the multiplicative algorithm to the problem of simultaneous computation of several eigenfunctions also formulated in a variational form. Numerical results are presented. Copyright © 2001 John Wiley & Sons, Ltd.     

An algorithm for solving the eigenvalue problem for a class of operator pencils

We study the generalized eigenvalue problem for a uniformly hyperbolic or totally hyperbolic polynomial operator pencil of arbitrary order. In the context of the variational approach to the problem of determining the eigenvalues of such pencils we propose and justify a recursive algorithm for finding an eigenpair. To accelerate the convergence we propose using the Rayleigh-Ritz procedure. We give data from a numerical implementation of the algorithm. Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, No. 37, 1994, pp. 24–28.     

Computation of eigenpair partial derivatives by Rayleigh–Ritz procedure

Based on Rayleigh–Ritz procedure, a new method is proposed for a few eigenpair partial derivatives of large matrices. This method simultaneously computes the approximate eigenpairs and their partial derivatives. The linear systems of equations that are solved for eigenvector partial derivatives are greatly reduced from the original matrix size. And the left eigenvectors are not required. Moreover, errors of the computed eigenpairs and their partial derivatives are investigated. Hausdorff distance and containment gap are used to measure the accuracy of approximate eigenpair partial derivatives. Error bounds on the computed eigenpairs and their partial derivatives are derived. Finally numerical experiments are reported to show the efficiency of the proposed method.     

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.

     

An accurate a posteriori error estimator for the Steklov eigenvalue problem and its applications

In this paper, a type of accurate a posteriori error estimator is proposed for the Steklov eigenvalue problem based on the complementary approach, which provides an asymptotic exact estimate for the approximate eigenpair. Besides, we design a type of cascadic adaptive finite element method for the Steklov eigenvalue problem based on the proposed a posteriori error estimator. In this new cascadic adaptive scheme, instead of solving the Steklov eigenvalue problem in each adaptive space directly, we only need to do some smoothing steps for linearized boundary value problems on a series of adaptive spaces and solve some Steklov eigenvalue problems on a low dimensional space. Furthermore, the proposed a posteriori error estimator provides the way to refine mesh and control the number of smoothing steps for the cascadic adaptive method. Some numerical examples are presented to validate the efficiency of the algorithm in this paper.

     

Parallel Jacobi–Davidson with block FSAI preconditioning and controlled inner iterations

The Jacobi–Davidson (JD) algorithm is considered one of the most efficient eigensolvers currently available for non‐Hermitian problems. It can be viewed as a coupled inner‐outer iteration, where the inner one expands the search subspace and the outer one reduces the eigenpair residual. One of the difficulties in the JD efficient use stems from the definition of the most appropriate inner tolerance, so as to avoid useless extra work and keep the number of outer iterations under control. To this aim, the use of an efficient preconditioner for the inner iterative solver is of paramount importance. The present paper describes a fresh implementation of the JD algorithm with controlled inner iterations and block factorized sparse approximate inverse preconditioning for non‐Hermitian eigenproblems in a parallel computational environment. The algorithm performance is investigated by comparison with a freely available software package such as SLEPc. The results show that combining the inner tolerance control with an efficient preconditioning technique can allow for a significant improvement of the JD performance, preserving a good scalability. Copyright © 2016 John Wiley & Sons, Ltd.     

Steklov eigenvalue problem and its applications An accurate a posteriori error estimator for the

In this paper, a type of accurate a posteriori error estimator is proposed for the Steklov eigenvalue problem based on the complementary approach, which provides an asymptotic exact estimate for the approximate eigenpair. Besides, we design a type of cascadic adaptive finite element method for the Steklov eigenvalue problem based on the proposed a posteriori error estimator. In this new cascadic adaptive scheme, instead of solving the Steklov eigenvalue problem in each adaptive space directly, we only need to do some smoothing steps for linearized boundary value problems on a series of adaptive spaces and solve some Steklov eigenvalue problems on a low dimensional space. Furthermore, the proposed a posteriori error estimator provides the way to refine meshes and control the number of smoothing steps for the cascadic adaptive method. Some numerical examples are presented to validate the efficiency of the algorithm in this paper.     

A posteriori error estimator for eigenvalue problems by mixed finite element method

In this paper,a residual type of a posteriori error estimator for the general second order elliptic eigenpair approximation by the mixed finite element method is derived and analyzed,based on a type of superconvergence result of the eigenfunction approximation.Its efficiency and reliability are proved by both theoretical analysis and numerical experiments.     

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…     

关于矩阵特征值问题向后误差分析的注记

本文研究实矩阵关于复近似特征对的范数型向后误差．在复扰动情形,这个问题已被Higham 等学者解决．本文研究实扰动情形．结果表明,通常情况下,两种情形差别不大,但在某些情形,二者可以相差很大．作为推广,我们还讨论了矩阵多项式的相应问题．文中的一个结果部分地解决了D．J．Higham和N．J．Higham 1999年提出的一个待解决的问题．     

Interpolation algorithm of Leverrier–Faddev type for polynomial matrices

We investigated an interpolation algorithm for computing outer inverses of a given polynomial matrix, based on the Leverrier–Faddeev method. This algorithm is a continuation of the finite algorithm for computing generalized inverses of a given polynomial matrix, introduced in [11]. Also, a method for estimating the degrees of polynomial matrices arising from the Leverrier–Faddeev algorithm is given as the improvement of the interpolation algorithm. Based on similar idea, we introduced methods for computing rank and index of polynomial matrix. All algorithms are implemented in the symbolic programming language MATHEMATICA , and tested on several different classes of test examples.