Warning: Your browser doesn't support all of the features in this Web site. Please view our accessibility page for more details.
If you are looking for the page for the current academic year, please see nuigalway.blackboard.com, or contact the module's lecturer.
|Lecturer:||Dr Niall Madden
|Lectures:||Monday at 12.00
Monday at 15.00
Wednesday at 11.00
Classes take place in ADB-1020.
|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.
|Also:||The module is complimented by a workshop at the end of the semester.|
A matrix is sparse it has sufficiently few non-zero 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 on-line through NUI Galway's subscription to SIAM e-books.
|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:||LU-factorisation||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 fill-in||3pm, Monday 03/03/14|
|Lecture 24:||Basic iterative methods||11am, Wednesday 05/03/14||Matlab script for Jacobi and G-S|
|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:||Non-stationary 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|
|All the notes to date in a single file|