## Numerical Linear Algebra

 Unit code: MATH46101 Credit Rating: 15 Unit level: Level 4 Teaching period(s): Semester 1 Offered by School of Mathematics Available as a free choice unit?: N

#### Requisites

None

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.

#### 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 uses MATLAB as tool for expressing and implementing algorithms and describes some of the key ideas used in developing high-performance linear algebra codes. Applications, such as machine learning and search engines, will be introduced throughout the module.

#### Teaching and learning methods

30 lectures (two or three lectures per week), with a fortnightly examples class.

#### 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.

#### Assessment methods

• Other - 20%
• Written exam - 80%

#### Assessment Further Information

• Mid-semester coursework: 20%
• End of semester examination: three hours weighting 80%

#### Syllabus

1. Basics. Summary/recap of basic concepts from linear algebra and numerical analysis: matrices, operation counts. Matrix multiplication, block matrices. [4]

Matrix norms. Linear system sensitivity. [2]

2. Matrix factorizations. Cholesky factorization. QR factorization by Householder matrices and by Givens rotations. [3]

LU factorization and Gaussian elimination; partial pivoting. Solving triangular systems by substitution. Solving full systems by factorization. Error analysis. Complete pivoting, rook pivoting. Numerical examples. [4]

3. Sparse and banded linear systems and iterative methods. Storage schemes for banded and sparse matrices.  LU Factorization, Markowitz pivoting. [2]

Iterative methods: Jacobi, Gauss-Seidel and SOR iterations. Kronecker product. Krylov subspace methods, conjugate gradient method. Preconditioning. [4]

4. Linear least squares problem. Basic theory using singular value decomposition (SVD) and pseudoinverse. Perturbation theory. Numerical solution: normal equations. SVD and rank deficiency.  [3]

5. Eigenvalue problem. Basic theory, including perturbation results. Power method, inverse iteration. Similarity reduction. QR algorithm. [5]

[1] 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.

[2] James W. Demmel, Applied Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1997, ISBN 0-89871-389-7, xi+419pp.

[3] Gene H. Golub and Charles F. Van~Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, MD, USA, fourth edition, 2013, ISBN 978-1-4214-0794-4. xxi+756pp.

[4] Desmond J. Higham and Nicholas J. Higham, MATLAB Guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, third edition, 2017, ISBN 978-1-61197-465-2. xxvi+476pp.

[5] 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.

[6] Yousef Saad. Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, second edition, 2003. ISBN 0-89871-534-2. xviii+528pp.

[7] G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973, ISBN 0-12-670350-7, xiii+441pp.

[8] 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.

[9] 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.

[10] 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.

[11] David S. Watkins, Fundamentals of Matrix Computations, Wiley, New York, third edition, 2010, ISBN 978-0-470-52833-4. xvi+644pp.

#### 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.

#### Study hours

• Assessment practical exam - 40 hours
• Lectures - 30 hours
• Tutorials - 12 hours
• Independent study hours - 68 hours

#### Teaching staff

Nicholas Higham - Unit coordinator

Francoise Tisseur - Unit coordinator