NUMERICAL METHODS FOR LARGE EIGENVALUE PROBLEMS

1 NUMERICAL METHODS FOR LARGEEIGENVALUE PROBLEMS Second editionYousef SaadCopyrightc 2011 bythe Society for Industrial and Applied MathematicsContentsPreface to Classics EditionxiiiPrefacexv1 Background in Matrix Theory and Linear .. Matrices and Eigenvalues .. of Matrices .. with Special Srtuctures .. Matrices .. Inner Products and Norms .. Norms .. Vectors and Subspaces .. Forms of Matrices .. to the Diagonal Form .. Jordan Canonical Form .. Schur Canonical Form .. and Hermitian Matrices .. Matrices .. Matrices.

2 Matrices ..252 Sparse .. Schemes .. Sparse Matrix Operations .. Direct Solution METHODS .. PROBLEMS .. Walk Problem .. Reactions .. Harwell-Boeing Collection .. New Sparse Matrix Repositories .. Matrices in Matlab ..433 Perturbation Theory and Error and their Properties .. Projectors .. Projectors .. and Spectral Projector .. with the Jordan form .. Perturbations ofA.. Error Bounds .. Error Bounds .. Hermitian Case .. Kahan-Parlett-Jiang Theorem .. of Eigen- PROBLEMS .. of Eigenvalues .. of Eigenvectors.

3 Of Invariant Subspaces .. Theorems ..794 The Tools of Spectral Vector Iterations .. Power Method .. Shifted Power Method .. Iteration .. Techniques .. Deflation with One Vector .. in Wieldant s Deflation .. with Several Vectors.. Schur Decomposition.. Deflation Procedures .. Projection METHODS .. Projection METHODS .. Hermitian Case .. Projection METHODS .. Polynomials .. Chebyshev Polynomials .. Chebyshev Polynomials .. 1095 Subspace Subspace Iteration .. Iteration with Projection .. Implementations.

4 Shifts .. 1236 Krylov Subspace Subspaces .. s Method .. Basic Algorithm .. Implementations .. of Implicit Deflation .. Hermitian Lanczos Algorithm .. Algorithm .. with Orthogonal Polynomials .. Lanczos Algorithm .. Algorithm .. Implementations .. Krylov METHODS .. of the Lanczos Process .. betweenKmand an Eigenvector .. of the Eigenvalues .. of the Eigenvectors .. of the Arnoldi Process .. 1517 Filtering and Restarting Filtering .. Restarted Arnoldi s Method .. Restarted Arnoldi s Method.

5 Filter Polynomials? .. Iteration .. Properties.. an Optimal Ellipse .. Subspace Iteration .. the Best Ellipse.. Squares - Arnoldi .. Least Squares Polynomial .. of Chebyshev Bases .. Gram Matrix .. the Best Polynomial .. Squares Arnoldi Algorithms .. 1888 Preconditioning Preconditioning .. Concepts .. with Complex Arithmetic .. Arnoldi .. Preconditioning .. s Method .. Jacobi-Davidson approach .. s Method .. with Newton s Method .. Jacobi-Davidson Approach.

6 CMS AMLS connection .. and the Correction Equation .. Schur Complements .. Projection Viewpoint .. 2159 Non-Standard EIGENVALUE .. EIGENVALUE PROBLEMS .. Results .. to Standard Form .. METHODS .. Hermitian Definite Case .. PROBLEMS .. Quadratic to Generalized PROBLEMS .. 23210 Origins of Matrix EIGENVALUE .. Vibrations .. Networks.. Structure Calculations .. descriptions of matter .. Hartree approximation .. Hartree-Fock approximation .. Functional Theory .. Kohn-Sham equation.

7 Of Dynamical Systems .. Analysis .. Reactions .. Chain Models .. 255 References259 Index271 Preface to the Classics EditionThis is a revised edition of a book which appeared close to twodecades scrutinizing how the field has evolved in these two decades will maketwo interesting observations. On the one hand the observer will be struck by thestaggering number of new developments in NUMERICAL linear algebra during thisperiod. The field has evolved in all directions: theory, algorithms, software, andnovel applications. Two decades ago there was essentially no publically availablesoftware for LARGE EIGENVALUE PROBLEMS .

8 Today one has a flurry to choose fromand the activity in software development does not seem to be abating. A numberof new algorithms appeared in this period as well. I can mention at the outset theJacobi-Davidson algorithm and the idea of implicit restarts, both discussed in thisbook, but there are a few others. The most interesting development to the numeri-cal analyst may be the expansion of the realm of EIGENVALUE techniques into newerand more challenging applications. Or perhaps, the more correct observation isthat these applications were always there, but they were notas widely appreciatedor understood by NUMERICAL analysts, or were not fully developed due to lack second observation to be made when comparing the state ofthe field nowand two decades ago is that at the same time the basic tools used to compute spec-tra have essentially not changed much.

9 Krylov subspaces arestill the whole, the new METHODS that have been developed consist of enhance-ments to these basic METHODS , sometimes major, in the form ofpreconditioners, orother variations. One might say that the field has evolved even more from gainingmaturity than from the few important developments which took place. This ma-turity has been brought about by the development of practical algorithms and bysoftware. Therefore, synergetic forces played a major role: new algorithms, en-hancements, and software packages were developed which enabled new interestfrom practitioners, which in turn sparkled demand and additional interest from thealgorithm light of this observation, I have grouped the 10 chapters of the first editioninto three categories.

10 In the first group are those chapters that are of a theoreti-cal nature (Chapters 1, 3, and 9). These have undergone smallchanges such ascorrecting errors, improving the style, and adding second group includes a few chapters that describe basicalgorithms orconcepts for example subspace iteration (Chapter 5) or thetools of spectralxiiixivPREFACE TO THECLASSICSEDITION approximation (Chapter 4). These have been left unchanged or have receivedsmall updates. Chapters 2 and 10 are also in this group which then consists ofChapters 2, 4, 5, and in the third group (chapters 6 to 8) underwent the biggest describe algorithms and their implementations.