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.

Teachers

Module 1: Rob Bisseling (Mathematical Institute UU)
Module 2: Alessandro Sbrizzi (University Medical Center Utrecht)
Teaching assistant: Lotte Muller (Mathematical Institute UU)

Course material

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 on networks.

Module 2 (4 weeks): Magnetic Resonance Imaging (MRI). Online material will become available through Blackboard.

Software

We use Matlab, see Free software at the UU for students. In Module 2 we will use the Image Processing Toolbox, which can be downloaded with the Matlab package. Tick a box when installing.

Information

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.

Grading

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.

Credits

7,5 ECTS

Description

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.

Language

English, but student may write their reports in English or Dutch.

Prerequisites

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.

Schedule

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.

Module 1

Lecture 1 (Monday February 8, 2021, 13.15-14.00 hour): Introduction Matlab (Ch1 and Ch2)
- Introduction to the course: goals, practicalities
- Iterations
- Fibonacci sequence
- 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)
- Web matrices
- Adjacency matrix of a graph
- PageRank algorithm
- 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
- Power-law networks
- High-degree nodes: hubs
- SIR model for networks
- Network dynamics of vaccinations and mutations
- Today's slides: Covid-19 Spreading on Networks by Rob Bisseling.
- Scaling in Spreading phenomena: a network approach by Shlomo Havlin, Bar Ilan University, webinar given at at Utrecht Centre for Complex Systems Studies, January 22, 2021. Shows effects of acquaintance vaccination.
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 Matlab versions).
- Today's slides: Sparse Matrix Partitioning by Rob Bisseling. Downloadable 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 and beyond.
After Lecture 6: Start working on project module 1
- Project: crawl the 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 Matlab-implementation.
- Compute 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.