A restarted Krylov method with inexact inversions

In this paper, we present a new type of restarted Krylov method for calculating the smallest eigenvalues of a symmetric positive definite matrix G. The new framework avoids the Lanczos tridiagonalization process and the use of polynomial filtering. This simplifies the restarting mechanism and allows the introduction of several modifications. Convergence is assured by a monotonicity property that pushes the eigenvalues toward their limits. Another innovation is the use of inexact inversions of G to generate the Krylov matrices. In this approach, the inverse of G is approximated by using an iterative method to solve the related linear system. Numerical experiments illustrate the usefulness of the proposed approach.     

Numerical enclosure for multiple eigenvalues of an Hermitian matrix whose graph is a tree

In this paper we consider a numerical enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. If an Hermitian matrix A whose graph is a tree has multiple eigenvalues, it has the property that matrices which are associated with some branches in the undirected graph of A have the same eigenvalues. By using this property and interlacing inequalities for Hermitian matrices, we show an enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. Since we do not generally know whether a given matrix has exactly a multiple eigenvalue from approximate computations, we use the property of interlacing inequalities to enclose some eigenvalues including multiplicities.In this process, we only use the enclosure of simple eigenvalues to enclose a multiple eigenvalue by using a computer and interval arithmetic.     

Computing the matrix sign and absolute value functions

We present two algorithms for the computation of the matrix sign and absolute value functions. Both algorithms avoid a complete diagonalisation of the matrix, but they however require some informations regarding the eigenvalues location. The first algorithm consists in a sequence of polynomial iterations based on appropriate estimates of the eigenvalues, and converging to the matrix sign if all the eigenvalues are real. Convergence is obtained within a finite number of steps when the eigenvalues are exactly known. Nevertheless, we present a second approach for the computation of the matrix sign and absolute value functions, when the eigenvalues are exactly known. This approach is based on the resolution of an interpolation problem, can handle the case of complex eigenvalues and appears to be faster than the iterative approach. To cite this article: M. Ndjinga, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach

Summary The Symmetric Tridiagonal Eigenproblem has been the topic of some recent work. Many methods have been advanced for the computation of the eigenvalues of such a matrix. In this paper, we present a divide-and-conquer approach to the computation of the eigenvalues of a symmetric tridiagonal matrix via the evaluation of the characteristic polynomial. The problem of evaluation of the characteristic polynomial is partitioned into smaller parts which are solved and these solutions are then combined to form the solution to the original problem. We give the update equations for the characteristic polynomial and certain auxiliary polynomials used in the computation. Furthermore, this set of recursions can be implemented on a regulartree structure. If the concurrency exhibited by this algorithm is exploited, it can be shown that thetime for computation of all the eigenvalues becomesO(nlogn) instead ofO(n ²) as is the case for the approach where the order is increased by only one at every step. We address the numerical problems associated with the use of the characteristic polynomial and present a numerically stable technique for the eigenvalue computation.     

A symmetry exploiting Lanczos method for symmetric Toeplitz matrices

Several methods for computing the smallest eigenvalues of a symmetric and positive definite Toeplitz matrix T have been studied in the literature. Most of them share the disadvantage that they do not reflect symmetry properties of the corresponding eigenvector. In this note we present a Lanczos method which approximates simultaneously the odd and the even spectrum of T at the same cost as the classical Lanczos approach.     

Nonequivalence transformation of λ‐matrix eigenproblems and model embedding approach to model tuning

In this paper we present some theory for a non‐equivalence transformation of matrix eigenvalues for λ‐matrix polynomials. Application of this transformation to eigenvalue embedding for model tuning on a realistic industry problem is illustrated. The new approach has several advantages such as flexibility, efficiency, and structure‐preservation. A numerical experiment on a pseudosimulation data set from The Boeing Company is reported. Copyright © 2001 John Wiley & Sons, Ltd.     

Locally Optimal Block Preconditioned Conjugate Gradient Method for Hierarchical Matrices

We present a method of almost linear complexity to approximate some (inner) eigenvalues of symmetric self-adjoint integral or differential operators. Using ℋ-arithmetic the discretisation of the operator leads to a large hierarchical (ℋ-) matrix M. We assume that M is symmetric, positive definite. Then we compute the smallest eigenvalues by the locally optimal block preconditioned conjugate gradient method (LOBPCG), which has been extensively investigated by Knyazev and Neymeyr. Hierarchical matrices were introduced by W. Hackbusch in 1998. They are data-sparse and require only O(nlog₂ n) storage. There is an approximative inverse, besides other matrix operations, within the set of ℋ-matrices, which can be computed in linear-polylogarithmic complexity. We will use the approximative inverse as preconditioner in the LOBPCG method. Further we combine the LOBPCG method with the folded spectrum method to compute inner eigenvalues of M. This is equivalent to the application of LOBPCG to the matrix M_μ = (M − μI)² . The matrix M_μ is symmetric, positive definite, too. Numerical experiments illustrate the behavior of the suggested approach. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the eigenvalue distribution of a class of preconditioning methods

