CSC2321 Matrix Calculations
announcements for current students and course outline
The first meeting of CSC2321 is Tuesday, September 8, 2026, 17:00-19:00, at MY 320.
Please note that we start at 17:10.Aims
- Review the basic concepts in the numerical solution of linear systems.
- Introduce recent developments in numerical linear algebra / PDEs.
- Develop and study efficient linear solvers, with focus on solvers for large sparse linear systems.
- Implement the above solvers as software.
- Use existing software and higher level environments.
- Analyze the performance of methods and software.
Topics
- Introduction
- Motivation
- Vectors and matrices
- Eigenvalues and eigenvectors
- Norms and inner products
- Block matrices
- Boundary value problems (1-dim) and stencils
- Boundary value problems (2-dim) and stencils
- Stencils and sparsity patterns
- Tensor products of matrices
- Direct methods for solving linear systems
- Gauss elimination, LU factorisation, back and forward substitutions
- Symmetric matrices, symmetric positive definite matrices, Cholesky factorisation
- Banded matrices
- Pivoting
- Sparse matrix storage schemes
- Adjacency graphs and irreducibility
- Iterative methods for solving linear systems
- Introduction
- Richardson, Jacobi, Gauss-Seidel, SOR and SSOR methods
- Block methods
- Convergence of matrices and vectors
- Convergence of iterative methods
- Rate of convergence of iterative methods
- Convergence theorems: Comparison of Jacobi and GS, Diagonal dominant matrices, SPD matrices, Spectral radius of SOR, Consistently ordered matrices - Optimal w for SOR
- Rates of convergence of basic iterative methods on the model problem, Computational issues
- Preconditioning
- Symmetrisable and extrapolated methods
- Polynomial acceleration
- Chebyshev acceleration
- Chebyshev polynomials
- Chebyshev acceleration
- Conjugate gradient acceleration
- The steepest descent method
- The family of Conjugate Direction methods
- The Conjugate Gradient method
- A three-term recurrence relation for CG
- The preconditioned CG method
- Methods for red-black partitioned matrices
- Red-black partitioned matrices
- Chebyshev and CG methods
- Cyclic semi-iterative and CG methods
- Reduced system semi-iterative and CG methods
- Gauss-Seidel and related methods
- The red-black ordering for the 5-point-star matrix
- Multicolor ordering and parallel computation
- Partial Differential Equations
- Schur complement method, arrowhead matrix, application to the 1D BVP
- The use of CG for the solution of the Schur complement system
- Schur complement method, arrowhead matrix, application to the 2D BVP
- Schwarz alternating (splitting) method, preconditioning
- Multigrid method, two- and multi-level method, preconditioning, extension and restriction operators, convergence, V-cycle and full MG
- Fast Fourier Transform methods, application to the 1D BVP
- FFT methods for the 2D BVP; diagonalization and block-diagonalization
- Interpolation
- Deboor decomposition
- Iterative methods for general (including non-symmetric) systems
- Introduction - Krylov subspace methods
- Generalized Minimal Residual (GMRES) method
- Restarted Generalized Minimal Residual method (GMRES(m))
- Convergence of GMRES
- Full Orthogonalization Method (FOM)
- Conjugate Residual (CR) method
- Other methods (GCR, Orthomin, Orthodir)
- Bi-orthogonal bases and related methods (BiCG, QMR, CGS, BiCGStab, TFQMR)
References
| Numerical Linear Algebra | ||
| L. A. Hageman and D. M. Young | Applied Iterative Methods | Academic Press 1981 |
| R. S. Varga | Matrix iterative analysis | Prentice Hall 1962 |
| D. M. Young | Iterative Solution of Large Linear Systems | Academic Press 1971 |
| J. M. Ortega | Matrix theory: a second course | Plenum Press 1987 |
| Gilbert W. Stewart | Introduction to matrix computations | Academic Press 1973 |
| William W. Hager | Applied Numerical Linear Algebra | Prentice Hall 1988 |
| Gene Golub and Charles Van Loan | Matrix computations | John Hopkins Univ. Press 1996 |
| Advanced Methods | ||
| Yousef Saad | Iterative Methods for Sparse Linear Systems | SIAM 2003 (PWS 1996) |
| Wolfgang Hackbusch | Iterative Solution of Large Sparse Systems of Equations | Springer Verlag 1994 |
| William L. Briggs | A multigrid tutorial | SIAM 2000 |
| Charles Van Loan | Computational Frameworks for the Fast Fourier Transform | SIAM 1992 |
| O. Axelsson and V. A. Barker | Finite element solution of boundary value problems | Academic Press 1984 | Parallel Computing |
| James M. Ortega | Introduction to Parallel and Vector Solution of Linear Systems | Plenum Press 1988 |
| Eric F. Van de Velde | Concurrent Scientific Computing Number 16 in Texts in Applied Mathematics | Springer Verlag 1994 |
| Gene H. Golub and J. M. Ortega | Scientific computing: an introduction with parallel computing | Academic Press 1993 |
| General Numerical Analysis | ||
| S. D. Conte and Carl de Boor | Elementary Numerical Analysis | McGraw-Hill Inc. |
| David Kincaid and Ward Cheney | Numerical Analysis | Brooks/Cole 2002 (1996) |
| Michael Heath | Scientific Computing: an introductory survey | McGraw-Hill Inc. 2003 |
| Richard L. Burden and J. Douglas Faires | Numerical Analysis | Brooks/Cole 2001 (1997) |
| L. W. Johnson and R. D. Riess | Numerical Analysis | Addison Wesley |
| Partial Differential Equations | ||
| Arieh Iserles | A first course in the Numerical Analysis of Partial Differential Equations | Cambridge University Press 1996 |
| Michael A. Celia and William G. Gray | Numerical methods for differential equations | Prentice Hall 1992 |
| William F. Ames | Numerical Methods for Partial Differential Equations | Academic Press 1977 3rd edition (or 2nd edition) (or Thomas Nelson & Sons) |
| C. A. Hall and T. A. Porsching | Numerical Analysis of Partial Differential Equations | Prentice Hall 1990 |
| John C. Strikwerda | Finite Difference schemes and Partial Differential Equations | Wadsworth and Brooks/Cole 1989 |
| John R. Rice and R. F. Boisvert | Solving Elliptic Problems with ELLPACK | Springer Verlag 1985 |
| Splines | ||
| P. M. Prenter | Splines and Variational Methods | John Wiley & Sons 1975 |
| Carl de Boor | A Practical Guide to Splines | Springer Verlag 1978 |
Prerequisites
- Calculus: Taylor series, Rolle's theorem, mean value theorem, graphs of functions, continuity, convergence, de l' Hospital's rule, partial differentiation, etc.
- Deep understanding of computational errors
- Numerical Linear Algebra (included in CSC350/336): some knowledge of direct and iterative methods for solving linear systems. Fluency in matrix and vector manipulation, both algebraic and algorithmic.
- Interpolation (included in CSC351/436): spline interpolation.
- Partial Differential Equations: minimal knowledge of PDEs.
- Theory of Computer Algorithms: minimal knowledge of computer algorithms, data structures and computational complexity.
- Programming: while most programming is in MATLAB, proficiency in some conventional programming language, such as FORTRAN, C or python, especially the handling of (sparse) matrices, vectors, indices, etc., is assumed.
Schedule for Fall 2026
| Lectures | Tuesday 5-7 PM | Room MY 320 |
| Office Hours | Monday 1:30-2:30 PM | Room BA4226 |
Tentative marking scheme for Fall 2026
| Problem set 1 | 23% |
| Problem set 2 | 23% |
| Problem set 3 | 23% |
| Term test 1 | 31% |