CAAM 551 (F) NUMERICAL LINEAR ALGEBRA _____________________________________ 10:00AM - 10:50AM MWF KCK 101 Course Web Page: http://www.caam.rice.edu/~caam551/ Instructor: Dan Sorensen Office: 2035 DH e-mail sorensen@rice.edu (best way to contact me) phone: 5193 Text: Iterative Methods for Sparse Linear Systems (2nd ed.) Y. Saad SIAM Publications Recommended: Numerical Linear Algebra L. Trefethen D. Bau SIAM Publications Matrix Computations (3rd ed.) G. Golub C. Van Loan Johns Hopkins Direct Methods for Sparse Linear Systems T.A. Davis SIAM Publications Prerequisites: CAAM 453 or permission of instructor. Computer programming in Matlab. Experience with one or more of C, F77, F90, C++ is desirable but not essential. %%%%%%%%%%%%%%%%%%%%%%%%%% VERY IMPORTANT %%%%%%%%%%%%%%%%%%%%%%%%% Please send e-mail to sorensen@rice.edu immediately. I will compose a mailing list from this. In your e-mail message, please indicate your major, advisor if you have one, and give a brief description of what you would like to get from the course. COURSE TOPICS -------------- Direct methods for large sparse linear systems Lecture Hours ---------------------------------------------- ------------- Introduction to Sparse Cholesky Factorization .5 Basics of graph representation of sparse matrices 1 and relation to elimination Symmetric Minimum Degree Ordering (and others) 1 Basic algorithm and data structure for Sparse Cholesky 1.5 Survey of modern methods and software (Super LU, Umfpack) 1 The linear least squares problem -------------------------------- Sources of least squares problems .5 Brief review of basic least squares algorithms and geometry .5 Classical Gram Schmidt with DGKS vs Modified Gram Schmidt 1 The SVD solution .5 Regularization 1.5 Principal Component Analysis .5 Error analysis linear equations and least squares ------------------------------------------------- Review of condition number and basic perturbation theory for linear systems .5 Implications for finite precision arithmetic .5 The Backward Error Analysis idea .5 Review Backward Error Analysis of triangular systems, LU decompostion, solution of Ax = b 1 Generalization of perturbation theory to least squares 1.5 Backward error analysis of least squares via Housholder 1 condition estimation .5 Matrix Theory I --------------- Basic definitions .5 Invariant Subspaces, similarity, diagonalizability .5 The Schur Decompostion and consequences .5 The Sylvester Equation .5 Derivation of the spectral decomposition and spectral 1 projectors The Cayley-Hamilton theorem .5 Preconditioned iterative methods for linear systems --------------------------------------------------- Brief review of classic iterative methods .5 The Krylov subspace and the Arnoldi process 1 GMRES derivation .5 Optimality and the GMRES polynomial .5 Two sided Lanczos process 1 QMR, BiCG, BiCGstab 1 The IDR family of iterative methods 1 Pre-Conditioning -- motivated by GMRES optimal polynomial .5 Jacobi, Block Jacobi, ICC, ILU preconditioners -- examples 1 Matrix Theory II ------------- Jordan Normal Form 1 The Courant-Fischer theorem .5 Basic perturbation theory for a simple eigenvalue 1 Field of values -- normal vs. non-normal .5 Pseudo-spectra and interpretations .5 geometry of subspaces, (distance, gap, sep ) 1 Eigenvalue methods ------------------ Single vector methods 1 (Power, Inverse Power, Inverse Iteration) Virtues of orthogonal similarity transformations .5 and reduction to condensed form The implicitly shifted QR algorithm 2 Numerical solution of Sylvester's equation, .5 SVD computation .5 The generalized eigenvalue problem .5 Solution of GEP via QZ algorithm .5 Introduction to methods for large scale eigenvalue problems ----------------------------------------------------------- Krylov Subspace projection and the Arnoldi process 1 Ritz values, Ritz vectors, residual error .5 The Lanczos process 1 Restarting .5 The Implicitly Restarted Arnoldi Method .5 Convergence theory via subspace analysis 1 Introduction to multi-grid methods ---------------------------------- Basic idea of multilevel methods .5 coarse vs fine grid oscillations .5 Basic multigrid step between two grid levels 1 Full multigrid V-cycle .5 Solution of u'' = f in one dimension .5 -------- 42.0