Extremal eigenvalue intervals of symmetric tridiagonal interval matrices

Computing the extremal eigenvalue bounds of interval matrices is non‐deterministic polynomial‐time (NP)‐hard. We investigate bounds on real eigenvalues of real symmetric tridiagonal interval matrices and prove that for a given real symmetric tridiagonal interval matrices, we can achieve its exact range of the smallest and largest eigenvalues just by computing extremal eigenvalues of four symmetric tridiagonal matrices.     

Strategies for spectrum slicing based on restarted Lanczos methods

In the context of symmetric-definite generalized eigenvalue problems, it is often required to compute all eigenvalues contained in a prescribed interval. For large-scale problems, the method of choice is the so-called spectrum slicing technique: a shift-and-invert Lanczos method combined with a dynamic shift selection that sweeps the interval in a smart way. This kind of strategies were proposed initially in the context of unrestarted Lanczos methods, back in the 1990’s. We propose variations that try to incorporate recent developments in the field of Krylov methods, including thick restarting in the Lanczos solver and a rational Krylov update when moving from one shift to the next. We discuss a parallel implementation in the SLEPc library and provide performance results.     

Convergence estimates of nonrestarted and restarted block‐Lanczos methods

The block‐Lanczos method serves to compute a moderate number of eigenvalues and the corresponding invariant subspace of a symmetric matrix. In this paper, the convergence behavior of nonrestarted and restarted versions of the block‐Lanczos method is analyzed. For the nonrestarted version, we improve an estimate by Saad by means of a change of the auxiliary vector so that the new estimate is much more accurate in the case of clustered or multiple eigenvalues. For the restarted version, an estimate by Knyazev is generalized by extending our previous results on block steepest descent iterations and single‐vector restarted Krylov subspace iterations. The new estimates can also be reformulated and applied to invert‐block‐Lanczos methods for solving generalized matrix eigenvalue problems.     

The block conjugate gradient algorithm and related methods

The development of the Lanczos algorithm for finding eigenvalues of large sparse symmetric matrices was followed by that of block forms of the algorithm. In this paper, similar extensions are carried out for a relative of the Lanczos method, the conjugate gradient algorithm. The resulting block algorithms are useful for simultaneously solving multiple linear systems or for solving a single linear system in which the matrix has several separated eigenvalues or is not easily accessed on a computer. We develop a block biconjugate gradient algorithm for general matrices, and develop block conjugate gradient, minimum residual, and minimum error algorithms for symmetric semidefinite matrices. Bounds on the rate of convergence of the block conjugate gradient algorithm are presented, and issues related to computational implementation are discussed. Variants of the block conjugate gradient algorithm applicable to symmetric indefinite matrices are also developed.     

隐式重启精化全局Lanczos方法

The numerical methods for solving large symmetric eigenvalue problems are considered in this paper.Based on the global Lanczos process,a global Lanczos method for solving large symmetric eigenvalue problems is presented.In order to accelerate the convergence of the F-Ritz vectors,the refined global Lanczos method is developed.Combining the implicitly restarted strategy with the deflation technique,an implicitly restarted and refined global Lanczos method for computing some eigenvalues of large symmetric matrices is proposed.Numerical results show that the proposed methods are efficient.     

PRECONDITIONING BLOCK LANCZOS ALGORITHM FOR SOLVING SYMMETRIC EIGENVALUE PROBLEMS

1. Introduction;The Lanczos process is an effective method [1, 2, 14, 21] for computing a feweigenValues and corresponding eigenvectors of a large sparse symmetric matrix A ERnxn. If it is practical to factor the matrix A -- PI for one or more values of p near thedesired eigenvalues, the Lanczos method can be used with the inverted operator andconvergence will be very rapid[5,10,22]. In practical applications, however, the matrixA is usually large and sparse, so factoring A is either impos…     

