RGL
Realistic Graphics Lab
EPFL Logo

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

Wednesday
2-4pm (Lecture)
4-5pm (Exercise)
Wenzel Jakob
Instructor
Andreas Finke
Teaching Assistant
Bugra Tekin
Teaching Assistant
Julia Proskurnia
Teaching Assistant
Leonardo Impett
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 learn how prin­cip­al com­pon­ent ana­lys­is can be lever­aged to com­press or re­duce the di­men­sion of large data­sets to make them easi­er to store and ana­lyze. 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: we of­fer the fol­low­ing of­fice hours:

  • Wen­zel Jakob: Monday 3:15-4:15 pm, BC 345 (weekly)
  • Ju­lia Proskur­nia & An­dreas Finke: Tues­day 1:45-2:45 pm, BC 147 (even-numbered weeks)
  • Bu­gra Tekin & Le­onardo Im­pett: Fri­day 10-11 am, BC 317 (odd-numbered weeks)

Fi­nal Ex­am: Fri­day 27.01.2017 from 08h15 to 11h15 (PO01). A few re­marks:

  • Please bring a black or blue ink pen. Pen­cils are not per­mit­ted.
  • Make sure to ar­rive suf­fi­ciently early and find the seat as­signed to you (the seat as­sign­ments are pos­ted on pa­per sheets at the ex­am loc­a­tion).
  • You must bring your ID card for iden­ti­fic­a­tion pur­poses and place it in front of your­self.
  • You are al­lowed to bring a single (1) writ­ten or prin­ted A4 page con­tain­ing per­son­al notes (you can use both sides). However, books and oth­er aids (laptops, cal­cu­lat­ors, smart­phones, smart­watches, etc.) are not per­mit­ted.
  • Ex­tra empty pa­per is provided dur­ing the ex­am if needed, there is no need to bring your own.

Schedule

Date Lecturer Contents
21.09.2016 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.

Read­ing: So­lomon, Chapter 1 (everything ex­cept Lag­range Mul­ti­pli­ers) & Chapter 2.

21.09.2016 Wenzel Jakob

Ex­er­cise: Py­thon & SciPy ba­sics

28.09.2016

Home­work 1 re­leased: get it here. Due in 2 weeks on Wed­nes­day 12/10 (be­fore class).

28.09.2016 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, SIMD vec­tor­iz­a­tion.

28.09.2016 Bugra Tekin

Ex­er­cise: NumPy/SciPy/Mat­plot­lib tu­tori­al (con­tin­ued)

30.09.2016

Re­gis­tra­tion dead­line

05.10.2016 Wenzel Jakob

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

Read­ing: So­lomon, Chapter 3.

05.10.2016 Andreas Finke

Ex­er­cise: Solv­ing lin­ear sys­tems in SciPy, Vec­tor­iz­ing a Sphere Ray Tracer.

12.10.2016 Wenzel Jakob

Lec­ture: Con­di­tion­ing of lin­ear sys­tems, Ap­plic­a­tions of Lin­ear Sys­tems

Read­ing: So­lomon, Chapter 4.

12.10.2016

No ex­er­cise ses­sion

19.10.2016 Wenzel Jakob

Lec­ture: QR Fac­tor­iz­a­tion, Least Squares Op­tim­iz­a­tion

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

19.10.2016 Leonardo Impett

Ex­er­cise: re­view of home­work as­sign­ment 1.

21.10.2016

Home­work 2 re­leased: get it here. It is due in 2 weeks on Fri­day 4/11.

26.10.2016 Wenzel Jakob

Lec­ture: Ei­gen­ana­lys­is & Sin­gu­lar Value De­com­pos­i­tion

Read­ing: Chapter 6 [up to 6.4.1]

26.10.2016

Ex­er­cise: ses­sion on home­work as­sign­ment 2.

02.11.2016 Wenzel Jakob

Lec­ture: The Sin­gu­lar Value De­com­pos­i­tion, con­tin­ued.

02.11.2016

Ex­er­cise: ses­sion on home­work as­sign­ment 2.

Ex­tra ma­ter­i­al re­view ques­tions.

09.11.2016 Wenzel Jakob

No Lec­ture / Ex­er­cise

16.11.2016 Wenzel Jakob

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

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

16.11.2016

No Ex­er­cise ses­sion

21.11.2016

Home­work 3 re­leased, get it here.

23.11.2016 Wenzel Jakob

Lec­ture: mul­ti­di­men­sion­al non­lin­ear equa­tions, op­tim­iz­a­tion.

23.11.2016 Andreas Finke

Dis­cus­sion of home­work 2 solu­tions.

25.11.2016

Drop dead­line

30.11.2016 Wenzel Jakob

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

30.11.2016

Ex­er­cise: Q&A for Home­work 3.

07.12.2016 Wenzel Jakob

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

07.12.2016 Leonardo Impett

Ex­er­cise: re­view of Home­work 3 solu­tions.

08.12.2016

Home­work 4 re­leased: get it here. It is due in 2 weeks on Thursday 22.12.

14.12.2016 Wenzel Jakob

Lec­ture: Monte Carlo meth­ods

14.12.2016

Ex­er­cise: home­work 4 Q&A.

21.12.2016 Wenzel Jakob

Lec­ture: Prac­tice ex­am

21.12.2016

Ex­er­cise: home­work 4 Q&A.

27.01.2017

Fi­nal Ex­am