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.

Summary This paper is concerned with several variants of the Hermitian and skew-Hermitian splitting iteration method to solve a class of complex symmetric linear systems. Theoretical analysis shows that several Hermitian and skew-Hermitian splitting based iteration methods are unconditionally convergent. Numerical experiments from an n-degree-of-freedom linear system are reported to illustrate the efficiency of the proposed methods. Copyright © 2014 John Wiley & Sons, Ltd.

We analyze an algorithm for computing a skew-Hermitian logarithm of a unitary matrix. This algorithm is very easy to implement using standard software and it works well even for unitary matrices with no spectral conditions assumed. Certain examples, with many eigenvalues near -1, lead to very non-Hermitian output for other basic methods of calculating matrix logarithms. Altering the output of these algorithms to force an Hermitian output creates accuracy issues which are avoided in the considered algorithm. A modification is introduced to deal properly with the $J$-skew symmetric unitary matrices. Applications to numerical studies of topological insulators in two symmetry classes are discussed.

The eigenproblems of the rank-one updates of the matrices have lots of applications in scientific computation and engineering such as the symmetric tridiagonal eigenproblems by the divide-andconquer method and Web search engine. Many researchers have well studied the algorithms for computing eigenvalues of Hermitian matrices updated by a rank-one matrix [1–6]. Recently, Ding and Zhou studied a spectral perturbation theorem for rank-one updated matrices of special structure in [7] and considered two applications. Cheng, Luo, and Li considered the bounds of the smallest and largest eigenvalues for rank-one modification of Hermitian matrices [8]. Eigenvalue bounds for perturbations of Hermitian matrices have been considered by Ipsen and Nadler in [9]. In this paper, we consider the bounds of the eigenvalues for rank-one modification of Hermitian matrices. The ideas of this paper were mainly motivated by one of [9]. We study the following form

SUMMARY A Hermitian matrix X is called a least-squares solution of the inconsistent matrix equation AXA* = B, where B is Hermitian. A* denotes the conjugate transpose of A if it minimizes the F-norm of B − AXA*; it is called a least-rank solution of AXA* = B if it minimizes the rank of B − AXA*. In this paper, we study these two types of solutions by using generalized inverses of matrices and some matrix decompositions. In particular, we derive necessary and sufficient conditions for the two types of solutions to coincide. Copyright © 2012 John Wiley & Sons, Ltd.

SUMMARY For a pair of given Hermitian matrix A and rectangular matrix B with the same row number, we reformulate a well-known simultaneous Hermitian-type generalized singular value decomposition (HGSVD) with more precise structure and parameters and use it to derive some algebraic properties of the linear Hermitian matrix function A−BXB* and Hermitian solution of the matrix equation BXB* = A, and the canonical form of a partitioned Hermitian matrix and some optimization problems on its inertia and rank. Copyright © 2012 John Wiley & Sons, Ltd.

SUMMARY Strang's proposal to use a circulant preconditioner for linear systems of equations with a Hermitian positive definite Toeplitz matrix has given rise to considerable research on circulant preconditioners. This paper presents an {eiφ}-circulant Strang-type preconditioner. Copyright © 2011 John Wiley & Sons, Ltd.

SUMMARY In this note, some errors in the article (Numer. Linear Algebra Appl. 2007; 14:217–235) are pointed out and some correct results are presented. Copyright © 2011 John Wiley & Sons, Ltd.

This paper deals with the normwise perturbation theory for linear (Hermitian) matrix equations. The definition of condition number for the linear (Hermitian) matrix equations is presented. The lower and upper bounds for the condition number are derived. The estimation for the optimal backward perturbation bound for the Hermitian matrix equations is obtained. Copyright © 2010 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.

General stationary iterative methods with a singular matrix M for solving range-Hermitian singular linear systems are presented, some convergence conditions and the representation of the solution are also given. It can be verified that the general Ortega–Plemmons theorem and Keller theorem for the singular matrix M still hold. Furthermore, the singular matrix M can act as a good preconditioner for solving range-Hermitian linear systems. Numerical results have demonstrated the effectiveness of the general stationary iterations and the singular preconditioner M. Copyright © 2009 John Wiley & Sons, Ltd.

Through a Hermitian-type (skew-Hermitian-type) singular value decomposition for pair of matrices (A, B) introduced by Zha (Linear Algebra Appl. 1996; 240:199–205), where A is Hermitian (skew-Hermitian), we show how to find a Hermitian (skew-Hermitian) matrix X such that the matrix expressions A − BX ± X*B* achieve their maximal and minimal possible ranks, respectively. For the consistent matrix equations BX ± X*B* = A, we give general solutions through the two kinds of generalized singular value decompositions. As applications to the general linear model {y, Xβ, σ2V}, we discuss the existence of a symmetric matrix G such that Gy is the weighted least-squares estimator and the best linear unbiased estimator of Xβ, respectively. Copyright © 2007 John Wiley & Sons, Ltd.