TWO ALGORITHMS FOR SYMMETRIC LINEAR SYSTEMS WITH MULTIPLE RIGHT-HAND SIDES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｍａｎｙａｐｐｌｉｃａｔｉｏｎｓｗｅｎｅｅｄｔｏｓｏｌｖｅｍｕｌｔｉｐｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓＡｘ(ｉ) =ｂ(ｉ) ,ｉ=1,… ,ｓ (1)ｗｉｔｈｔｈｅｓａｍｅｎ×ｎｒｅａｌｓｙｍｍｅｔｒｉｃｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘＡ ,ｂｕｔｓｄｉｆｆｅｒｅｎｔｒｉｇｈｔ ｈａｎｄｓｉｄｅｓｂ(ｉ) (ｉ=1,… ,ｓ) .Ｉｆａｌｌｏｆｔｈｅｒｉｇｈｔ ｈａｎｄｓｉｄｅｓａｒｅａｖａｉｌａｂｌｅｓｉｍｕｌｔａｎｅｏｕｓｌｙ ,ｔｈｅｎｔｈｅｓｅｓｌｉｎｅａｒｓｙｓｔｅ…     

The use of a refined error bound when updating eigenvalues of tridiagonals

The Lanczos algorithm is used to compute some eigenvalues of a given symmetric matrix of large order. At each step of the Lanczos algorithm it is valuable to know which eigenvalues of the associated tridiagonal matrix have stabilized at eigenvalues of the given symmetric matrix. We present a robust algorithm which is fast (20j to 40j operations at the jth Lanczos step), uses about 30 words of extra storage, and has a fairly short program (approxiamately 200 executable statements)     

On the Lanczos and Golub–Kahan reduction methods applied to discrete ill‐posed problems

The symmetric Lanczos method is commonly applied to reduce large‐scale symmetric linear discrete ill‐posed problems to small ones with a symmetric tridiagonal matrix. We investigate how quickly the nonnegative subdiagonal entries of this matrix decay to zero. Their fast decay to zero suggests that there is little benefit in expressing the solution of the discrete ill‐posed problems in terms of the eigenvectors of the matrix compared with using a basis of Lanczos vectors, which are cheaper to compute. Similarly, we show that the solution subspace determined by the LSQR method when applied to the solution of linear discrete ill‐posed problems with a nonsymmetric matrix often can be used instead of the solution subspace determined by the singular value decomposition without significant, if any, reduction of the quality of the computed solution. Copyright © 2015 John Wiley & Sons, Ltd.     

Dealing with linear dependence during the iterations of the restarted block Lanczos methods

The Lanczos method can be generalized to block form to compute multiple eigenvalues without the need of any deflation techniques. The block Lanczos method reduces a general sparse symmetric matrix to a block tridiagonal matrix via a Gram–Schmidt process. During the iterations of the block Lanczos method an off-diagonal block of the block tridiagonal matrix may become singular, implying that the new set of Lanczos vectors are linearly dependent on the previously generated vectors. Unlike the single vector Lanczos method, this occurrence of linearly dependent vectors may not imply an invariant subspace has been computed. This difficulty of a singular off-diagonal block is easily overcome in non-restarted block Lanczos methods, see [12,30]. The same schemes applied in non-restarted block Lanczos methods can also be applied in restarted block Lanczos methods. This allows the largest possible subspace to be built before restarting. However, in some cases a modification of the restart vectors is required or a singular block will continue to reoccur. In this paper we examine the different schemes mentioned in [12,30] for overcoming a singular block for the restarted block Lanczos methods, namely the restarted method reported in [12] and the Implicitly Restarted Block Lanczos (IRBL) method developed by Baglama et al. [3]. Numerical examples are presented to illustrate the different strategies discussed.     

Upper (lower) bounds of the eigenvalues,spread and the open problems for the real symmetric interval matrices

This work is concerned with exploring the upper bounds and lower bounds of the eigenvalues of real symmetric matrices of order n whose entries are in a given interval. It gives the maximum and minimum of the eigenvalues and the upper bounds of spread of real symmetric interval matrices in all cases. It also gives the answers of the open problems for the maximum and minimum of the eigenvalues of real symmetric interval matrices. Copyright © 2012 John Wiley & Sons, Ltd.     

Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices

It is shown that the method of Arnoldi can be successfully used for solvinglarge unsymmetric eigenproblems. Like the symmetric Lanczos method, Arnoldi's algorithm realizes a projection process onto the Krylov subspace K_m spanned by v₁,Av₁,...,A^m?1v₁, where v₁ is the initial vector. We therefore study the convergence of the approximate eigenelements obtained by such a process. In particular, when the eigenvalues of A are real, we obtain bounds for the rates of convergence similar to those for the symmetric Lanczos algorithm. Some practical methods are presented in addition to that of Arnoldi, and several numerical experiments are described.     

