- •1 Introduction
- •1.1 What makes eigenvalues interesting?
- •1.2 Example 1: The vibrating string
- •1.2.1 Problem setting
- •1.2.2 The method of separation of variables
- •1.3.3 Global functions
- •1.3.4 A numerical comparison
- •1.4 Example 2: The heat equation
- •1.5 Example 3: The wave equation
- •1.6 The 2D Laplace eigenvalue problem
- •1.6.3 A numerical example
- •1.7 Cavity resonances in particle accelerators
- •1.8 Spectral clustering
- •1.8.1 The graph Laplacian
- •1.8.2 Spectral clustering
- •1.8.3 Normalized graph Laplacians
- •1.9 Other sources of eigenvalue problems
- •Bibliography
- •2 Basics
- •2.1 Notation
- •2.2 Statement of the problem
- •2.3 Similarity transformations
- •2.4 Schur decomposition
- •2.5 The real Schur decomposition
- •2.6 Normal matrices
- •2.7 Hermitian matrices
- •2.8 Cholesky factorization
- •2.9 The singular value decomposition (SVD)
- •2.10 Projections
- •2.11 Angles between vectors and subspaces
- •Bibliography
- •3 The QR Algorithm
- •3.1 The basic QR algorithm
- •3.1.1 Numerical experiments
- •3.2 The Hessenberg QR algorithm
- •3.2.1 A numerical experiment
- •3.2.2 Complexity
- •3.3 The Householder reduction to Hessenberg form
- •3.3.2 Reduction to Hessenberg form
- •3.4 Improving the convergence of the QR algorithm
- •3.4.1 A numerical example
- •3.4.2 QR algorithm with shifts
- •3.4.3 A numerical example
- •3.5 The double shift QR algorithm
- •3.5.1 A numerical example
- •3.5.2 The complexity
- •3.6 The symmetric tridiagonal QR algorithm
- •3.6.1 Reduction to tridiagonal form
- •3.6.2 The tridiagonal QR algorithm
- •3.7 Research
- •3.8 Summary
- •Bibliography
- •4.1 The divide and conquer idea
- •4.2 Partitioning the tridiagonal matrix
- •4.3 Solving the small systems
- •4.4 Deflation
- •4.4.1 Numerical examples
- •4.6 Solving the secular equation
- •4.7 A first algorithm
- •4.7.1 A numerical example
- •4.8 The algorithm of Gu and Eisenstat
- •4.8.1 A numerical example [continued]
- •Bibliography
- •5 LAPACK and the BLAS
- •5.1 LAPACK
- •5.2 BLAS
- •5.2.1 Typical performance numbers for the BLAS
- •5.3 Blocking
- •5.4 LAPACK solvers for the symmetric eigenproblems
- •5.6 An example of a LAPACK routines
- •Bibliography
- •6 Vector iteration (power method)
- •6.1 Simple vector iteration
- •6.2 Convergence analysis
- •6.3 A numerical example
- •6.4 The symmetric case
- •6.5 Inverse vector iteration
- •6.6 The generalized eigenvalue problem
- •6.7 Computing higher eigenvalues
- •6.8 Rayleigh quotient iteration
- •6.8.1 A numerical example
- •Bibliography
- •7 Simultaneous vector or subspace iterations
- •7.1 Basic subspace iteration
- •7.2 Convergence of basic subspace iteration
- •7.3 Accelerating subspace iteration
- •7.4 Relation between subspace iteration and QR algorithm
- •7.5 Addendum
- •Bibliography
- •8 Krylov subspaces
- •8.1 Introduction
- •8.3 Polynomial representation of Krylov subspaces
- •8.4 Error bounds of Saad
- •Bibliography
- •9 Arnoldi and Lanczos algorithms
- •9.2 Arnoldi algorithm with explicit restarts
- •9.3 The Lanczos basis
- •9.4 The Lanczos process as an iterative method
- •9.6 Partial reorthogonalization
- •9.5 An error analysis of the unmodified Lanczos algorithm
- •9.7 Block Lanczos
- •9.8 External selective reorthogonalization
- •Bibliography
- •10 Restarting Arnoldi and Lanczos algorithms
- •10.2 Implicit restart
- •10.3 Convergence criterion
- •10.4 The generalized eigenvalue problem
- •10.5 A numerical example
- •10.6 Another numerical example
- •10.7 The Lanczos algorithm with thick restarts
- •10.8 Krylov–Schur algorithm
- •10.9 The rational Krylov space method
- •Bibliography
- •11 The Jacobi-Davidson Method
- •11.1 The Davidson algorithm
- •11.2 The Jacobi orthogonal component correction
- •11.2.1 Restarts
- •11.2.2 The computation of several eigenvalues
- •11.2.3 Spectral shifts
- •11.3 The generalized Hermitian eigenvalue problem
- •11.4 A numerical example
- •11.6 Harmonic Ritz values and vectors
- •11.7 Refined Ritz vectors
- •11.8 The generalized Schur decomposition
- •11.9.1 Restart
- •11.9.3 Algorithm
- •Bibliography
- •12 Rayleigh quotient and trace minimization
- •12.1 Introduction
- •12.2 The method of steepest descent
- •12.3 The conjugate gradient algorithm
- •12.4 Locally optimal PCG (LOPCG)
- •12.5 The block Rayleigh quotient minimization algorithm (BRQMIN)
- •12.7 A numerical example
- •12.8 Trace minimization
- •Bibliography
240CHAPTER 12. RAYLEIGH QUOTIENT AND TRACE MINIMIZATION
2.Multiple dynamic shifts. Each linear system (12.57) is solved with an individual shift. The shift is ‘turned on’ close to convergence. Since the linear systems are indefinite, PCG has to be adapted.
3.Preconditioning. The linear systems (12.57) can be preconditioned, e.g., by a matrix of the form M = CC where CC ≈ A is an incomplete Cholesky factorization. One then solves
(12.57) |
P˜(A˜ − σi(k)M˜ )P˜d˜i(k) = P˜˜ri, X˜k M˜ d˜i(k) = 0 |
˜ −1 − ˜ −1 − ˜(k)
with A = C AC , M = C MC , di
˜ − ˜ ˜ ˜ ˜ 2 ˜ −1 ˜ ˜ and P = I MXk(Xk M Xk) Xk M.
(k) ˜ (k) (k)
= C di , Xk = C Xk, x˜i = C xi ,
In Table 12.2 results are collected for some problems in the Harwell-Boeing collection [10]. These problems are di cult because the gap ratios for the smallest eigenvalues are extremely small due to the huge span of the spectra. Without preconditioning, none of these problems can be solved with a reasonable cost. In the experiments, the incomplete Cholesky factorization (IC(0)) of A was used as the preconditioner for all the matrices of the form A − σB.
Problem |
Size |
Max # |
Block Jacobi-Davidson |
Davidson-type tracemin |
||||
|
|
inner its |
#its |
A mults |
time[sec] |
#its |
A mults |
time[sec] |
|
|
|
|
|
|
|
|
|
BCSST08 |
1074 |
40 |
34 |
3954 |
4.7 |
10 |
759 |
0.8 |
BCSST09 |
1083 |
40 |
15 |
1951 |
2.2 |
15 |
1947 |
2.2 |
BCSST11 |
1473 |
100 |
90 |
30990 |
40.5 |
54 |
20166 |
22.4 |
BCSST21 |
3600 |
100 |
40 |
10712 |
35.1 |
39 |
11220 |
36.2 |
BCSST26 |
1922 |
100 |
60 |
21915 |
32.2 |
39 |
14102 |
19.6 |
Table 12.2: Numerical results for problems from the HarwellBoeing collection with four processors
The Davidson-type trace minimization algorithm with multiple dynamic shifts works better than the block Jacobi–Davidson algorithm for three of the five problems. For the other two, the performance for both algorithms is similar.
Bibliography
[1]P. ARBENZ, U. L. HETMANIUK, R. B. LEHOUCQ, AND R. TUMINARO, A comparison
of eigensolvers for large-scale 3D modal analysis using AMG-preconditioned iterative methods, Internat. J. Numer. Methods Eng., 64 (2005), pp. 204–236.
[2]O. AXELSSON AND V. BARKER, Finite Element Solution of Boundary Value Problems, Academic Press, Orlando FL, 1984.
[3]D. K. FADDEEV AND V. N. FADDEEVA, Computational Methods of Linear Algebra, Freeman, San Francisco, 1963.
[4]Y. T. FENG AND D. R. J. OWEN, Conjugate gradient methods for solving the smallest eigenpair of large symmetric eigenvalue problems, Internat. J. Numer. Methods Eng., 39 (1996), pp. 2209–2229.
BIBLIOGRAPHY |
241 |
[5]M. R. HESTENES AND E. STIEFEL, Methods of conjugent gradients for solving linear systems, J. Res. Nat. Bur. Standards, 49 (1952), pp. 409–436.
[6]A. V. KNYAZEV, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23 (2001), pp. 517–541.
[7]A. V. KNYAZEV, M. E. ARGENTATI, I. LASHUK, AND E. E. OVTCHINNIKOV, Block
locally optimal preconditioned eigenvalue Xolvers (BLOPEX) in hypre and PETSc, SIAM J. Sci. Comput., 29 (2007), pp. 2224–2239.
[8]D. E. LONGSINE AND S. F. MCCORMICK, Simultaneous Rayleigh–quotient minimization methods for Ax = λBx, Linear Algebra Appl., 34 (1980), pp. 195–234.
[9]A. RUHE, Computation of eigenvalues and vectors, in Sparse Matrix Techniques, V. A. Barker, ed., Lecture Notes in Mathematics 572, Berlin, 1977, Springer, pp. 130–184.
[10]A. SAMEH AND Z. TONG, The trace minimization method for the symmetric generalized eigenvalue problem, J. Comput. Appl. Math., 123 (2000), pp. 155–175.
[11]A. H. SAMEH AND J. A. WISNIEWSKI, A trace minimization algorithm for the generalized eigenvalue problem, SIAM J. Numer. Anal., 19 (1982), pp. 1243–1259.
[12]H. R. SCHWARZ, Rayleigh–Quotient–Minimierung mit Vorkonditionierung, in Numerical Methods of Approximation Theory, Vol. 8, L. Collatz, G. Meinardus, and G. N¨urnberger, eds., vol. 81 of International Series of Numerical Mathematics (ISNM), Basel, 1987, Birkh¨auser, pp. 229–45.
[13]G. L. G. SLEIJPEN AND H. A. VAN DER VORST, Jacobi–Davidson method, in Templates for the solution of Algebraic Eigenvalue Problems: A Practical Guide, Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., SIAM, Philadelphia, PA, 2000, pp. 238–246.