RGL
EPFL Logo

CS 328: Nu­mer­ic­al Meth­ods for Visu­al Com­put­ing (Fall 2018)

Wednesday
2-4pm (Lecture)
4-5pm (Exercise)
Wenzel Jakob
Instructor
Helge Rhodin
Instructor
Merlin Nimier-David
Teaching Assistant
Tizian Zeltner
Teaching Assistant
Delio Vicini
Teaching Assistant

General information

Sum­mary: Visu­al com­put­ing dis­cip­lines are char­ac­ter­ized by their uni­ver­sal re­li­ance on nu­mer­ic­al al­gorithms to pro­cess and dis­play large amounts of visu­al in­form­a­tion such as geo­metry, im­ages, and volume data; an un­der­stand­ing of nu­mer­ic­al meth­ods is thus an im­port­ant pre­requis­ite to work­ing in this area. This course will fa­mil­i­ar­ize stu­dents with a range of es­sen­tial nu­mer­ic­al tools to solve prac­tic­al prob­lems in a visu­al com­put­ing con­text.

Con­tents: This course provides a first in­tro­duc­tion to the field of nu­mer­ic­al ana­lys­is with a strong fo­cus on visu­al com­put­ing ap­plic­a­tions. Us­ing ex­amples from com­puter graph­ics, geo­metry pro­cessing, com­puter vis­ion, and com­pu­ta­tion­al pho­to­graphy, stu­dents will gain hands-on ex­per­i­ence with a range of es­sen­tial nu­mer­ic­al al­gorithms. 

The course will be­gin with a re­view of im­port­ant con­sid­er­a­tions re­gard­ing float­ing point arith­met­ic and er­ror propaga­tion in nu­mer­ic­al com­pu­ta­tions. Fol­low­ing this, stu­dents will study and ex­per­i­ment with sev­er­al tech­niques that solve sys­tems of lin­ear and non-lin­ear equa­tions. Since many in­ter­est­ing prob­lems can­not be solved ex­actly, nu­mer­ic­al op­tim­iz­a­tion tech­niques con­sti­tute the second ma­jor top­ic of this course. Stu­dents will solve a vari­ety of prob­lems us­ing non­lin­ear op­tim­iz­a­tion, prin­cip­al com­pon­ent anlys­is, and deep neur­al net­works. The course con­cludes with a re­view of nu­mer­ic­al meth­ods that make ju­di­cious use of ran­dom­ness to solve prob­lems that would oth­er­wise be in­tract­able. 

Stu­dents will have the op­por­tun­ity to gain prac­tic­al ex­per­i­ence with the dis­cussed meth­ods us­ing pro­gram­ming as­sign­ments based on Sci­entif­ic Py­thon.

Pre­requis­ites: Course pre­requis­ites are MATH-101 (Ana­lys­is I) and MATH-111 (Lin­ear Al­gebra). The courses CS-211 (In­tro­duc­tion to visu­al com­put­ing) and MATH-106 (Ana­lys­is II) are re­com­men­ded but not re­quired.

Stu­dents are ex­pec­ted to have good fa­mili­ar­ity with at least one pro­gram­ming lan­guage (e.g. C/C++, Java, Scala, Py­thon, R, Ruby...). The course it­self will rely on Py­thon, but this is straight­for­ward to learn while tak­ing the course. Dur­ing the first weeks of the semester, there will be tu­tori­al ses­sions on us­ing Py­thon and Sci­entif­ic Py­thon.

Al­though it is not a strict pre­requis­ite, this course is highly re­com­men­ded for stu­dents who wish to pur­sue stud­ies in the area of Visu­al Com­put­ing, in par­tic­u­lar: CS-341 (In­tro­duc­tion to com­puter graph­ics), CS-440 (Ad­vanced com­puter graph­ics), CS-442 (Com­puter vis­ion), CS-413 (Com­pu­ta­tion­al Pho­to­graphy), CS-444 (Vir­tu­al Real­ity), and CS-445 (Di­git­al 3D geo­metry pro­cessing) 

Learn­ing out­comes:  At the end of the course, stu­dents should be able to:

  • Write com­puter pro­grams that use nu­mer­ic­al lin­ear al­gebra and ana­lys­is tech­niques to trans­form and visu­al­ize data

  • Reas­on about ways of struc­tur­ing nu­mer­ic­al com­pu­ta­tions ef­fi­ciently.

  • Ana­lyze the nu­mer­ic­al sta­bil­ity of pro­grams built on float­ing point arith­met­ic

  • Re­cog­nize nu­mer­ic­al prob­lems in visu­al com­put­ing ap­plic­a­tions and cast them in­to a form that can be solved or op­tim­ized.

Teach­ing meth­ods: Lec­tures, in­ter­act­ive demos, the­ory and pro­gram­ming ex­er­cises

Ex­pec­ted stu­dent activ­it­ies: Stu­dents are ex­pec­ted to study the provided read­ing ma­ter­i­al and act­ively par­ti­cip­ate in class and in ex­er­cise ses­sions. They will be giv­en both the­or­et­ic­al ex­er­cises and a set of hands-on pro­gram­ming as­sign­ments. 

As­sess­ment meth­ods:

  1. Con­tinu­ous as­sess­ment dur­ing the semester via pro­ject as­sign­ments (50%)
  2. Fi­nal ex­am (50%)