Extending the eigCG algorithm to nonsymmetric Lanczos for linear systems with multiple right‐hand sides

The technique that was used to build the eigCG algorithm for sparse symmetric linear systems is extended to the nonsymmetric case using the BiCG algorithm. We show that, similar to the symmetric case, we can build an algorithm that is capable of computing a few smallest magnitude eigenvalues and their corresponding left and right eigenvectors of a nonsymmetric matrix using only a small window of the BiCG residuals while simultaneously solving a linear system with that matrix. For a system with multiple right‐hand sides, we give an algorithm that computes incrementally more eigenvalues while solving the first few systems and then uses the computed eigenvectors to deflate BiCGStab for the remaining systems. Our experiments on various test problems, including Lattice QCD, show the remarkable ability of eigBiCG to compute spectral approximations with accuracy comparable with that of the unrestarted, nonsymmetric Lanczos. Furthermore, our incremental eigBiCG followed by appropriately restarted and deflated BiCGStab provides a competitive method for systems with multiple right‐hand sides. Copyright © 2013 John Wiley & Sons, Ltd.     

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.     

Tracking the Progress of the Lanczos Algorithm for Large Symmetric Eigenproblems

A reliable and efficient algorithm for finding all or part ofthe spectrum (set of eigenvalues without regard to multiplicity)of a large symmetric matrix A may be based on the Lanczos algorithm,by tracking the progress of the eigenvalues of the Lanczos tridiagonalmatrices towards the eigenvalues of A. Rather than using routinesfor computing eigenvalues of tridiagonal matrices, we run recurrenceson sets of points within and near the wanted part of the spectrum.Interpolation procedures are used at these points in order toestimate the actual positions of eigenvalues. New points areadded and old ones are discarded according to the way the eigenvaluesconverge. The goal is to recognize convergence automaticallyand keep small the number of Lanczos steps, each of which demandsaccess to the whole of the large matrix A. Results of computerruns are reported.     

Use of the Lanczos Method for Finding Complete Sets of Eigenvalues of Large Sparse Symmetric Matrices

A way of using the Lanczos method to find all the eigenvaluesof a large sparse symmetric matrix is described, and some empiricalobservations on the manner in which the method works in practiceare given. The method seems to be accurate, fast, and not verydemanding on storage. A formula for the number of iterationsnecessary to get the eigenvalues is proposed.     

由谱数据数值稳定地构造实对称带状矩阵

§1.引言 设r,n是正整数并且0r有a_(ij)=0.     

Application of the Lanczos algorithm for solving the linear systems that occur in continuation problems

We study the Lanczos method for solving symmetric linear systems with multiple right‐hand sides. First, we propose a numerical method of implementing the Lanczos method, which can provide all approximations to the solution vectors of the remaining linear systems. We also seek possible application of this algorithm for solving the linear systems that occur in continuation problems. Sample numerical results are reported. Copyright © 2002 John Wiley & Sons, Ltd.     

A numerical solution of the constrained weighted energy problem

A numerical algorithm is presented to solve the constrained weighted energy problem from potential theory. As one of the possible applications of this algorithm, we study the convergence properties of the rational Lanczos iteration method for the symmetric eigenvalue problem. The constrained weighted energy problem characterizes the region containing those eigenvalues that are well approximated by the Ritz values. The region depends on the distribution of the eigenvalues, on the distribution of the poles, and on the ratio between the size of the matrix and the number of iterations. Our algorithm gives the possibility of finding the boundary of this region in an effective way.We give numerical examples for different distributions of poles and eigenvalues and compare the results of our algorithm with the convergence behavior of the explicitly performed rational Lanczos algorithm.     

A PROCESS FOR SOLVING A FEW EXTREME EIGENPAIRS OF LARGE SPARSE POSITIVE DEFINITE GENERALIZED EIGENVALUE PROBLEM

1. IntroductionWe are concerned in this work with finding a few extreme eigenvalues and theircorresponding eigenvectors of a generalized large scale eigenvalue problem in which thematrices are sparse and symmetric positive definite.Although finding a few extreme eigenpairs is of interest both in theory and practice,there are only few usable and efficient methods up to now. Reinsch and Baner ([12]),suggested a oR algorithm with Newton shift for the standard eigenproblem which included an ingen…