This is the webpage for the Imperial College London Mathematics module MATH60024/MATH70024 - Computational Linear Algebra.

• General course information
  • Course leader
  • Accreditation
  • Assumed knowledge
  • Assessment
    • Mastery
  • Blackboard
• Errata for 2024/25

A PDF version of the course notes is available here. The lecture material for this course is available as videos linked from the web version of the notes.

The text for this part of the module is Trefethen and Bau Numerical Linear Algebra. Another very useful reference is Golub and van Loan Matrix Computations.

We provide a complete set of notes for the course below.

Lecture notes:

• 1. Getting ready for computational exercises
  • 1.1. Getting the software that you need
  • 1.2. The Terminal
  • 1.3. Python virtual environment
  • 1.4. GitHub and git
  • 1.5. Setting up your repository
  • 1.6. How to do the computational exercises
  • 1.7. Running your work
  • 1.8. Testing your work
  • 1.9. Coding style and commenting
  • 1.10. Skeleton code documentation
• 2. Linear algebra preliminaries
  • 2.1. Matrices, vectors and matrix-vector multiplication
  • 2.2. Range, nullspace and rank
  • 2.3. Invertibility and inverses
  • 2.4. Adjoints and Hermitian matrices
  • 2.5. Inner products and orthogonality
  • 2.6. Orthogonal components of a vector
  • 2.7. Unitary matrices
  • 2.8. Vector norms
  • 2.9. Projectors and projections
  • 2.10. Constructing orthogonal projectors from sets of orthonormal vectors
• 3. QR factorisation
  • 3.1. What is the QR factorisation?
  • 3.2. QR factorisation by classical Gram-Schmidt algorithm
  • 3.3. Projector interpretation of Gram-Schmidt
  • 3.4. Modified Gram-Schmidt
  • 3.5. Modified Gram-Schmidt as triangular orthogonalisation
  • 3.6. Householder triangulation
  • 3.7. Application: Least squares problems
• 4. Analysing algorithms
  • 4.1. Operation count
  • 4.2. Operation count for modified Gram-Schmidt
  • 4.3. Operation count for Householder
  • 4.4. Matrix norms for discussing stability
  • 4.5. Norm inequalities
  • 4.6. Condition number
  • 4.7. Conditioning of linear algebra computations
  • 4.8. Floating point numbers and arithmetic
  • 4.9. Stability
  • 4.10. Backward stability of the Householder algorithm
  • 4.11. Backward stability for solving a linear system using QR
• 5. Finding eigenvalues of matrices
  • 5.1. How to find eigenvalues?
  • 5.2. Transformations to Schur factorisation
  • 5.3. Similarity transformation to upper Hessenberg form
  • 5.4. Rayleigh quotient
  • 5.5. Power iteration
  • 5.6. Inverse iteration
  • 5.7. Rayleigh quotient iteration
  • 5.8. The pure QR algorithm
  • 5.9. Simultaneous iteration
  • 5.10. The pure QR algorithm and simultaneous iteration are equivalent
  • 5.11. Connections between power iteration, inverse iteration, and QR algorithm
  • 5.12. The practical QR algorithm
• 6. Iterative Krylov methods for \(Ax=b\)
  • 6.1. Krylov subspace methods
  • 6.2. Arnoldi iteration
  • 6.3. GMRES
  • 6.4. Convergence of GMRES
  • 6.5. Preconditioned GMRES
  • 6.6. Knowing when to stop
• 7. Preconditioning Krylov methods
  • 7.1. Stationary iterative methods
  • 7.2. Using splitting methods as preconditioners
  • 7.3. Symmetric iterative methods
  • 7.4. Convergence criteria for stationary methods
  • 7.5. Splitting methods as preconditioners
  • 7.6. Convergence analysis for Richardson
  • 7.7. Convergence analysis for symmetric matrices
  • 7.8. An example matrix (Non-examinable in 2024/25)
  • 7.9. Chebyshev acceleration (examinable in 2024/25)

The automated documentation for the skeleton code is below.

• cla_utils package
  • Submodules
  • cla_utils.exercises1 module
    • ABiC()
    • basic_matvec()
    • column_matvec()
    • rank1pert_inv()
    • rank2()
    • time_matvecs()
    • timeable_basic_matvec()
    • timeable_column_matvec()
    • timeable_numpy_matvec()
  • cla_utils.exercises10 module
    • GMRES()
    • arnoldi()
    • get_AA100()
    • get_BB100()
    • get_CC100()
  • cla_utils.exercises2 module
    • GS_classical()
    • GS_modified()
    • GS_modified_R()
    • GS_modified_get_R()
    • orthog_cpts()
    • orthog_proj()
    • orthog_space()
    • solve_Q()
  • cla_utils.exercises3 module
    • householder()
    • householder_ls()
    • householder_qr()
    • householder_solve()
    • solve_U()
  • cla_utils.exercises8 module
    • Q1AQ1s()
    • ev()
    • hessenberg()
    • hessenbergQ()
    • hessenberg_ev()
  • cla_utils.exercises9 module
    • get_A100()
    • get_A3()
    • get_B100()
    • get_B3()
    • get_C100()
    • get_D100()
    • inverse_it()
    • pow_it()
    • pure_QR()
    • rq_it()
  • Module contents