CS 328: Numerical Methods for Visual Computing (Fall 2016)
Summary: Visual computing disciplines are characterized by their universal reliance on numerical algorithms to process and display large amounts of visual information such as geometry, images, and volume data; an understanding of numerical methods is thus an important prerequisite to working in this area. This course will familiarize students with a range of essential numerical tools to solve practical problems in a visual computing context.
Contents: This course provides a first introduction to the field of numerical analysis with a strong focus on visual computing applications. Using examples from computer graphics, geometry processing, computer vision, and computational photography, students will gain hands-on experience with a range of essential numerical algorithms.
The course will begin with a review of important considerations regarding floating point arithmetic and error propagation in numerical computations. Following this, students will study and experiment with several techniques that solve systems of linear and non-linear equations. Since many interesting problems cannot be solved exactly, numerical optimization techniques constitute the second major topic of this course. Students will learn how principal component analysis can be leveraged to compress or reduce the dimension of large datasets to make them easier to store and analyze. The course concludes with a review of numerical methods that make judicious use of randomness to solve problems that would otherwise be intractable.
Students will have the opportunity to gain practical experience with the discussed methods using programming assignments based on Scientific Python.
Prerequisites: Course prerequisites are MATH-101 (Analysis I) and MATH-111 (Linear Algebra). The courses CS-211 (Introduction to visual computing) and MATH-106 (Analysis II) are recommended but not required.
Students are expected to have good familiarity with at least one programming language (e.g. C/C++, Java, Scala, Python, R, Ruby...). The course itself will rely on Python, but this is straightforward to learn while taking the course. During the first weeks of the semester, there will be tutorial sessions on using Python and Scientific Python.
Although it is not a strict prerequisite, this course is highly recommended for students who wish to pursue studies in the area of Visual Computing, in particular: CS-341 (Introduction to computer graphics), CS-440 (Advanced computer graphics), CS-442 (Computer vision), CS-413 (Computational Photography), CS-444 (Virtual Reality), and CS-445 (Digital 3D geometry processing)
Learning outcomes: At the end of the course, students should be able to:
Write computer programs that use numerical linear algebra and analysis techniques to transform and visualize data
Reason about ways of structuring numerical computations efficiently.
Analyze the numerical stability of programs built on floating point arithmetic
Recognize numerical problems in visual computing applications and cast them into a form that can be solved or optimized.
Teaching methods: Lectures, interactive demos, theory and programming exercises
Expected student activities: Students are expected to study the provided reading material and actively participate in class and in exercise sessions. They will be given both theoretical exercises and a set of hands-on programming assignments.
- Continuous assessment during the semester via project assignments (50%)
- Final exam (50%)
Resources: Slides and other resource will be provided at the end of each class. The course textbook is Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics by Justin Solomon (freely available here)
The following optional references are optional but highly recommended: Scientific Computing: An Introductory Survey (2nd edition) by Michael Heath and What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg.
Late policy: the score of late homework submissions is reduced by -25% per late day.
Academic Integrity: Assignments must be solved and submitted individually. Do not copy (or even look at) parts of any of the homeworks from anyone else including the web. Do not make any parts of your homework available to anyone, and ensure that your files are not accessible to others. The university policies on academic integrity will be applied rigorously.
Office Hours: we offer the following office hours:
- Wenzel Jakob: Monday 3:15-4:15 pm, BC 345 (weekly)
- Julia Proskurnia & Andreas Finke: Tuesday 1:45-2:45 pm, BC 147 (even-numbered weeks)
- Bugra Tekin & Leonardo Impett: Friday 10-11 am, BC 317 (odd-numbered weeks)
Final Exam: Friday 27.01.2017 from 08h15 to 11h15 (PO01). A few remarks:
- Please bring a black or blue ink pen. Pencils are not permitted.
- Make sure to arrive sufficiently early and find the seat assigned to you (the seat assignments are posted on paper sheets at the exam location).
- You must bring your ID card for identification purposes and place it in front of yourself.
- You are allowed to bring a single (1) written or printed A4 page containing personal notes (you can use both sides). However, books and other aids (laptops, calculators, smartphones, smartwatches, etc.) are not permitted.
- Extra empty paper is provided during the exam if needed, there is no need to bring your own.
Lecture: Administrative details, overview of course topics, introduction to Floating Point arithmetic & error analysis.
Reading: Solomon, Chapter 1 (everything except Lagrange Multipliers) & Chapter 2.
Exercise: Python & SciPy basics
Homework 1 released: get it here. Due in 2 weeks on Wednesday 12/10 (before class).
Lecture: How to write efficient numerical code: high-performance computing, processor architecture trends, parallelism, SIMD vectorization.
Exercise: NumPy/SciPy/Matplotlib tutorial (continued)
Lecture: Linear systems review, LU decomposition.
Reading: Solomon, Chapter 3.
Exercise: Solving linear systems in SciPy, Vectorizing a Sphere Ray Tracer.
Lecture: Conditioning of linear systems, Applications of Linear Systems
Reading: Solomon, Chapter 4.
No exercise session
Lecture: QR Factorization, Least Squares Optimization
Reading: Solomon, Chapter 5 (you can skip over the section on Gram-Schmidt QR).
Exercise: review of homework assignment 1.
Homework 2 released: get it here. It is due in 2 weeks on Friday 4/11.
Lecture: Eigenanalysis & Singular Value Decomposition
Reading: Chapter 6 [up to 6.4.1]
Exercise: session on homework assignment 2.
Lecture: The Singular Value Decomposition, continued.
Exercise: session on homework assignment 2.
No Lecture / Exercise
Lecture: (Nonlinear) Root finding and optimization (1D)
Reading material: Solomon, Chapter 8, Section 1: Nonlinear Systems (1D case)
No Exercise session
Homework 3 released, get it here.
Lecture: multidimensional nonlinear equations, optimization.
Discussion of homework 2 solutions.
Exercise: Q&A for Homework 3.
Lecture: Numerical integration
Exercise: review of Homework 3 solutions.
Homework 4 released: get it here. It is due in 2 weeks on Thursday 22.12.
Lecture: Monte Carlo methods
Exercise: homework 4 Q&A.
Lecture: Practice exam
Exercise: homework 4 Q&A.