The preconditioned inverse iteration for hierarchical matrices

The preconditioned inverse iteration is an efficient method to compute the smallest eigenpair of a symmetric positive definite matrix M. Here we use this method to find the smallest eigenvalues of a hierarchical matrix. The storage complexity of the data‐sparse ‐matrices is almost linear. We use ‐arithmetic to precondition with an approximate inverse of M or an approximate Cholesky decomposition of M. In general, ‐arithmetic is of linear‐polylogarithmic complexity, so the computation of one eigenvalue is cheap. We extend the ideas to the computation of inner eigenvalues by computing an invariant subspace S of (M ? μI)² by subspace preconditioned inverse iteration. The eigenvalues of the generalized matrix Rayleigh quotient μ_M(S) are the desired inner eigenvalues of M. The idea of using (M ? μI)² instead of M is known as the folded spectrum method. As we rely on the positive definiteness of the shifted matrix, we cannot simply apply shifted inverse iteration therefor. Numerical results substantiate the convergence properties and show that the computation of the eigenvalues is superior to existing algorithms for non‐sparse matrices.Copyright © 2012 John Wiley & Sons, Ltd.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

Additive Maps Preserving Moore–Penrose Inverses of Matrices on Symmetric Matrix Spaces

Suppose F is a field of characteristic not 2. Let M_n F and S_n F be the n × n full matrix space and symmetric matrix space over F, respectively. All additive maps from S_n F to S_n F (respectively, M_n F) preserving Moore–Penrose inverses of matrices are characterized. We first characterize all additive Moore–Penrose inverse preserving maps from S_n F to M_n F, and thereby, all additive Moore–Penrose inverse preserving maps from S_n F to itself are characterized by restricting the range of these additive maps into the symmetric matrix space.     

A note on harmonic Ritz values and their reciprocals

This note summarizes an investigation of harmonic Ritz values to approximate the interior eigenvalues of a real symmetric matrix A while avoiding the explicit use of the inverse A^?1. We consider a bounded functional ψ that yields the reciprocals of the harmonic Ritz values of a symmetric matrix A. The crucial observation is that with an appropriate residual s, many results from Rayleigh quotient and Rayleigh–Ritz theory naturally extend. The same is true for the generalization to matrix pencils (A, B) when B is symmetric positive definite. These observations have an application in the computation of eigenvalues in the interior of the spectrum of a large sparse matrix. The minimum and maximum of ψ correspond to the eigenpairs just to the left and right of zero (or a chosen shift). As a spectral transformation, this distinguishes ψ from the original harmonic approach where an interior eigenvalue remains at the interior of the transformed spectrum. As a consequence, ψ is a very attractive vehicle for a matrix‐free, optimization‐based eigensolver. Instead of computing the smallest/largest eigenvalues by minimizing/maximizing the Rayleigh quotient, one can compute interior eigenvalues as the minimum/maximum of ψ. Copyright © 2009 John Wiley & Sons, Ltd.     

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.     

Preconditioned HSS method for large multilevel block Toeplitz linear systems via the notion of matrix‐valued symbol

We perform a spectral analysis of the preconditioned Hermitian/skew‐Hermitian splitting (PHSS) method applied to multilevel block Toeplitz linear systems in which the coefficient matrix T_n(f) is associated with a Lebesgue integrable matrix‐valued function f. When the preconditioner is chosen as a Hermitian positive definite multilevel block Toeplitz matrix T_n(g), the resulting sequence of PHSS iteration matrices M_n belongs to the generalized locally Toeplitz class. In this case, we are able to compute the symbol ?(f,g) describing the asymptotic eigenvalue distribution of M_nwhen n→∞ and the matrix size diverges. By minimizing the infinity norm of the spectral radius of the symbol ?(f,g), we are also able to identify effective PHSS preconditioners T_n(g) for the matrix T_n(f). A number of numerical experiments are presented and commented, showing that the theoretical results are confirmed and that the spectral analysis leads to efficient PHSS methods. Copyright © 2015 John Wiley & Sons, Ltd.     

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.     

A New Algorithm for the Symmetric Tridiagonal Eigenvalue Problem

We apply a novel approach to approximate within ϵ to all the eigenvalues of an n × n symmetric tridiagonal matrix A using at most n²([3 log₂(625n⁶)] + (83n − 34)[log₂ (log₂((λ₁ − λ_n)/(2ϵ))/log₂(25_n))]) arithmetic operations where λ₁ and λ_n denote the extremal eigenvalues of A. The algorithm can be modified to compute any fixed numbers of the largest and the smallest eigenvalues of A and may also be applied to the band symmetric matrices without their reduction to the tridiagonal form.     

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.     

A Galerkin Approach for Solving Matrix Equations with Hierarchical Matrices

We consider a new approach for computing solutions of certain matrix equations, for example AXA = C, AX + XB = C or AX = I. This approach is based on a variational formulation in the matrix space, employing the Frobenius inner product. Using the space of ℋ²-matrices as trial space leads to a sparse linear system that can be solved by iterative methods to compute an approximate solution of the underlying matrix equation. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

SQP algorithms for solving Toeplitz matrix approximation problem

Given an n × n matrix F, we find the nearest symmetric positive semi‐definite Toeplitz matrix T to F. The problem is formulated as a non‐linear minimization problem with positive semi‐definite Toeplitz matrix as constraints. Then a computational framework is given. An algorithm with rapid convergence is obtained by l₁ Sequential Quadratic Programming (SQP) method. Copyright © 2002 John Wiley & Sons, Ltd.     

