Skip navigation

CS448J: Concepts and Algorithms of Scientific and Visual Computing

Prof. Dominik L. Michels, Stanford University.
Autumn 2015, TTh 10:30-11:50, R 200-107.


This course covers a selection of fundamental concepts and algorithms for scientific and visual computing. Based on prior knowledge in basis calculus, linear algebra, numerical interpolation and optimization, this course introduces the concept of the phase space, variational principles, methods for ordinary and partial differential equations, Fourier analysis, and multiscale modeling. The lecture is algorithmically oriented, aiming to enable the students to develop efficient solutions for practically relevant problems, based on solid theoretical foundations and mathematically precise modeling. It covers practical applications, like the simulation of rigid and deformable objects, fibers, fluids, molecular dynamics, signal/image analysis and processing, as well as wavelet-based modeling on different scales.


The course will assume basic knowledge such as taught in MATH41, MATH42, CS103, or CS205A. It is suitable for undergraduate as well as for graduate students.


(1) Phase Space
(i) Configurations and Trajectories
(ii) Generalized Coordinates
(iii) Constraints

Application: Phase Space Analysis

(2) Variational Principles
(i) Calculus of Variations
(ii) Euler Lagrange Equation
(iii) Canonical Equations

Application: Systems of Coupled Oscillators, Particle Systems
Application: Variational-based Image Segmentation

(3) Ordinary Differential Equations (ODEs)
(i) Cauchy Problems for ODEs
(ii) Stability, Explicit and Implicit Integration
(iii) Runge Kutta Methods (RK), Verlet Integration
(iv) Symplecticity and Variational Integrators
(v) Stiff Differential Equations
(vi) Splitting Methods
(vii) Implicit-explicit Integration Methods (IMEX)
(viii) Semi-analytical Methods
(ix) Time-scale Segmentation
(x) Constraint Methods
(xi) Lagrange-multiplier-based Methods
(xii) SHAKE and RATTLE Method

Application: Simulation of Deformable Objects
Application: Rigid Body Dynamics
Application: Molecular Dynamics

(4) Partial Differential Equations (PDEs)
(i) Cauchy Problems for PDEs
(ii) Hamilton-Jacobi Equation (HJE) and Level Set Method (LSM)
(iii) Finite Difference Method (FDM)
(iv) Finite Element Method (FEM)
(v) Boundary Element Method (BEM)
(vi) Lie Theory

Application: Fiber Simulation (Cosserat Equations)
Application: Fluid Simulation (Navier-Stokes Equations)

(5) Fourier Analysis
(i) Function Spaces
(ii) Banach and Hilbert Spaces
(iii) Lebesgue Spaces
(iv) Fourier Transform (FT)
(v) Continuous-time Fourier Transform (CTFT)
(vi) Discrete-time Fourier Transform (DTFT)
(vii) Windowed Fourier Transform (WFT)
(viii) Fast Fourier Transform (FFT)
(ix) Multidimensional Fourier Transform
(x) Discrete Cosine Transform (DCT)

Application: Signal Analysis and Filtering
Application: Image Compression

(6) Multiscale Modeling
(i) Wavelets
(ii) Continuous-time Wavelet Transform (CTWT)
(iii) Haar’s Theorem
(iv) Multiresolution Analysis (MRA)
(v) Fast Wavelet Transform (FWT)
(vi) Multiscale Methods

Application: Hierarchical Spacetime Control
Application: Wavelet Importance Sampling

(7) Outlook
(i) Advanced Models of Computation
(ii) Quantum Computing

Lecture Notes / Slides

The topics are illustrated on the blackboard as well as using the following slides. Please keep in mind, that the slides do not cover the whole content of the lecture.

09-22: Phase Space
09-24: Variational Principles
09-29: Canonical Equations
10-01: Image Segmentation
10-06: Ordinary Differential Equations
10-08: Symplecticity
10-13: Stiff Differential Equations
10-15: Constraint Methods
10-20: Partial Differential Equations
10-22: Finite Element Method
10-27: Lie Theory
10-29: Fourier Analysis
[11-03/05: Signal Analysis (by D. Hyde)]
11-10: Discrete Fourier Transforms
11-12: Fast Fourier Transform
11-17: Wavelets
11-19: Multiresolution Analysis
[11-24/26: (Thanksgiving Recess)]
12-01: Advanced Computation Models
12-03: Quantum Algorithms

