Guojian Yin

Guojian Yin

The FEAST algorithm, due to Polizzi, is a typical contour-integral based eigensolver for computing the eigenvalues, along with their eigenvectors, inside a given region in the complex plane. It was formulated under the circumstance that the considered eigenproblem is Hermitian. The FEAST algorithm is stable and accurate, and has attracted much attention in recent years. However, it was observed that the FEAST algorithm may fail to find the target eigenpairs when applying it to the non-Hermitian problems. Efforts have been made to adapt the FEAST algorithm to non-Hermitian cases. In this work, we develop a new non-Hermitian scheme for the FEAST algorithm. The mathematical framework will be established, and the convergence analysis of our new method will be studied. Numerical experiments are reported to demonstrate the effectiveness of our method and to validate the convergence properties.

HanQin Cai, Jian-Feng Cai, Tianming Wang et al.

Consider a spectrally sparse signal $\boldsymbol{x}$ that consists of $r$ complex sinusoids with or without damping. We study the robust recovery problem for the spectrally sparse signal under the fully observed setting, which is about recovering $\boldsymbol{x}$ and a sparse corruption vector $\boldsymbol{s}$ from their sum $\boldsymbol{z}=\boldsymbol{x}+\boldsymbol{s}$. In this paper, we exploit the low-rank property of the Hankel matrix formed by $\boldsymbol{x}$, and formulate the problem as the robust recovery of a corrupted low-rank Hankel matrix. We develop a highly efficient non-convex algorithm, coined Accelerated Structured Alternating Projections (ASAP). The high computational efficiency and low space complexity of ASAP are achieved by fast computations involving structured matrices, and a subspace projection method for accelerated low-rank approximation. Theoretical recovery guarantee with a linear convergence rate has been established for ASAP, under some mild assumptions on $\boldsymbol{x}$ and $\boldsymbol{s}$. Empirical performance comparisons on both synthetic and real-world data confirm the advantages of ASAP, in terms of computational efficiency and robustness aspects.

Xian-Ming Gu, Ting-Zhu Huang, Guojian Yin et al.

It is known that the restarted full orthogonalization method (FOM) outperforms the restarted generalized minimum residual (GMRES) method in several circumstances for solving shifted linear systems when the shifts are handled simultaneously. Many variants of them have been proposed to enhance their performance. We show that another restarted method, the restarted Hessenberg method [M. Heyouni, Méthode de Hessenberg Généralisée et Applications, Ph.D. Thesis, Université des Sciences et Technologies de Lille, France, 1996] based on Hessenberg procedure, can effectively be employed, which can provide accelerating convergence rate with respect to the number of restarts. Theoretical analysis shows that the new residual of shifted restarted Hessenberg method is still collinear with each other. In these cases where the proposed algorithm needs less enough CPU time elapsed to converge than the earlier established restarted shifted FOM, weighted restarted shifted FOM, and some other popular shifted iterative solvers based on the short-term vector recurrence, as shown via extensive numerical experiments involving the recent popular applications of handling the time fractional differential equations.

Guojian Yin

Recently, a kind of eigensolvers based on contour integral were developed for computing the eigenvalues inside a given region in the complex plane. The CIRR method is a classic example among this kind of methods. In this paper, we propose a contour-integral based QZ method which is also devoted to computing partial spectrum of generalized eigenvalue problems. Our new method takes advantage of the technique in the CIRR method of constructing a particular subspace containing the eigenspace of interest via contour integrals. The main difference between our method and CIRR is the mechanism of extracting the desired eigenpairs. We establish the related framework and address some implementation issues so as to make the resulting method applicable in practical implementations. Numerical experiments are reported to illustrate the numerical performance of our new method.

Guojian Yin, Raymond H. Chan, Man-Chung Yeung

The contour-integral based eigensolvers are the recent efforts for computing the eigenvalues inside a given region in the complex plane. The best-known members are the Sakurai-Sugiura (SS) method, its stable version CIRR, and the FEAST algorithm. An attractive computational advantage of these methods is that they are easily parallelizable. The FEAST algorithm was developed for the generalized Hermitian eigenvalue problems. It is stable and accurate. However, it may fail when applied to non-Hermitian problems. In this paper, we extend the FEAST algorithm to non-Hermitian problems. The approach can be summarized as follows: (i) to construct a particular contour integral to form a subspace containing the desired eigenspace, and (ii) to use the oblique projection technique to extract desired eigenpairs with appropriately chosen test subspace. The related mathematical framework is established. We also address some implementation issues such as how to choose a suitable starting matrix and design good stopping criteria. Numerical experiments are provided to illustrate that our method is stable and efficient.

Guojian Yin

In many applications, the information about the number of eigenvalues inside a given region is required. In this paper, we propose a contour-integral based method for this purpose. The new method is motivated by two findings. There exist methods for estimating the number of eigenvalues inside a region in the complex plane. But our method is able to compute the number of eigenvalues inside the given region exactly. An appealing feature of our method is that it can integrate with the recently developed contour-integral based eigensolvers to help them detect whether all desired eigenvalues are found. Numerical experiments are reported to show the viability of our new method.