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 .. 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.

2 Perturbations ofA.. Error Bounds .. Error Bounds .. Hermitian Case .. Kahan-Parlett-Jiang Theorem .. of Eigen- PROBLEMS .. of Eigenvalues .. of Eigenvectors .. 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 .. Shifts .. 1236 Krylov Subspace Subspaces .. s Method .. Basic Algorithm .. Implementations .. of Implicit Deflation .. Hermitian Lanczos Algorithm .. Algorithm.

3 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 .. 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.

4 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 .. 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.

5 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 . 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: 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.

6 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. 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).

7 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. Chapters 7 and 8 of thefirst edition contained a mix of topics some of which are less important today,and so some reorganization was needed. I preferred to shorten or reorganize thediscussion of some of these topics rather than remove them altogether, becausemost are not covered in other books. At the same time it was necessary to add afew sections on topics of more recent interest. These include the implicit restarttechniques (inlcuded in Chapter 7) and the Jacobi-Davidsonmethod (included aspart of Chapter 7 on preconditioning techniques). A sectionon AMLS (Auto-matic Multi-Level Substructuring) which has had excellentsuccess in StructuralEngineering has also been included with a goal to link it to other known were left unchanged from the earlier edition, but theNotes and ref-erencessections ending each chapter were systematically notationhas also been altered from the previous edition to reflect more common usage.

8 Forexample, the term null space has been substituted to less common term kernel. An on-line version of this book, along with a few resources such as tutorials,and MATLAB scripts, is posted on my web site; see: , I am indebted to the National Science Foundation and to the Depart-ment of Energy for their support of my research throughout the SaadMinneapolis, January 6, 2011 PrefaceMatrix EIGENVALUE PROBLEMS arise in a LARGE number of disciplines of sciences andengineering. They constitute the basic tool used in designing buildings, bridges,and turbines, that are resistent to vibrations. They allow to model queueing net-works, and to analyze stability of electrical networks or fluid flow. They also allowthe scientist to understand local physical phenonema or to study bifurcation pat-terns in dynamical systems. In fact the writing of this book was motivated mostlyby the second class of books dealing with NUMERICAL METHODS for solving EIGENVALUE prob-lems involving symmetric (or Hermitian) matrices have beenwritten and thereare a few software packages both public and commercial available.

9 The bookby Parlett [148] is an excellent treatise of the problem. Despite a rather strongdemand by engineers and scientists there is little written on nonsymmetric prob-lems and even less is available in terms of software. The 1965book by Wilkinson[222] still constitutes an important reference. Certainly, science has evolved sincethe writing of Wilkinson s book and so has the computationalenvironment andthe demand for solving LARGE matrix PROBLEMS . PROBLEMS are becoming largerand more complicated while at the same time computers are able to deliver everhigher performances. This means in particular that methodsthat were deemed toodemanding yesterday are now in the realm of the achievable. Ihope that this bookwill be a small step in bridging the gap between the literature on what is avail-able in the symmetric case and the nonsymmetric case. Both the Hermitian andthe non-Hermitian case are covered, although non-Hermitian PROBLEMS are givenmore book attempts to achieve a good balance between theory and practice.

10 Ishould comment that the theory is especially important in the nonsymmetric essence what differentiates the Hermitian from the non-Hermitian eigenvalueproblem is that in the first case we can always manage to compute an approxi-mation whereas there are nonsymmetric PROBLEMS that can be arbitrarily difficultto solve and can essentially make any algorithm fail. Statedmore rigorously, theeigenvalue of a Hermitian matrix is always well-conditioned whereas this is nottrue for nonsymmetric matrices. On the practical side, I tried to give a generalview of algorithms and tools that have proved efficient. Manyof the algorithmsdescribed correspond to actual implementations of research software and havebeen tested on realistic PROBLEMS . I have tried to convey ourexperience from thexvxviPREFACE practice in using these a result of the partial emphasis on theory, there are a few chapters thatmay be found hard to digest for readers inexperienced with linear algebra.