Mathematical Methods for Computer Vision, Robotics, and Graphics (Fall 2008)

Date | Contents |
---|

This course will focus on the continuous mathematics used in computer science (and EE) with a particular emphasis on the issues associated with designing, implementing and/or using numerical algorithms to solve equations. An underlying theme concerns the approximation issues associated with using floating-point numbers (as opposed to integers) in numerical algorithms.

- Instructor
- Ron Fedkiw (fedkiw@cs.stanford.edu)
- Office: Gates 207
- Office hours: After class (10:45AM-11:45AM)

- Course Assistant
- Avi Robinson-Mosher (avir@stanford.edu)
- Office: Gates 210
- Office hours: Tuesday, 2:30PM - 3:30PM in Gates 210

- Course Assistant
- Michael Lentine (contact.lentine@gmail.com)
- Office: Gates 206
- Office hours: Tuesday, 1:30PM - 2:30PM in Gates 206

Please refer all questions about course material and practices to the CAs
**before** contacting Professor Fedkiw. If you have a question for the CAs, please make sure that it isn't answered
on this webpage before contacting them. Also, please do not show up outside of
scheduled office hours without first making an appointment. When emailing the
CAs, make sure to include "CS205" somewhere in the subject of your message.

- Class: Tuesday and Thursday, 9:30AM-10:45AM in Skill 193
- Discussion: Friday, 11:00AM-11:50AM in Gates B01

*Scientific Computing: An Introductory Survey (2nd edn)*

by Michael T. Heath, McGraw-Hill publishing, New York, 2002 (class textbook) (Amazon Link)

*An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (notes)*

by Jonathan R. Shewchuk, August 1994 (http://www.cs.cmu.edu/~jrs/jrspapers.html)

Please note that you may be able to take the course without owning the textbook but you are still required to be able to access a copy if needed. It is also an excellent resource (it was written by a Stanford graduate) and thus highly recommended.

Notes | |
---|---|

Class |

Class | Description |
---|

Topic | Estimated Length |
---|---|

Sources and measure of numerical errors. Accuracy and stability of numerical calculations |
1 class |

Linear Systems. Existence and uniqueness of a solution. Gaussian elimination and LU factorization. Pivoting. |
1 1/2 classes |

Matrix norms and condition number | 1/2 class |

Cholesky factorization | 1/2 class |

Overconstrained systems. Normal Equations | 1/2 class |

QR factorization. Gram-Schmidt orthonormalization. Householder transform |
1 class |

Eigenvalue problems. Characteristic Polynomial. Similarity transforms. Jordan forms. Power Method | 1 1/2 classes |

Singular Value Decomposition | 1/2 classes |

Nonlinear equations. Fixed point iteration. Newton, secant and bisection methods. Convergence rate. Systems of nonlinear equations. | 1 1/2 classes |

Unconstrained optimization. Golden section search. Newton iteration. Steepest descent method. | 1 class |

Conjugate Gradients Method | 2 1/2 classes |

Preconditioning | 1/2 class |

Constrained optimization. Lagrange multipliers | 1/2 class |

Function interpolation. Polynomial interpolants. Lagrange and Newton interpolation. Splines | 1 class |

Numerical quadrature. Newton-Cotes and Gaussian quadrature. | 1/2 class |

Initial value ODE problems. Stability and accuracy. | 1/2 class |

Forward and Backward Euler, Trapezoidal Rule. Runge-Kutta, TVD and multistep methods. | 1 class |

Newmark integrators. Staggered position/velocity grids. | 1 class |

Boundary value PDE problems. Discretization and solution of the Laplace Equation. The Heat Equation. CFL condition and stability. | 1 class |

There will be a problem set assigned each week which will be posted on Thursday
at 11:59 PM. The homework is due the following Thursday by 11:59 PM, and
solutions will be posted promptly at that time. Homework is considered late if
it is not in the box at the time the solutions are posted to the webpage, and
late homework will receive **no credit**, with absolutely no exceptions.

Homework will be graded in coarse, half-point increments between 0 and 2 points. A sample midterm will be assigned in lieu of normal problems the week before each midterm and graded coarsely out of 3 points.

You may collaborate on homework assignments provided each student writes up his or her own solutions and clearly lists the names of all the students in the group.

Homework |
---|

**Submission**: Homework must be submitted physically in the bin outside
Gates 210. If it is after hours and you cannot get onto the second floor of
gates you can use your Student ID to get into the basement. There is a dropoff
bin inside the Pup cluster. Please only use the bin in the pup cluster if it is
after hours. You can also turn in homework the **Thursday** they are due in class.

No, we do not have a stapler that you can use. Don't even ask.

Homework is available for pickup in Gates 377 in the filing cabinet.

There will be two in-class midterm examinations on October 21st (Class 9) and December 4th (Last Class). Additionally there will be an optional cumulative final on December 8th from 12:15-3:15pm. If you choose not to take the final, your final exam grade will be determined by averaging your two midterm scores. All exams are closed book and closed notes. The final exam will be held in Skilling 193 (the usual classroom). The part of the exam corresponding to the first midterm will run from 12:15-1:30pm, there will be a 15 minute break, and then the part corresponding to the second midterm will run from 1:45-3:00pm.

Section | Proportion |
---|---|

Homework | 20% |

Midterm Exam 1 | 20% |

Midterm Exam 2 | 20% |

Final Exam | 40% |