CAAM 651: Topics in Numerical Linear Algebra

GMRES, Preconditioning, Multigrid

Spring 2008 · Rice University

MATRICES   //  MATLAB CODES

Admin:	Tuesdays and Thursdays, 4-5:20pm, Humanities 328; Syllabus, poster gmres_tasks1.pdf: a description of the first set of GMRES experiments gmres_report.zip: a zip file with a LaTeX template for your report, along with supporting graphics and macros gmres_tasks2.pdf: a description of the second set of GMRES experiments New: precon_tasks2.pdf: a description of the preconditioning experiments
Lecture 16:	Preconditioners for saddle-point problems, part 2 J. Liesen and B. Parlett. On nonsymmetric saddle point matrices that allow conjugate gradient iterations, Numer. Math. 108 (2008) 605-624. M. Benzi and V. Simoncini. On the eigenvalues of a class of saddle point matrices, Numer. Math. 103 (2006) 173-196. C. Keller, N. I. M. Gould, and A. J. Wathen. Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl. 21 (2000) 1300-1317.
Lecture 15:	Preconditioners for saddle-point problems, part 1 M. Benzi, G. H. Golub, and J. Liesen. Numerical solution of saddle point problems, Acta Numerica 14 (2005) 1-137. H. C. Elman, D. J. Silvester, and A. J. Wathen. Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics, Oxford University Press, 2005. M. F. Murphy, G. H. Golub, and A. J. Wathen. A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comp. 21 (2000) 1969-1972.
Lecture 14:	Sparse approximate inverse preconditioners M. J. Grote and T. Huckle. Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comp. 18 (1997) 838-853. E. Chow. A priori sparsity patterns for parallel sparse approximate inverse preconditioners, SIAM J. Sci. Comp. 21 (2000) 1804-1822. M. Benzi and M. Tuma. A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comp. 19 (1998) 968-994.
Lecture 13:	Incomplete LU factorizations Y. Saad. Iterative Methods for Sparse Linear Systems, Section 10.3, 2nd ed., 2003. (The first edition is available free from the linked website.) M. Benzi. Preconditioning techniques for large linear systems: a survey, J. Comp. Phys. 182 (2002) 418-477.
Lecture 12:	Preconditioning theory and simple preconditioners (Jacobi, Gauss-Seidel, SOR) Y. Saad. Iterative Methods for Sparse Linear Systems, Section 10.2, 2nd ed., 2003. (The first edition is available free from the linked website.)
Lecture 11:	Survey of practical iterations: restarted GMRES, augmented GMRES, BiCGSTAB, QMR, ... Y. Saad. Iterative Methods for Sparse Linear Systems, Chapters 6 and 7, 2nd ed., 2003. (The first edition is available free from the linked website.)
Lecture 10:	Superlinear convergence of GMRES A. van der Sluis and H. A. van der Vorst. The rate of convergence of conjugate gradients, Numer. Math. 48 (1986) 543-560. H. A. van der Vorst and C. Vuik. The superlinear convergence behaviour of GMRES, J. Comp. Appl. Math. 48 (1993) 327-341. Z.-H. Cao. A note on the convergence behavior of GMRES, Applied Num. Math. 25 (1997) 13-20. There is also a literature on superlinear convergence for CG/GMRES on infinite dimensional operators; see, e.g., R. Winther. Some superlinear convergence results for the conjugate gradient method, SIAM J. Num. Anal. 17 (1980) 14-17. I. Moret. A note on the superlinear convergence of GMRES, SIAM J. Num. Anal. 34 (1997) 513-516.
Lecture 9:	Ideal GMRES and polynomial numerical hulls K.-C. Toh. GMRES vs. Ideal GMRES, SIAM J. Matrix Anal. Appl. 18 (1997) 30-36. A. Greenbaum. Generalizations of the field of values useful in the study of polynomial functions of a matrix, Linear Algebra Appl. 347 (2002) 233-249. J. V. Burke and A. Greenbaum. Characterizations of the polynomial numerical hull of degree k, Linear Algebra Appl. 419 (2006) 37-47.
Lecture 8:	Convergence bounds based on pseudospectra L. N. Trefethen. Approximation theory in numerical linear algebra. In Approximation Theory and Numerical Linear Algebra, Algorithms for Approximation II, ed. J. C. Mason and M. G. Cox, Chapman and Hall, London, 1990. (not available online) T. A. Driscoll, K.-C. Toh, L. N. Trefethen. From potential theory to matrix iterations in six steps, SIAM Review 40 (1998) 547-578. L. N. Trefethen and M. Embree. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, Princeton, 2005. See Chapters 2 and 26.
Lecture 7:	Convergence bounds based on the numerical range R. A. Horn and C. R. Johnson. Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991. See Chapter 1. M. Eiermann. Fields of values and iterative methods, Linear Algebra Appl. 180 (1993) 167-197. M. Eiermann and O. G. Ernst. Geometric aspects of the theory of Krylov subspace methods, Acta Numerica 10 (2001) 251-312. B. Beckermann, S. A. Goreinov, and E. E. Tyrtyshnikov. Some remarks on the Elman estimate for GMRES, SIAM J. Matrix Anal. Appl. 27 (2006) 772-778. M. Crouzeix. Numerical range and functional calculus in Hilbert space, J. Functional Anal. 244 (2007) 668-690.
Lecture 6:	Example: tridiagonal Toeplitz matrices L. Reichel and L. N. Trefethen. Eigenvalues and pseudo-eigenvalues of Toeplitz matrices, Linear Algebra Appl. 162-164 (1992) 153-185. J. Liesen and Z. Strakǒs. Convergence of GMRES for Tridiagonal Toeplitz matrices, SIAM J. Matrix Anal. Appl. 26 (2004) 233-251.
Lecture 5:	Limitations of eigenvalue-based convergence analysis A. Greenbaum, V. Pták, Z. Strakǒs. Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl. 17 (1996) 465-469. New: Lecture notes on the Greenbaum, Pták, Strakǒs theorem Catalog of test matrices and codes
Lecture 4:	Eigenvalue-eigenvector bounds for GMRES; Chebyshev polynomials for intervals S. C. Eisenstat, H. C. Elman, M. H. Schultz. Variational iterative methods for nonsymmetric systems of linear equations. SIAM J. Num. Anal. 20 (1983) 345-357. Y. Saad. Iterative Methods for Sparse Linear Systems, Section 6.11.1, 2nd ed., 2003. (The first edition is available free from the linked website.)
Lecture 3:	Roots of the GMRES polynomial and Rayleigh-Ritz eigenvalue estimates R. B. Morgan. Computing interior eigenvalues of large matrices. Linear Algebra Appl. 154-156 (1991) 289-309. R. W. Freund. Quasi-kernel polynomials and their use in non-Hermitian matrix iterations J. Comp. Appl. Math. 43 (1992) 135-158. T. A. Manteuffel and J. S. Otto. On the roots of orthogonal polynomials and residual polynomials associated with a conjugate gradient method. Num. Lin. Alg. Appl. 1 (1994) 449-475. C. Paige, B. Parlett, H. van der Vorst. Approximate solutions and eigenvalue bounds from Krylov subspaces. Num. Lin. Alg. Appl. 2 (1995) 115-133.
Lecture 2:	GMRES Algorithm Y. Saad and M. Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comp. 7 (1986) 856-869. C. Paige and M. Saunders. Solution of sparse indefinite systems of linear equations. SIAM J. Num. Anal. 12 (1975) 617-629.
Lecture 1:	Motivation; Arnoldi algorithm Y. Saad. Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices. Linear Algebra Appl. 34 (1980) 269-295.