Numerical Linear Algebra
|Unit level:||Level 6|
|Teaching period(s):||Semester 1|
|Offered by||School of Mathematics|
|Available as a free choice unit?:||N
Students are not permitted to take, for credit, MATH46101 in an undergraduate programme and then MATH66101 in a postgraduate programme at the University of Manchester, as the courses are identical.
To develop understanding of modern methods of numerical linear algebra for solving linear systems, least squares problems and the eigenvalue problem.
This module treats the main classes of problems in numerical linear algebra: linear systems, least square problems, and eigenvalue problems, covering both dense and sparse matrices. It provides analysis of the problems along with algorithms for their solution. It also introduces MATLAB as tool for expressing and implementing algorithms and describes some of the key ideas used in developing high-performance linear algebra codes (blocking, BLAS). Applications will be introduced throughout the module.
On successful completion of this course unit students will
- understand the concepts of efficiency and stability of algorithms in numerical linear algebra;
- understand the importance of matrix factorizations, and know how to construct some key factorizations using elementary transformations;
- be familiar with some important methods for solving linear systems, least squares problems, and the eigenvalue problem;
- appreciate the issues involved in the choice of algorithm for particular problems (sparsity, structure, etc.);
- appreciate the basic concepts involved in the efficient implementation of algorithms in a high-level language.
- Other - 25%
- Written exam - 75%
Assessment Further Information
- Mid-semester coursework: 25%
- End of semester examination: three hours weighting 75%
- Introduction. Summary/recap of basic concepts from linear algebra and numerical analysis: matrices, operation counts. [1 lecture]. Introduction to MATLAB. . Matrix norms. Linear system sensitivity. 
- Matrix factorizations. Cholesky factorization. QR factorization by Householder matrices and by Givens rotations. . LU factorization and Gaussian elimination; partial pivoting. Error analysis. . Block algorithms and their suitability for modern machine architectures. . The BLAS and LAPACK. 
- Linear systems. Solving triangular systems by substitution. Solving full systems by factorization. Application: Newton's method for nonlinear systems. 
- Sparse and banded linear systems and iterative methods. LU factorization for banded and sparse matrices. Storage schemes. . Iterative methods: Jacobi, Gauss-Seidel and SOR iterations. Krylov subspace methods, conjugate gradient method. Preconditioning. Application: differential equations. 
- Linear least squares problem. Basic theory using singular value decomposition (SVD) and pseudoinverse. Perturbation theory. Numerical solution: normal equations. SVD and rank deficiency. Application: image deblurring. 
- Eigenvalue problem. Basic theory, including perturbation results. Power method, inverse iteration. Similarity reduction. QR algorithm. Application: Google PageRank. 
-  Timothy A. Davis, Direct Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2006, ISBN 0-89871-613-6, xii+217pp.
-  James W. Demmel, Applied Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1997, ISBN 0-89871-389-7, xi+419pp.
-  Gene H. Golub and Charles F. Van~Loan, Matrix Computations Johns Hopkins University Press, Baltimore, MD, USA, third edition, 1996, ISBN 0-8018-5413-X (hardback), 0-8018-5414-8 (paperback), xxvii+694pp.
-  Desmond J. Higham and Nicholas J. Higham, MATLAB Guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, second edition, 2005, ISBN 0-89871-578-4, xxiii+382pp.
-  Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, second edition, 2002, ISBN 0-89871-521-0, xxx+680pp.
-  G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973, ISBN 0-12-670350-7, xiii+441pp.
-  G. W. Stewart, Matrix Algorithms, Volume I: Basic Decompositions, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1998, ISBN 0-89871-414-1, xx+458pp.
-  G. W. Stewart, Matrix Algorithms, Volume II: Eigensystems, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001, ISBN 0-89871-503-2, xix+469pp.
-  Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1997, ISBN 0-89871-361-7, xii+361pp.
-  David S. Watkins, Fundamentals of Matrix Computations, Wiley, New York, second edition, 2002, ISBN 0-471-21394-2, xiii+618pp.
-  Per Christian Hansen, James G. Nagy, and Dianne P. O'Leary, Deblurring Images: Matrices, Spectra, and Filtering, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2006, ISBN 0-89871-618-7, xiv+130pp.
-  C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1995, ISBN 0-89871-352-8, xiii+165pp.
-  Amy N. Langville and Carl D. Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, NJ, USA, 2006, ISBN 0-691-12202-4, x+224 pp.
Books  -  cover the core material, while  -  cover the applications.
Feedback tutorials will provide an opportunity for students' work to be discussed and provide feedback on their understanding. Coursework or in-class tests (where applicable) also provide an opportunity for students to receive feedback. Students can also get feedback on their understanding directly from the lecturer, for example during the lecturer's office hour.
- Lectures - 22 hours
- Tutorials - 11 hours
- Independent study hours - 117 hours