This note outlines an algorithm for solving the complex ‘matrix Procrustes problem’. This is a least-squares approximation over the cone of positive semi-definite Hermitian matrices, which has a number of applications in the areas of Optimization, Signal Processing and Control. The work generalizes the method of Allwright (SIAM J. Control Optim. 1988; 26(3):537–556), who obtained a numerical solution to the real-valued version of the problem. It is shown that, subject to an appropriate rank assumption, the complex problem can be formulated in a real setting using a matrix-dilation technique, for which the method of Allwright is applicable. However, this transformation results in an over-parametrization of the problem and, therefore, convergence to the optimal solution is slow. Here, an alternative algorithm is developed for solving the complex problem, which exploits fully the special structure of the dilated matrix. The advantages of the modified algorithm are demonstrated via a numerical example. Copyright © 2007 John Wiley & Sons, Ltd.

The consistent conditions and the general expressions about the Hermitian solutions of the linear matrix equations AXB=C and (AX, XB)=(C, D) are studied in depth, where A, B, C and D are given matrices of suitable sizes. The Hermitian minimum F-norm solutions are obtained for the matrix equations AXB=C and (AX, XB)=(C, D) by Moore–Penrose generalized inverse, respectively. For both matrix equations, we design iterative methods according to the fundamental idea of the classical conjugate direction method for the standard system of linear equations. Numerical results show that these iterative methods are feasible and effective in actual computations of the solutions of the above-mentioned two matrix equations. Copyright © 2006 John Wiley & Sons, Ltd.

In this paper we consider solving Hermitian Toeplitz systems Tnx=b by using the preconditioned conjugate gradient (PCG) method. Here the Toeplitz matrices Tn are assumed to be generated by a non-negative continuous 2π-periodic function ƒ, i.e. Tn=n[ƒ]. It was proved in (Linear Algebra Appl. 1993; 190:181) that if ƒ is positive then the spectrum of n[1/ƒ]n[ƒ] is clustered around 1. We prove that the trigonometric polynomial q (s⩾2, cf. (2) and (3)) converges to 1/ƒ uniformly as n→∞ under the condition that 1/ƒ is in Wiener class. It follows that the computational cost of the PCG method can be reduced by replacing 1/ƒ with q, where N

This work is concerned with the signal interpolation problem, i.e. given only samples of a signal, a method is derived for evaluating its samples on finer grids. The derivation is based on a discrete-time decimation formula. In the special case where the known samples have the Hermitian property, two schemes are presented and mathematically proved to result in interpolated points having the same property. The first scheme does not utilize the known sample at the origin and results in a square system of equations to be solved for the unknown interpolated points of the signal. The second scheme has the merit of utilizing all the known samples, but it results in an overdetermined system of equations to be solved by the least squares method. The exploitation of the elegant properties of the involved centrosymmetric matrices is central to the treatment presented here. Copyright © 2002 John Wiley & Sons, Ltd.

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.

We are interested in the calculation of explicit formulae for the condition numbers of the two factors of the polar decomposition of a full rank real or complex m × n matrix A, where m ≥ n. We use a unified presentation that enables us to compute such condition numbers in the Frobenius norm, in cases where A is a square or a rectangular matrix subjected to real or complex perturbations. We denote by σ1 (respectively σn) the largest (respectively smallest) singular value of A, and by K(A) = σ1/σn the generalized condition number of A. Our main results are that the absolute condition number of the Hermitian polar factor is √2(1 + K(A)2)1/2/(1 + K(A)) and that the absolute condition number of the unitary factor of a rectangular matrix is 1/σn. Copyright © 2000 John Wiley & Sons, Ltd.

A new iterative scheme is described for the solution of large linear systems of equations with a matrix of the form A = ρU + ζI, where ρ and ζ are constants, U is a unitary matrix and I is the identity matrix. We show that for such matrices a Krylov subspace basis can be generated by recursion formulas with few terms. This leads to a minimal residual algorithm that requires little storage and makes it possible to determine each iterate with fairly little arithmetic work. This algorithm provides a model for iterative methods for non-Hermitian linear systems of equations, in a similar way to the conjugate gradient and conjugate residual algorithms. Our iterative scheme illustrates that results by Faber and Manteuffel [3,4] on the existence of conjugate gradient algorithms with short recurrence relations, and related results by Joubert and Young [13], can be extended.