Introduction Scientific Computing (WISB 356), 2018/2019
Location and time
Monday (13.15-17 hour) and Thursday (9-12.45 hour) from February 4, 2018 until April 4, 2018
in room BBG115
at the Uithof campus in Utrecht. Not on: March 4, 7 (break week).
Module 1: Rob Bisseling (Mathematical Institute UU)
Module 2: Alessandro Sbrizzi (University Medical Center Utrecht)
Teaching assistent: Ruben Meijs (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.
Module 2 (4 weeks): Magnetic Resonance Imaging (MRI). Online material will become available soon
via Alessandro Sbrizzi's ISC webpage.
We use Matlab, see Free software at the UU
for students. Bring your own laptop, because we work by the principle
Bring Your Own Device (BYOD). In class there are no desktop computers.
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 on Alessandro Sbrizzi's ISC webpage.
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 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.
Both theoretical aspects and practical, software-related
aspects will be treated. Every week there will be frontal lectures alternating with exercise/computer laboratory classes.
This course presents a taste of the new master track Applied Mathematics, Complex systems, and Scientific Computing
and it represents an overview of scientific computing.
The connection to practice is further established by one or more guest teachers.
Linear algebra (WISB121),
Calculus A (WISB132),
Calculus B (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. Wsrning: 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. Small changes may still occur depending on our progress.
- Day 1 (Monday February 4, 2019): Introduction Matlab (Ch1 and Ch2)
- Life demos from .m files from the book
- Exercises Ch1: 1, 6, 9, 10, 15
- Exercises Ch2: 3, 4, 5, 6, 7, 8
- Today's slides : A quick introduction to Matlab,
Johns Hopkins University, Computer Science Dept. 2007
- Day 2 (Thursday February 7, 2019): Matrix laboratory (Ch4)
Matrices and transformations
Rotations and QR decomposition
Timing of matrix multiplication
Traditional vs. Strassen matrix multiplication
- Exercises Ch4: 3, 4, 5, 8, 14
- Useful videos on linear algebra:
Essence of linear algebra
by 3Blue1Brown, a YouTube channel on animating mathematics.
- Day 3 (Monday February 11, 2019): Linear systems (Ch5)
- Day 4 (Thursday February 14, 2019): Google PageRank (Ch7)
Adjacency matrix of a graph
- Exercises Ch7: 1, 3, 4, 6.
- Day 5 (Monday February 18, 2019): Sparse matrices
- Day 6 (Thursday February 21, 2019): Iterative solvers
- 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.
- Day 7 (Monday February 25, 2019): Working on project 1
Discussion of the report to be written on the project.
Working on the project:
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 PAQ.
Find a suitable P and Q, e.g. based on the Hilbert-curve, Morton-curve,
Separated Block Diagonal (SBD) structure.
Aim: more efficient use of the
computer cache, and faster SpMV.
Compare your own program with the
PageRank of the websites from your own chosen domain.
How large can you choose your domain?
Use your SpMV also in an iterative solver to solve a linear system.
- A detailed description of the project can be found on Blackboard.
- Day 8 (Thursday February 28, 2019): Continuing with project 1
- Start writing your first report.
The deadline of this report is Monday March 11, 13.15 hour,
i.e., at the start of module 2.
Send your report for module 1 preferably through Blackboard (Assignment 1) to Rob Bisseling.
If this fails, just as PDF by email to Rob Bisseling.
It will be discused indivually with every student the week after.
Last update of this page by
Rob Bisseling: March 7, 2019.