A Low-Complexity Divide-and-Conquer Method for Computing Eigenvalues and Eigenvectors of Symmetric Band Matrices

A framework for an efficient low-complexity divide-and-conquer algorithm for computing eigenvalues and eigenvectors of an n × n symmetric band matrix with semibandwidth b n is proposed and its arithmetic complexity analyzed. The distinctive feature of the algorithm—after subdivision of the original problem into p subproblems and their solution—is a separation of the eigenvalue and eigenvector computations in the central synthesis problem. The eigenvalues are computed recursively by representing the corresponding symmetric rank b(p–1) modification of a diagonal matrix as a series of rank-one modifications. Each rank-one modifications problem can be solved using techniques developed for the tridiagonal divide-and-conquer algorithm. Once the eigenvalues are known, the corresponding eigenvectors can be computed efficiently using modified QR factorizations with restricted column pivoting. It is shown that the complexity of the resulting divide-and-conquer algorithm is O (n ² b ²) (in exact arithmetic).This revised version was published online in October 2005 with corrections to the Cover Date.     

New convergence results and preconditioning strategies for the conjugate gradient method

Instead of the standard estimate in terms of the spectral condition number we develop a new CG iteration number estimate depending on the quantity B = 1/ntr M/(det M)^1/n, where M is an n × n preconditioned matrix. A new family of iterative methods for solving symmetric positive definite systems based on B-reducing strategies is described. Numerical results are presented for the new algorithms and compared with several well-known preconditioned CG methods.     

Computational complexity of LCPs associated with positive definite symmetric matrices

Murty in a recent paper has shown that the computational effort required to solve a linear complementarity problem (LCP), by either of the two well known complementary pivot methods is not bounded above by a polynomial in the size of the problem. In that paper, by constructing a class of LCPs—one of ordern forn 2—he has shown that to solve the problem of ordern, either of the two methods goes through 2 ⁿ pivot steps before termination.However that paper leaves it as an open question to show whether or not the same property holds if the matrix,M, in the LCP is positive definite and symmetric. The class of LCPs in whichM is positive definite and symmetric is of particular interest because of the special structure of the problems, and also because they appear in many practical applications.In this paper, we study the computational growth of each of the two methods to solve the LCP, (q, M), whenM is positive definite and symmetric and obtain similar results.This research is partially supported by Air Force Office of Scientific Research, Air Force Number AFOSR-78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation thereon.     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.     

A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions

Let M_T be the mean first passage matrix for an n‐state ergodic Markov chain with a transition matrix T. We partition T as a 2×2 block matrix and show how to reconstruct M_T efficiently by using the blocks of T and the mean first passage matrices associated with the non‐overlapping Perron complements of T. We present a schematic diagram showing how this method for computing M_T can be implemented in parallel. We analyse the asymptotic number of multiplication operations necessary to compute M_T by our method and show that, for large size problems, the number of multiplications is reduced by about 1/8, even if the algorithm is implemented in serial. We present five examples of moderate sizes (of orders 20–200) and give the reduction in the total number of flops (as opposed to multiplications) in the computation of M_T. The examples show that when the diagonal blocks in the partitioning of T are of equal size, the reduction in the number of flops can be much better than 1/8. Copyright © 2001 John Wiley & Sons, Ltd.     

Iterative minimization of the Rayleigh quotient by block steepest descent iterations

The topic of this paper is the convergence analysis of subspace gradient iterations for the simultaneous computation of a few of the smallest eigenvalues plus eigenvectors of a symmetric and positive definite matrix pair (A,M). The methods are based on subspace iterations for A ^{? 1}M and use the Rayleigh‐Ritz procedure for convergence acceleration. New sharp convergence estimates are proved by generalizing estimates, which have been presented for vectorial steepest descent iterations (see SIAM J. Matrix Anal. Appl., 32(2):443‐456, 2011). Copyright © 2013 John Wiley & Sons, Ltd.     

A Multilevel AINV Preconditioner

In this paper we describe an algebraic multilevel extension of the approximate inverse AINV preconditioner for solving symmetric positive definite linear systems Ax=b with the preconditioned conjugate gradient method. The smoother is the approximate inverse M and the coarse grids and the interpolation operator are constructed by looking at the entries of M. Numerical examples are given for problems arising from discretization of partial differential equations.     

m-Functions and inverse spectral analysis for finite and semi-infinite Jacobi matrices

We study inverse spectral analysis for finite and semi-infinite Jacobi matricesH. Our results include a new proof of the central result of the inverse theory (that the spectral measure determinesH). We prove an extension of the theorem of Hochstadt (who proved the result in casen = N) thatn eigenvalues of anN × N Jacobi matrixH can replace the firstn matrix elements in determiningH uniquely. We completely solve the inverse problem for (δ _n , (H-z)^-1 δ _n ) in the caseN < ∞. This material is based upon work supported by the National Science Foundation under Grant Nos. DMS-9623121 and DMS-9401491.     

单位积决定的若当矩阵代数(英文)

本文研究了单位积决定的若当矩阵代数M=Mn(R)的条件及分类问题.利用基矩阵及巧妙对对称双线性映射{·,·}进行构造和扩充,用初等矩阵的方法,获得了一系列新的同样重要的定义,结论与证明(与参考文献[1]相比较),推广了参考文献[1]的结论,作为其应用可以进一步证明了Mn(R)上的任意可逆线性映射都是保单位积的.