Introduction Scientific Computing (WISB 356), 2020/2021, Utrecht University
Location and time
Monday (13.15-17 hour), Tuesday (13.15-15 hour) and Thursday (9-10.45 hour)
from February 8, 2021 until April 8, 2021
online in Microsoft Teams.
No class in week from 8-12 March.
Module 1: Rob Bisseling (Mathematical Institute UU)
Module 2: Alessandro Sbrizzi (University Medical Center Utrecht)
Teaching assistant: Lotte Muller (Mathematical Institute UU)
Module 1 (4 weeks): begin intro Matlab, then Chapter 5 (linear systems) and 7 (PageRank)
from the online book by Cleve Moler (2011),
Experiments with Matlab.
We will use other materials as well, in particular for the topic of Covid-19 simulation
Module 2 (4 weeks): Magnetic Resonance Imaging (MRI). Online material will become available
We use Matlab, see Free software at the UU
In Module 2 we will use the Image Processing Toolbox, which can be downloaded with the Matlab package.
Tick a box when installing.
All information on module 1 can be found on the present page.
All information on module 2 can be found through the Blackboard pages of this course.
Based on two reports, one per module.
Both reports have equal weight and count for 50% of the final grade of the course.
Every report needs to obtain a grade of at least 5, and the rounded final grade must be at least 6.
The reports can be written in either Dutch or English.
The reports can be written together with (at most) one fellow student.
Every student is individually accountable for the whole report.
Reports can be discussed individually afterwards.
This discussion may influence the final grade.
The aim of this course is to provide a first orientation towards the area of
scientific computing by some
case studies from various application areas. Topics treated are widely used techniques
from numerical linear algebra such as the solution of linear
systems and eigenvalue problems, both dense and sparse, within the context of an application
such as computing the
Google PageRank of a webpage or the processing of images obtained by an
MRI scanner. We will also study algorithms of a more combinatorial nature,
such as the partitioning of sparse matrices. We will explore the connection between
sparse matrices and networks, and will perform simulations of various vaccination
strategies on the spread of Covid-19 on a population network.
Both theoretical aspects and practical, software-related
aspects will be treated. Every week there will be online lectures alternating with exercise sessions,
and question and answer sessions, either individual or in groups.
This course presents a taste of the master track Applied Mathematics, Complex Systems, and Scientific Computing
and it represents an overview of scientific computing.
English, but student may write their reports in English or Dutch.
Calculus and Linear Algebra (WISB107, WISB108, WISB137),
The course Numerical Mathematics WISB251 is desired, but not strictly necessary.
When in doubt, or for majors other than in Mathematics or Physics,
please contact one of the teachers.
It is not necessary to know Matlab already, as we will start with a gentle
introduction to Matlab. Warning: be aware that the level of difficulty of the course
will gradually increase during the period of the course, both conceptually and practically,
so that near the end (in the second module) we expect the maximum effort from the student.
We roughly follow the schedule below. Ch5 means Chapter 5 from the book by Cleve Moler,
"Experiments with Matlab", 2011.
The chapter and exercise numbering is according to the PDF version of the book.
The exercises listed are related to the lecture and they are are meant for the exercises sessions.
The exercise sessions are: Monday 14.15-15.00 hour (led by Rob), Monday 16.15-17.00 (Rob), Tuesday 13.15-15.00 (Lotte),
Thursday 10.00-10.45 (Rob+Lotte). The exercises need not be handed in. They are selected
to get you started, and can be discussed with the teachers. Don't worry if they are too much;
you do not need to finish them all.
Small changes in the schedule and content may still occur depending on our progress.
- Lecture 1 (Monday February 8, 2021, 13.15-14.00 hour): Introduction Matlab (Ch1 and Ch2)
- Introduction to the course: goals, practicalities
- Exercises Ch1: 1, 6, 10, 15
- Exercises Ch2: 3, 4, 5, 6
- Today's slides : A quick introduction to Matlab,
Johns Hopkins University, Computer Science Dept. 2007
- Lecture 2 (Monday February 8, 2021, 15.15-16.00 hour): Matrix multiplication (Ch4)
Matrices and transformations
Timing of matrix multiplication
Traditional vs. Strassen matrix multiplication
- Live demos
- Exercises Ch4: 3, 4, 8, 14
- Today's slides: Matrix Multiplication
- Useful videos on linear algebra:
Essence of linear algebra
by 3Blue1Brown, a YouTube channel on animating mathematics.
- Lecture 3 (Thursday February 11, 2021, 9.00-9.45 hour): Linear systems (Ch5)
LU decomposition with partial pivoting
Triangular system solving
- Today's slides: Solving Systems of Linear Equations
by Greg Fasshauer, Illinois Institute of Technology.
We present pages 1-25, 43-46.
- Exercises Ch5: 2, 3, 4
- Lecture 4 (Monday February 15, 2021, 13.15-14.00 hour): Sparse matrix ordering
SparseSuite (University of Florida) collection of sparse matrices
- Sparse Cholesky factorisation
- Relation between a sparse matrix and a graph
- Minimum degree ordering
- Today's slides: Sparse Matrix Ordering
- Lecture 5 (Monday February 15, 2021, 15.15-16.00 hour): Google PageRank (Ch7)
Adjacency matrix of a graph
- Exercises Ch7: 1, 3, 4
- Today's slides: Google's PageRank
- Lecture 6 (Thursday February 18, 2021, 9.00-9.45 hour): Sparse linear systems
- Finding pivots by graph matching.
- Block triangular form of a matrix.
Krylov methods: conjugate gradients, GMRES, BiCGStab
Neural networks as a sparse matrix-vector product
- Today's slides: Sparse Linear Systems by Rob Bisseling.
- Lecture 7 (Monday February 22, 2021, 13.15-14.00 hour): Covid-19 spreading on networks
- Lecture 8 (Monday February 22, 2021, 15.15-16.00 hour): Sparse matrix partitioning
- Partitioning of graphs and sparse matrices
- Separated Block Diagonal (SBD) structure
- Parallel computing
- Mondriaan package. (Please note: its Matlab interface does not work anymore with the recent
- Today's slides: Sparse Matrix Partitioning
by Rob Bisseling.
file for Sparse Matrix partitioning including movies in .avi format, compressed as gzipped tarfile.
Note that the movies may not work on every computer.
- Short informal talk (Monday March 1, 2021, 13.15-13.45 hour): How to write a report
- I will discuss a number of important aspects of writing a report, for this course
- After Lecture 6: Start working on project module 1
World Wide Web using a crawler, and choose your own subdomain.
Construct a PageRank algorithm, and investigate personalisation.
- Write your own sparse matrix-vector product (SpMV)
with your own data structure. Reorder
the matrix A into PAP^T.
Find a suitable P
e.g. based on the Morton-curve.
Aim: more efficient use of the
computer cache, and faster SpMV.
Compare your program with your own baseline and with the
PageRank of the websites from your own chosen domain.
How large can you choose your domain?
Create a random sparse matrix that represents the physical interactions between people.
The degrees of the network should be distributed by a power law.
The vector to be multiplied in the SpMV consists of values 0 (representing susceptible) and 1 (infectious).
Perform a number of iterations to see what happens.
Change you network dynamically by removing infected nodes at a certain rate,
representing recovery (immunity).
This also removes the corresponding edges.
- Try different vaccination strategies (which are also node removals):
random vaccination, vaccination of high-degree nodes first.
- Try to model the effect of mutations.
- A detailed description of the project can be found on Blackboard.
- Deadline project module 1
The deadline of this report is Monday March 15, 13.15 hour,
i.e., at the start of module 2.
Send your report for module 1 through Blackboard (Assignment 1) to Rob Bisseling.
It will be discused indivually with every student the week after.
Last update of this page by
Rob Bisseling: March 1, 2021.