Warning: Your browser doesn't support all of the features in this Web site. Please view our accessibility page for more details.
Lecturer:  Dr Niall Madden 

Lectures:  Monday at 12.00 Monday at 15.00 Wednesday at 11.00 Classes take place in ADB1020. 

Starts:  Tuesday, Jan 14, at 11.00.  
Lecture summaries:  see below.  
Credits:  10 ECTS (a 5 ECTS variant may be available to students in structured PhD programmes).  
Overview:  This module is concerned with the mathematics of algorithms for
the numerical solution of sparse linear systems by direct and iterative
methods, and estimation of eigenvalues. It is aimed at graduate students (taught Masters and structured PhD programmes) in mathematical and computational sciences. 
A matrix is sparse it has sufficiently few nonzero entries that this fact is worth exploiting when preforming computations. Most matrices that the working scientists encounters, whether through the discretization of partial differential equations, or the representation of graphs and networks, are sparse.
In this module, our primary interest is in the construction, analysis and implementation of direct and iterative methods for the solution of linear systems of equations, and the estimation of eigenvalues and eigenvectors.
We'll begin with some motivating examples, with a particular emphasis on how sparse matrices arise when implementing finite different and finite element methods, and representing graphs
This will be followed by a study of some fundamental ideas (orthogonality, norms, the Singular Value Decomposition, condition numbers...)
We then look at the direct solution of linear systems using Gaussian Elimination, and its variants (e.g., Cholesky Factorisation, Thomas Algorithm). This is followed by a study of some iterative techniques (e.g, conjugate gradients, Krylov Sequence Methods, Multigrid methods).
Our learning will be motivated and informed by experimentation. You'll be expected to code many of the algorithms we encounter, and to investigate their properties in practical settings. Our lingua franca will be Matlab/Octave, though you can use any programming language you like. Python (NumPy), C, C++ and Fortran (yes, it is still in use) are particularly useful. I'll also use existing highly optimised libraries, such as the BLAS, LAPACK, CSparse and SuiteSparse (used, for example, in Google's Ceres Solver that underpins Street View and PhotoTours).
For a few interesting articles on applications of methods that will be introduced in this course see
The following contains an unordered list of the main texts for this module. All are published by SIAM and, with the (most unfortunate) exception of Trefethen and Bau, are freely available to you online through NUI Galway's subscription to SIAM ebooks.
Lecture 1:  Introduction to MA519  12pm Monday, 13/01/14  
Lecture 2:  Matrix multiplication  3pm Monday, 13/01/14  
Lecture 3:  Matrix inverse  11am Wednesday, 15/01/14  
Lecture 4:  Norms (Part 1)  12pm Monday, 20/01/14  
Lecture 5:  Norms (Part 2)  3pm Monday, 20/01/14  
Lecture 6:  Unitary matrices and the Frobenious Norm  11am Wednesday, 22/01/14  
Lecture 7:  The singular value decomposition  12pm Monday, 27/01/14  The matlab file used in class  
Lecture 8:  One theorem about the SVD  3pm, Monday 27/01/14  
Lecture 9:  Nine more theorems about the SVD  11am, Wednesday, 29/01/14  
Problem set 1  
Lecture 10:  Solving differential equations  12pm, Monday 03/02/14  
Lecture 11:  Finite Difference Methods (1)  3pm, Monday 03/02/14  
Lecture 12:  Lab: orthogonality, and the SVD  11am, Wednesday 05/02/14  Detailed lab notes  Example files 
Lecture 13:  Finite Difference Methods (2)  12pm, Monday 10/02/14  
Lecture 14:  Finite Differences in 2D  3pm, Monday 10/02/14  
Lecture 15:  Properties of the 2D finite difference matrix  11am, Wednesday 12/02/14  
Lecture 16:  Gaussian Elimination  12pm, Monday 17/02/14  
Lecture 17:  LUfactorisation  3pm, Monday 17/02/14  
Lecture 18:  Symmetric positive definite matrices  11am, Wednesday 19/02/14  
Lecture 19:  Cholesky factorisation  12pm, Monday 24/02/14  
Lecture 20:  Computing Cholesky  3pm, Monday 24/02/14  
Lecture 21:  Sparse Cholesky  11am, Wednesday 26/02/14  
Lab 2:  Programming Cholesky  1pm, Thursday 27/02/14  TestCholesky1.m  
Lecture 22:  The graph of a matrix  12pm, Monday 03/03/14  
Lecture 23:  Analysis of fillin  3pm, Monday 03/03/14  
Lecture 24:  Basic iterative methods  11am, Wednesday 05/03/14  Matlab script for Jacobi and GS  
Lecture 25:  Analysis of basic iterative methods  12pm, Monday 10/03/14  
Lecture 26:  Convergence  3pm, Monday 10/03/14  
Lecture 27:  Detour: the Jordan Canonical Form  11am, Wednesday 12/03/14  
Lecture 28:  Regular splittings  1pm, Tuesday 18/03/14  
Lecture 29:  Nonstationary methods  11am, Monday 24/03/14  
Lecture 30:  Convergence of Orthomin(1)  3pm, Monday 24/03/14  
Lecture 31:  Orthomin(2)  11am, Wednesday 26/03/14  Sorry  no notes typed up yet  
Lab 3:  Iterative Solvers  1pm, Thursday 27/02/14  TestGaussSeidel.m  TestOrthomin1.m 
Lecture 32:  Conjugate Gradients method (CG)  12am, Monday 31/03/14  
Lecture 33:  Analysis of CG  3pm, Monday 31/03/14  
Lecture 34:  Krylov Subspaces  11am, Wednesday 02/04/14  
Bibliography  
All the notes to date in a single file 