Re­sources: Slides and oth­er re­source will be provided at the end of each class. The course text­book is Nu­mer­ic­al Al­gorithms: Meth­ods for Com­puter Vis­ion, Ma­chine Learn­ing, and Graph­ics by Justin So­lomon (freely avail­able here)

The fol­low­ing op­tion­al ref­er­ences are op­tion­al but highly re­com­men­ded: Sci­entif­ic Com­put­ing: An In­tro­duct­ory Sur­vey (2nd edi­tion) by Mi­chael Heath and What Every Com­puter Sci­ent­ist Should Know About Float­ing-Point Arith­met­ic by Dav­id Gold­berg.

Late policy: the score of late home­work sub­mis­sions is re­duced by -25% per late day.

Aca­dem­ic In­teg­rity: As­sign­ments must be solved and sub­mit­ted in­di­vidu­ally. Do not copy (or even look at) parts of any of the home­works from any­one else in­clud­ing the web. Do not make any parts of your home­work avail­able to any­one, and en­sure that your files are not ac­cess­ible to oth­ers. The uni­versity policies on aca­dem­ic in­teg­rity will be ap­plied rig­or­ously.

Of­fice hours

  • TA of­fice hours:  BC364, Monday 17:00-18:00.
  • Wen­zel's of­fice hours: BC345, Fri­day 11:00-12:00.

Fi­nal ex­am: The ex­am will take place on Thursday 24.01.2019 from 16h15 to 18h15 (CM2CM3)

Schedule

Date Lecturer Contents
19.09.2018 Wenzel Jakob

Lec­ture: Ad­min­is­trat­ive de­tails, over­view of course top­ics, in­tro­duc­tion to Float­ing Point arith­met­ic & er­ror ana­lys­is.

19.09.2018 Merlin Nimier-David

Ex­er­cise: In­tro­duc­tion to Py­thon.

26.09.2018

Home­work 1 pos­ted.

26.09.2018 Helge Rhodin

Lec­ture: Lin­ear sys­tems re­view, LU de­com­pos­i­tion.

Read­ing: So­lomon, Chapter 3.

Home­work 1 re­leased.

26.09.2018 Delio Vicini

Ex­er­cise: In­tro­duc­tion to NumPy.

03.10.2018 Wenzel Jakob

Lec­ture: Con­di­tion­ing of lin­ear sys­tems, In­tro to Least Squares

Read­ing: So­lomon, Chapter 4.

03.10.2018 Tizian Zeltner

Ex­er­cise: Part 1: In­tro­duc­tion to Mat­plot­lib, Part 2: home­work Q&A.

10.10.2018

Home­work 2 pos­ted.

10.10.2018 Wenzel Jakob

Lec­ture: Least Squares con­tin­ued, QR Fac­tor­iz­a­tion, Reg­u­lar­iz­a­tion

Read­ing: So­lomon, Chapter 5 (you can skip over the sec­tion on Gram-Schmidt QR).

Home­work 1 due, home­work 2 re­leased.

17.10.2018 Wenzel Jakob

Lec­ture: How to write ef­fi­cient nu­mer­ic­al code: high-per­form­ance com­put­ing, pro­cessor ar­chi­tec­ture trends, par­al­lel­ism, vec­tor­iz­a­tion.

Read­ing: None.

24.10.2018

Home­work 3 pos­ted.

24.10.2018 Wenzel Jakob

Lec­ture: Sin­gu­lar Value De­com­pos­i­tion

Read­ing: Chapter 6 [up to 6.4.1]

Home­work 2 due, home­work 3 re­leased.

31.10.2018 Wenzel Jakob

Lec­ture: (Non­lin­ear) Root find­ing and op­tim­iz­a­tion (1D)

Read­ing:  So­lomon, Chapter 8, Sec­tion 1: Non­lin­ear Sys­tems (1D case)

07.11.2018

Home­work 4 pos­ted.

07.11.2018 Wenzel Jakob

Lec­ture: Non­lin­ear prob­lems, Mul­tiple vari­ables and Op­tim­iz­a­tion

Read­ing: So­lomon, Chapter 9.

Home­work 3 due, home­work 4 re­leased.

14.11.2018 Wenzel Jakob

Lec­ture: In­ter­pol­a­tion

21.11.2018 Wenzel Jakob

Lec­ture: Nu­mer­ic­al in­teg­ra­tion. 

Read­ing: So­lomon, Chapter 14.1 & 14.2.[1,2,3,5,6]

28.11.2018

Home­work 5, in­clud­ing the data­set was pos­ted on Moodle.

28.11.2018 Helge Rhodin

Lec­ture: Neur­al net­works.

Read­ingNeur­al Net­works and Deep Learn­ing (on­line book), Chapter 1-2

Home­work 4 due, home­work 5 re­leased.

05.12.2018 Helge Rhodin

Lec­ture: Monte Carlo meth­ods.

Read­ing: PhD Thes­is by Wo­j­ciech Jarosz: Ap­pendix A: Monte Carlo In­teg­ra­tionpages 149-157

12.12.2018 Wenzel Jakob

Lec­ture: Markov Chain Monte Carlo (CANCELLED)

19.12.2018 Wenzel Jakob

Lec­ture: Markov Chain Monte Carlo & ex­am re­view.