Summary A class of preconditioning methods depending on a relaxation parameter is presented for the solution of large linear systems of equationAx=b, whereA is a symmetric positive definite matrix. The methods are based on an incomplete factorization of the matrixA and include both pointwise and blockwise factorization. We study the dependence of the rate of convergence of the preconditioned conjugate gradient method on the distribution of eigenvalues ofC ^–1 A, whereC is the preconditioning matrix. We also show graphic representations of the eigenvalues and present numerical tests of the methods.     

Preconditioned AHSS iteration method for singular saddle point problems

In this paper, for solving the singular saddle point problems, we present a new preconditioned accelerated Hermitian and skew-Hermitian splitting (AHSS) iteration method. The semi-convergence of this method and the eigenvalue distribution of the preconditioned iteration matrix are studied. In addition, we prove that all eigenvalues of the iteration matrix are clustered for any positive iteration parameters α and β. Numerical experiments illustrate the theoretical results and examine the numerical effectiveness of the AHSS iteration method served either as a preconditioner or as a solver.     

PDEs for the Gaussian ensemble with external source and the Pearcey distribution

The present paper studies a Gaussian Hermitian random matrix ensemble with external source, given by a fixed diagonal matrix with two eigenvalues ±a. As a first result, the probability that the eigenvalues of the ensemble belong to an interval E satisfies a fourth‐order PDE with quartic nonlinearity; the variables are the eigenvalue a and the boundary of E. This equation enables one to find a PDE for the Pearcey distribution. The latter describes the statistics of the eigenvalues near the closure of a gap, i.e., when the support of the equilibrium measure for large‐size random matrices has a gap that can be made to close. The Gaussian Hermitian random matrix ensemble with external source, described above, has this feature. The Pearcey distribution is shown to satisfy a fourth‐order PDE with cubic nonlinearity. This also gives the PDE for the transition probability of the Pearcey process, a limiting process associated with nonintersecting Brownian motions on ℝ. © 2006 Wiley Periodicals, Inc.     

Sturm Sequences and Random Eigenvalue Distributions

This paper proposes that the study of Sturm sequences is invaluable in the numerical computation and theoretical derivation of eigenvalue distributions of random matrix ensembles. We first explore the use of Sturm sequences to efficiently compute histograms of eigenvalues for symmetric tridiagonal matrices and apply these ideas to random matrix ensembles such as the β-Hermite ensemble. Using our techniques, we reduce the time to compute a histogram of the eigenvalues of such a matrix from O(n ²+m) to O(mn) time where n is the dimension of the matrix and m is the number of bins (with arbitrary bin centers and widths) desired in the histogram (m is usually much smaller than n). Second, we derive analytic formulas in terms of iterated multivariate integrals for the eigenvalue distribution and the largest eigenvalue distribution for arbitrary symmetric tridiagonal random matrix models. As an example of the utility of this approach, we give a derivation of both distributions for the β-Hermite random matrix ensemble (for general β). Third, we explore the relationship between the Sturm sequence of a random matrix and its shooting eigenvectors. We show using Sturm sequences that assuming the eigenvector contains no zeros, the number of sign changes in a shooting eigenvector of parameter λ is equal to the number of eigenvalues greater than λ. Finally, we use the techniques presented in the first section to experimentally demonstrate a O(log n) growth relationship between the variance of histogram bin values and the order of the β-Hermite matrix ensemble. This research was supported by NSF Grant DMS–0411962.     

The Probability that a Random Real Gaussian Matrix haskReal Eigenvalues, Related Distributions, and the Circular Law

LetAbe annbynmatrix whose elements are independent random variables with standard normal distributions. Girko's (more general) circular law states that the distribution of appropriately normalized eigenvalues is asymptotically uniform in the unit disk in the complex plane. We derive the exact expected empirical spectral distribution of the complex eigenvalues for finiten, from which convergence in the expected distribution to the circular law for normally distributed matrices may be derived. Similar methodology allows us to derive a joint distribution formula for the real Schur decomposition ofA. Integration of this distribution yields the probability thatAhas exactlykreal eigenvalues. For example, we show that the probability thatAhas all real eigenvalues is exactly 2^{−n(n−1)/4}.     

The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

