Numerical Algorithms for Visual Computing
Dr. Matthias Augustin
Office hour: Please contact me via email or Teams.
Summer Term 2021
Lectures (3h) with exercises (1h);
(6 ETCS points)
Lectures: Online Sessions with Q&A and Tutorial Sections
Tuesday, 8:30-10:00
Thursday, 12:15-14:00
First online session: Tuesday, April 13, 2021
First tutorial: Thursday, May, 13
Announcements –
Description –
Prerequisites –
Tutorials –
Registration –
Exam –
Contents –
Assignments –
Literature
- 2021-07-21:
Sample solution to Assignment 06 online.
Lecture notes updated: Corrected a sign error in the last line of Eq.(7.1.39).
- 2021-07-19:
Lecture notes updated: Changed a formulation on page 82 (reference version)
which wrongly stated that, for the conjugate gradient scheme, the correction
is given by the residual.
- 2021-07-13: Assignment 06 is online.
You can submit this assignment until 2021-07-20, 14:00 via e-mail to
Matthias Augustin.
Lecture notes updated (all numbers are with
respect to the reference version of the lecture notes):
- Corrected index in Eq. (5.2.19), first line, in the expression
directly before the equality sign with the ! above.
- Corrected parentheses on left-hand side of Eq. (6.3.6).
- Corrected a sign in (6.3.11) and cancelled out the \tau on the
right-most side.
- Added parentheses around the k+1 on the left-hand side of
Eq. (6.3.20).
- Extended Definition 6.5 and Remark 6.6 slightly to clarify the
kinds of limits that need to be considered.
- Changed Eq. (6.4.2) such that k is an upper index to the
finite difference operator, not an argument.
- Added missing index to norm of matrix in Eq. (6.4.13).
- Added missing index j to t on right-hand side of Eq. (6.4.19).
- Changed n to k in Eqs. (6.4.20) and (6.4.22) as well as in the
line before Eq. (6.4.24).
- Added a missing factor to Eq. (6.4.35) and added a line before that
equation to explain where the factor comes from.
- Added missing factor h in the norms in Eq. (6.4.45), (6.4.46), and
(6.4.47).
Target group: Students in the Master Programme Visual Computing
Lecture aim: Provide some concepts which are useful for the numerical
treatment of partial differential equations. This includes
- iterative solvers for linear systems of equations,
- (short) introduction to partial differential equations (PDEs),
- finite-difference (FD) schemes,
- schemes for PDEs of potential and diffusion type,
- properties of PDEs which transfer to FD schemes,
- hyperbolic problems and upwinding.
This course is suitable for students of visual computing, mathematics, and
computer science.
Students attending this course should be familiar with basic concepts of
(multi-dimensional) calculus and linear algebra as covered in introductory
maths course (such as Mathematik für Informatiker I-III). Mathematical
prerequisites which exceed the basic mathematics courses are provided within
the lecture notes. All material will be in English. Knowledge from image
processing may be helpful, but is not required.
Due to the current sitation caused by SARS-Cov2, this lecture will be closer
to an inverted classroom / blended learning setting. This means that for each
live online sessions, students will be required to prepare using the available
material. A schedule detailing the amount of content that you need to prepare
will be made available at the start of the lecturing period. Live sessions
themselves are intended to follow a Q&A structures and might present further
exercise material.
There will be a total of 6 homework assignments
which will be graded. Assignments will be published on the Teams file
repository and this website.
Students are expected to submit their solutions to these assignments via email
to
Matthias Augustin within
one week after publications.
Working together in groups of up to 3 students is permitted and encouraged.
Some assignments contain programming exercises.
In order to qualify for the final exam, it is necessary to achieve 50% of the
points of all assignment sheets in total. All exams will be oral.
Registration is closed since the submitting date of the first assignment passed
(2021-05-01).
According to the regulations concerning storage and processing of
personal data (Art. 6 (1) Datenschutzgrundverordnung (DSGVO)) we
store and process your personal data for the purpose of lecture and
tutorial organisation only. I.e. we may use them to contact you, to
inform you about your grade, and to transmit your grades to the
examination office.
In order to qualify for the final exam, it is necessary to achieve 50% of the
points of all assignment sheets in total.
There will be two oral exams, one at the beginning and one at the end of
the semester break. In case of qualification, you are allowed to take part in
both exams. The better grade counts, but each exam will count as an attempt
individually.
Please remember that you have to register online for the exam
in the HISPOS system of the
Saarland University for each attempt separately.
The first exam takes place on
Monday, August 02, 2020.
The second exam takes place on
Thursday, September 30, 2020.
Further information about the exam can be found
here
Organizational slides
from the first online session
Lecture notes
reference version
newest version
The first chapter of these lecture notes is intended to be a summary of content from
linear algebra, in particular concerning things needed in the context of systems of
linear equations. It is intended to allow students to quickly refresh their knowledge in
this particular field. The actual content of this lecture starts with Chapter 2.
Links to additional exercises will be added to the schedule after each live session.
Date |
Please prepare |
Pages |
04/13 |
Introduction and Organization |
-- |
04/15 |
Section 2.1
|
47-53 |
04/20 |
Section 2.2
|
53-61 |
04/22 |
Section 2.3 to end of Section 2.3.1
|
61-67 |
04/27 |
Section 2.3.2 and Section 2.3.3
|
67-72 |
04/29 |
Section 2.3.4 and Section 2.4.1
|
72-77 |
05/04 |
Section 2.4.2 to Equation (2.4.45)
|
77-83 |
05/06 |
Definition 2.48 to Equation (2.4.81)
|
77-83 |
05/11 |
Section 2.5
|
90-94 |
05/13 |
Ascension Day
|
-- |
05/18 |
Chapter 3 up to Remark 3.5 & Assignment 01
|
97-101 |
05/20 |
Pages 102 to 108
|
102-108 |
05/25 |
Section 3.3 to Section 4.2
|
109-113 |
05/27 |
Assignment 02
|
-- |
06/01 |
Section 4.3 and Section 4.4
|
114-118 |
06/03 |
Corpus Christi
|
-- |
06/08 |
Chapter 5 up to Equation (5.2.22)
|
119-125 |
06/10 |
Remark 5.5 to Equation (5.2.41) & Assignment 03
|
125-133 |
06/15 |
Section 5.3 to Remark 5.13
|
133-138 |
06/17 |
Section 5.3.3 to Remark 5.18
|
138-145 |
06/22 |
Section 5.5 to Remark 6.2
|
145-152 |
06/24 |
Assignment 04
|
-- |
06/29 |
Section 6.3 to Remark 6.4
|
152-157 |
07/01 |
After Remark 6.4 to Remark 6.13
|
157-164 |
07/06 |
Section 6.4.2 and Section 6.4.3
|
164-170 |
07/08 |
Assignment 05
|
-- |
07/13 |
Section 6.4.4 and Section 6.4.5
|
170-174 |
07/15 |
Chapter 7 up to Equation (7.1.37)
|
191-196 |
07/20 |
Definition 7.2 to Theorem 7.11
|
196-204 |
07/22 |
Assignment 06
|
-- |
No. |
Title |
Date |
|
Submit until |
Assignment 01 |
Iterative Solvers -- Splitting Methods |
05/04 |
[download] |
05/11 |
Assignment 02 |
Iterative Solvers -- Gradient and Projection Methods |
05/18 |
[download] |
05/25 |
Assignment 04 |
Laplace Equation in 1D |
06/15 |
[download] |
06/22 |
Assignment 05 |
Parabolic Schemes |
06/29 |
[download] |
07/06 |
No. |
Title |
Date |
|
Submit until |
Assignment 01 |
Iterative Solvers -- Splitting Methods |
05/04 |
[download] |
05/11 |
Assignment 02 |
Iterative Solvers -- Gradient and Projection Methods |
05/18 |
[download] |
05/25 |
Assignment 03 |
PDEs, Classification, Finite Differences |
06/01 |
[download] |
06/08 |
Assignment 04 |
2D Stencils, Higher Order Consistency,
Numerics for Laplace Equation in 1D
|
06/15 |
[download] |
06/22 |
Assignment 05 |
Parabolic PDEs |
06/29 |
[download] |
07/06 |
Assignment 06 |
von Neumann Analysis |
07/13 |
[download] |
07/20 |
No. |
Title |
Date |
|
Assignment 01 |
Iterative Solvers -- Splitting Methods |
05/13 |
[download] |
Assignment 01 |
Sample Program: Iterative Solvers -- Splitting Methods |
05/13 |
[download] |
Assignment 02 |
Iterative Solvers -- Gradient and Projection Methods |
05/26 |
[download] |
Assignment 02 |
Sample Program: Iterative Solvers -- Gradient and Projection Methods |
05/26 |
[download] |
Assignment 03 |
PDEs, Classification, Finite Differences |
06/08 |
[download] |
Assignment 04 |
2D Stencils, Higher Order Consistency,
Numerics for Laplace Equation in 1D
|
06/23 |
[download] |
Assignment 04 |
Sample Program: Laplace Equation in 1D |
06/23 |
[download] |
Assignment 05 |
Parabolic PDEs |
07/06 |
[download] |
Assignment 05 |
Sample Programm: Parabolic Schemes |
07/06 |
[download] |
Assignment 06 |
von Neumann Analysis |
07/21 |
[download] |
There is no specific text book for this class, but here is a selection of some
books covering many of the topics in this course, giving background material
and providing further reading:
-
Numerical Solution of Partial Differential Equations in Science and
Engineering
L. Lapidus, G. F. Pinder, Wiley, 1999.
-
Numerical Partial Differential Equations
Volume I: Finite Difference Methods
Volume II: Conservation Laws and Elliptic Equations
J. W. Thomas, Springer, 1995 (Vol. I) / 1999 (Vol. II).
-
Finite Difference Methods for Ordinary and Partial Differential Equations
R. J. LeVeque, SIAM, 2007.
-
Numerical Methods for Conservation Laws
R. J. LeVeque, Birkhäuser, 1992.
-
Numerical Solution of Partial Differential Equations
K. W. Morton, D. Mayers, Cambridge University Press, 2005.
-
The Finite Difference Method in Partial Differential Equations
A. R. Mitchell, D. F. Griffiths, Wiley, 1985.
-
Numerical Solution of Differential Equations
W. E. Milne, Wiley, 1960.
-
Introduction to Numerical Analysis
J. Stoer, R. Bulirsch, Springer, 1993.
English translation of the originally german version.
Most of these and further books can be found in the mathematics and computer
science library.
Further references will be provided during the lecture as needed.
|