MSc Applied Mathematics

Year of entry: 2024

Course unit details:
Numerical Linear Algebra

Course unit fact file
Unit code MATH66101
Credit rating 15
Unit level FHEQ level 7 – master's degree or fourth year of an integrated master's degree
Teaching period(s) Semester 1
Offered by Department of Mathematics
Available as a free choice unit? No

Overview

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.

Pre/co-requisites

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.

Aims

To develop understanding of modern methods of numerical linear algebra for solving linear systems, least squares problems and the eigenvalue problem.

Learning outcomes

On completion of the module, students will be able to

  • construct some key matrix factorizations using elementary transformations,
  • choose an appropriate numerical method to solve systems, least squares problems, and the eigenvalue problem.
  • evaluate and compare the efficiency and numerical stability of different algorithms for solving linear systems, least squares problems, and the eigenvalue problem.
  • design algorithms that exploit matrix structures such as triangularity, sparsity, banded structure, and symmetric positive definiteness,
  • quantify the sensitivity of a linear system or least squares problem to perturbations in the data.

Syllabus

  • Introduction. Summary/recap of basic concepts from linear algebra and numerical analysis: matrices, operation counts. [1 lecture]. Introduction to MATLAB. [2]. Matrix norms. Linear system sensitivity. [2]
  • Matrix factorizations. Cholesky factorization. QR factorization by Householder matrices and by Givens rotations. [5]. LU factorization and Gaussian elimination; partial pivoting. Error analysis. [2]. Block algorithms and their suitability for modern machine architectures. [1]. The BLAS and LAPACK. [1]
  • Linear systems. Solving triangular systems by substitution. Solving full systems by factorization. Application: Newton's method for nonlinear systems. [1]
  • Sparse and banded linear systems and iterative methods. LU factorization for banded and sparse matrices. Storage schemes. [1]. Iterative methods: Jacobi, Gauss-Seidel and SOR iterations. Krylov subspace methods, conjugate gradient method. Preconditioning. Application: differential equations. [4]
  • 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. [5]
  • Eigenvalue problem. Basic theory, including perturbation results. Power method, inverse iteration. Similarity reduction. QR algorithm. Application: Google PageRank. [5]

Assessment methods

Method Weight
Other 20%
Written exam 80%
  • Mid-semester coursework: 20%
  • End of semester examination: weighting 80%

Feedback methods

Feedback tutorials will provide an opportunity for students' work to be discussed and provide feedback on their understanding.  Coursework also provides 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.
 

Recommended reading

Further Reccomended Reading

  • David Gleich, Expanders, Tropical Semi-Rings, and Nuclear Norms: Oh My!, XRDS: Crossroads, The ACM Magazine for Students, 19(3) 32-36, 2013. What does "The Matrix" have to do with "The Social Network"?
  • Desmond J. Higham and Alan Taylor, The Sleekest Link Algorithm, Mathematics Today, 39(6):192-197, 2003. An article explaining the maths begind Google’s PageRank algorithm.
  • Nicholas J. Higham, Cholesky Factorization, WIREs Comp. Stat., 1(2):251-254, 2009.
  • Nicholas J. Higham, Gaussian Elimination, WIREs Comp. Stat., 3(3):230-238, 2011.
  • Nicholas J. Higham, Numerical Linear Algebra and Matrix Analysis, In N. J. Higham, M. R. Dennis, P. Glendinning, P. A. Martin, F. Santosa, and J. Tanner, editors, The Princeton Companion to Applied Mathematics, pages 263-281. Princeton University Press, Princeton, NJ, USA, 2015.
  • Nicholas J. Higham, The Singular Value Decomposition, In N. J. Higham, M. R. Dennis, P. Glendinning, P. A. Martin, F. Santosa, and J. Tanner, editors, The Princeton Companion to Applied Mathematics, pages 126-127. Princeton University Press, Princeton, NJ, USA, 2015.
  • Gilbert Strang, Row Rank Equals Column Rank: Four Approaches, IMAGE (The Bulletin of the International Linear Algebra Society), 53:17, 2014.

Study hours

Scheduled activity hours
Lectures 24
Tutorials 12
Independent study hours
Independent study 114

Teaching staff

Staff member Role
Nicholas Higham Unit coordinator
Francoise Tisseur Unit coordinator

Additional notes

This course unit detail provides the framework for delivery in 20/21 and may be subject to change due to any additional Covid-19 impact.  

Please see Blackboard / course unit related emails for any further updates.

Return to course details