Search

The shifted finite-difference discretization of the one-dimensional almost-isotropic spatial fractional diffusion equation results in a discrete linear system whose coefficient matrix is a sum of two diagonal-times-Toeplitz matrices. For this kind of linear systems, we propose a class of regularized Hermitian splitting iteration methods and prove its asymptotic convergence under mild conditions. For appropriate circulant-based approximation to the corresponding regularized Hermitian splitting preconditioner, we demonstrate that the induced fast regularized Hermitian splitting preconditioner possesses a favorable preconditioning property. Numerical results show that, when used to precondition Krylov sub-space iteration methods such as generalized minimal residual and biconjugate gradient stabilized methods, the fast preconditioner significantly outperforms several existing ones.

Summary Estimating the number of eigenvalues located in a given interval of a large sparse Hermitian matrix is an important problem in certain applications, and it is a prerequisite of eigensolvers based on a divide-and-conquer paradigm. Often, an exact count is not necessary, and methods based on stochastic estimates can be utilized to yield rough approximations. This paper examines a number of techniques tailored to this specific task. It reviews standard approaches and explores new ones based on polynomial and rational approximation filtering combined with a stochastic procedure. We also discuss how the latter method is particularly well-suited for the FEAST eigensolver. Copyright © 2016 John Wiley & Sons, Ltd.

Summary We describe randomized algorithms for computing the dominant eigenmodes of the generalized Hermitian eigenvalue problem Ax = λBx, with A Hermitian and B Hermitian and positive definite. The algorithms we describe only require forming operations Ax,Bx and B−1x and avoid forming square roots of B (or operations of the form, B1/2x or B−1/2x). We provide a convergence analysis and a posteriori error bounds and derive some new results that provide insight into the accuracy of the eigenvalue calculations. The error analysis shows that the randomized algorithm is most accurate when the generalized singular values of B−1A decay rapidly. A randomized algorithm for the generalized singular value decomposition is also provided. Finally, we demonstrate the performance of our algorithm on computing an approximation to the Karhunen–Loeve expansion, which involves a computationally intensive generalized Hermitian eigenvalue problem with rapidly decaying eigenvalues. Copyright © 2015 John Wiley & Sons, Ltd.

The performance of the Hermitian and skew-Hermitian splitting (HSS) preconditioner for the non-Hermitian positive definite system of linear equations is largely dependent on the choice of its parameter value. In this work, an efficient scaled norm minimization (SNM) method is proposed to compute the parameter value of the HSS preconditioner. In addition, by choosing different parameters for the Hermitian and the skew-Hermitian matrices in the HSS preconditioner, a two-parameter HSS preconditioner is proposed. Moreover, an efficient and practical formula for computing the parameter values of this new preconditioner is also derived by using the SNM method. Numerical examples are illustrated to verify the performances of the HSS and the two-parameter HSS preconditioners when their parameters are computed by the SNM method.

Summary For the discrete linear systems resulted from the discretization of the one-dimensional anisotropic spatial fractional diffusion equations of variable coefficients with the shifted finite-difference formulas of the Grunwald–Letnikov type, we propose a class of respectively scaled Hermitian and skew-Hermitian splitting iteration method and establish its asymptotic convergence theory. The corresponding induced matrix splitting preconditioner, through further replacements of the involved Toeplitz matrices with certain circulant matrices, leads to an economic variant that can be executed by fast Fourier transforms. Both theoretical analysis and numerical implementations show that this fast respectively scaled Hermitian and skew-Hermitian splitting preconditioner can significantly improve the computational efficiency of the Krylov subspace iteration methods employed as effective linear solvers for the target discrete linear systems.

Summary We consider subspace iteration (or projection-based) algorithms for computing those eigenvalues (and associated eigenvectors) of a Hermitian matrix that lie in a prescribed interval. For the case that the projector is approximated with polynomials, we present an adaptive strategy for selecting the degree of these polynomials such that convergence is achieved with near-to-optimum overall work without detailed a priori knowledge about the eigenvalue distribution. The idea is then transferred to the approximation of the projector by numerical integration, which corresponds to FEAST algorithm proposed by E. Polizzi in 2009. [E. Polizzi: Density-matrix-based algorithm for solving eigenvalue problems. Phys. Rev. B 2009; 79:115112]. Here, our adaptation controls the number of integration nodes. We also discuss the interaction of the method with search space reduction methods.

Summary 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 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. Recently, a dual subspace FEAST algorithm was proposed to extend the FEAST algorithm to non-Hermitian problems. In this paper, we instead use the oblique projection technique to extend FEAST to the non-Hermitian problems. Our approach can be summarized as follows: (a) construct a particular contour integral to form a search subspace containing the desired eigenspace and (b) use the oblique projection technique to extract desired eigenpairs with appropriately chosen test subspace. The related mathematical framework is established. Comparing to the dual subspace FEAST algorithm, we can save the computational cost roughly by a half if only the eigenvalues or the eigenvalues together with their right eigenvectors are needed. We also address some implementation issues such as how to choose a suitable starting matrix and design-efficient stopping criteria. Numerical experiments are provided to illustrate that our method is stable and efficient.