Student Work

There will be a problem set assigned each week, which will be graded. This homework track is mostly theoretical, but it will include a final project and smaller programming tasks along the way. The final project will consist of writing a simulator for one of the main types of phenomena discussed in the course. The students may collaborate on the assignments provided each student writes up his or her own solutions and clearly lists the names of all the students in the group. There will be no midterm or final exam.

Exercise Sheets

The Homework is due every Tuesday. Written solutions should be handed in before the lecture. Programming assignments must be submitted by email to your tutor.

00: Warming-up (0 Points, not graded)
01: Variational Principles (20 Points, due Oct 6)
02: Classical Variational Problems (18 Points, due Oct 13)
03: Integrating Ordinary Differential Equations (20 Points, due Oct 20)
04: Fermi Pasta Ulam Problem (10 Points, due Oct 27)
05: Heat Equation (15 Points, due Nov 3)
06: Fourier Analysis (12 Points, due Nov 10)
07: Fourier Transforms (17 Points, due Nov 17)
08: Fast Fourier Transform (22 Points, due Nov 24, electronic submission)
09: Multiresolution Analysis (16 Points, due Dec 1)


Solutions to selected exercises are provided for the students.

00-5: Analysis of Algorithms
01-1: Double Pendulum
01-3: Fundamental Lemma
02-X: Classical Variational Problems
02-X: Classical Variational Problems (by W. Lin)
03-1: Foucault Pendulum
03-2: Verlet Integration
04-1: Fermi Pasta Ulam Problem
05-1: Heat Equation (HeatEquation.m, hls2rgb.m, stanford.png)
06-1: Fourier Analysis
07-X: Fourier Transforms
08-X: Fast Fourier Transform
09-X: Multiresolution Analysis

Grading Policy

Assignments: 25%, Final Project: 75%.

Honor Code

The university expects both faculty and students to respect and follow Stanford’s Honor Code.


S. Arora, B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
J.-L. Basdevant. Variational Principles in Physics. Springer, 2007.
I. Daubechies. Ten Lectures on Wavelets. SIAM, 1992.
W. Hackbusch. Multi-Grid Methods and Applications. Springer, 2010.
J.M. Haile. Molecular Dynamics Simulation: Elementary Methods. Wiley, 1997.
E. Hairer, S.P. Nørsett. Solving Ordinary Differential Equations I: Nonstiff Problems. Springer, 2009.
E. Hairer, C. Lubich. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Springer, 2010.
E. Hairer, G. Wanner. Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. Springer, 2010.
G. Kaiser. A Friendly Guide to Wavelets. Birkhäuser Classics, 2011.
L.D. Landau, E.M. Lifshitz. Mechanics, Third Edition, Course of Theoretical Physics, Volume 1. Butterworth-Heinemann, 1982.
R.H. Landau, M.J. Páez, C.C. Bordeianu. Computational Physics: Problem Solving with Computers. Wiley, 2007.
A. Mitiche, I.B. Ayed. Variational and Level Set Methods in Image Segmentation. Springer, 2011.
R.M. Murray, Z.Li, S.S. Sastry. A Mathematical Introduction to Robotic Manipulation. CRC Press, 1994.
S. Osher, R. Fedkiw. Level Set Methods and Dynamic Implicit Surfaces. Springer, 2002.
E.M. Stein. Fourier Analysis: An Introduction. Princeton University Press, 2003.
G. Strang. Computational Science and Engineering. Wellesley-Cambridge Press, 2007.
O.C. Zienkiewicz, R.L. Taylor, J.Z. Zhu. The Finite Element Method: Its Basis and Fundamentals. Butterworth-Heinemann, 2013.

Course Staff

Instructor: Prof. Dominik L. Michels
Office: 208 Gates CS Bldg.
Office Hours: F 10-12

Course Assistant: David Hyde
Office: 209 Gates CS Bldg.
Office Hours: F 10-12