We consider the eigenvalues and eigenvectors of finite, low rank perturbations of random matrices. Specifically, we prove almost sure convergence of the extreme eigenvalues and appropriate projections of the corresponding eigenvectors of the perturbed matrix for additive and multiplicative perturbation models.The limiting non-random value is shown to depend explicitly on the limiting eigenvalue distribution of the unperturbed random matrix and the assumed perturbation model via integral transforms that correspond to very well-known objects in free probability theory that linearize non-commutative free additive and multiplicative convolution. Furthermore, we uncover a phase transition phenomenon whereby the large matrix limit of the extreme eigenvalues of the perturbed matrix differs from that of the original matrix if and only if the eigenvalues of the perturbing matrix are above a certain critical threshold. Square root decay of the eigenvalue density at the edge is sufficient to ensure that this threshold is finite. This critical threshold is intimately related to the same aforementioned integral transforms and our proof techniques bring this connection and the origin of the phase transition into focus. Consequently, our results extend the class of ‘spiked’ random matrix models about which such predictions (called the BBP phase transition) can be made well beyond the Wigner, Wishart and Jacobi random ensembles found in the literature. We examine the impact of this eigenvalue phase transition on the associated eigenvectors and observe an analogous phase transition in the eigenvectors. Various extensions of our results to the problem of non-extreme eigenvalues are discussed.     

A reconstruction method for a two-dimensional inverse eigenvalue problem

In this paper we describe a method for constructing approximate solutions of a two-dimensional inverse eigenvalue problem. Here we consider the problem of recovering a functionq(x, y) from the eigenvalues of — +q(x, y) on a rectangle with Dirichlet boundary conditions. The potentialq(x, y) is assumed to be symmetric with respect to the midlines of the rectangle. Our method is a generalization of an algorithm Hald presented for the construction of symmetric potentials in the one-dimensional inverse Sturm-Liouville problem. Using a projection method, the inverse spectral problem is reduced to an inverse eigenvalue problem for a matrix. We show that if the given eigenvalues are small perturbations of simple eigenvalues ofq=0, then the matrix problem has a solution. This solution is used to construct a functionq which has the same lowest eigenvalues as the unknownq, and several numerical examples are given to illustrate the methods.     

Remarks on Non-Linear Spectral Perturbation

We are interested in some aspects of the perturbation effects in the spectrum of a real nonnormal matrix A under linear perturbations. We discuss some known results and we use them to justify some recent experimental observations. Moreover, we demonstrate that the qualitative behavior of the eigenvalues of A under linear perturbations may be predicted by inspecting the spectral radius of a related matrix. Then, we show how this information can be used to analyze the quality of the approximation of a projection method and to justify the presence of unexpected approximate eigenvalues.     

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.     

矩阵特征值的一类新的包含域

用盖尔圆盘定理来估计矩阵的特征值是一个经典的方法,这种方法仅利用矩阵的元素来确定特征值的分布区域.本文利用相似矩阵有相同的特征值这一理论,得到了矩阵特征值的一类新的包含域,它们与盖尔圆盘等方法结合起来能提高估计的精确度.     

Spectral analysis of the finite Hankel transform and circular prolate spheroidal wave functions

In this paper, we develop two practical methods for the computation of the eigenvalues as well as the eigenfunctions of the finite Hankel transform operator. These different eigenfunctions are called circular prolate spheroidal wave functions (CPSWFs). This work is motivated by the potential applications of the CPSWFs as well as the development of practical methods for computing their values. Also, in this work, we should prove that the CPSWFs form an orthonormal basis of the space of Hankel band-limited functions, an orthogonal basis of L²([0,1]) and an orthonormal system of L²([0,+∞[). Our computation of the CPSWFs and their associated eigenvalues is done by the use of two different methods. The first method is based on a suitable matrix representation of the finite Hankel transform operator. The second method is based on the use of an efficient quadrature method based on a special family of orthogonal polynomials. Also, we give two Maple programs that implement the previous two methods. Finally, we present some numerical results that illustrate the results of this work.     

Domains of divergence of the USSOR method applied onp-cyclic matrices

Summary Using a recently derived classical type general functional equation, relating the eigenvalues of a weakly cyclic Jacobi iteration matrix to the eigenvalues of its associated Unsymmetric Successive Overrelaxation (USSOR) iteration matrix, we obtain bounds for the convergence of the USSOR method, when applied to systems with ap-cyclic coefficient matrix.     

Inferring consensus weights from pairwise comparison matrices without suitable properties

Pairwise comparison is a popular method for establishing the relative importance of n objects. Its main purpose is to get a set of weights (priority vector) associated with the objects. When the information gathered from the decision maker does not verify some rational properties, it is not easy to search the priority vector. Goal programming is a flexible tool for addressing this type of problem. In this paper, we focus on a group decision-making scenario. Thus, we analyze different methodologies for getting a collective priority vector. The first method is to aggregate general pairwise comparison matrices (i.e., matrices without suitable properties) and then get the priority vector from the consensus matrix. The second method proposes to get the collective priority vector by formulating an optimization problem without determining the consensus pairwise comparison matrix beforehand.