Tentative Schedule

This schedule is very preliminary: the number of lectures and order of the topics are likely to change.

Lec. Date Day Topic Notes
Aug 25 T No Class
Aug 27 T No Class
Sep 01 T No Class
Sep 03 T No Class
1 Sep 08 T Introduction and Course topics, Introduced Graph Laplacian, Effective Resistance, and Random Walks.
2 Sep 10 T Resistance, Energy and Rayleigh's Monotonicity Law.
3 Sep 15 T Random Walks the symmetric case.
4 Sep 17 T Random Walks and Eigenvectors
Sep 22 T No Class: Bill Gates visit
5 Sep 24 T Mixing Times for Random Walks
6 Sep 29 T Spring-Mass Systems and Graph Laplacian's
7 Oct 01 T Estimating Lambda_2 for Graph Laplacian's using path embedding.
8 Oct 06 T Eigenvalues of directed graphs and the Perron-Frobenius Theorem Hwk-1 out [PDF]
9 Oct 08 T Solving Linear Systems and Nested Dissection
10 Oct 13 T More Nested Dissection, Minimum Degree Heuristic, and Fractals
11 Oct 15 T The Cheeger inequality
12 Oct 20 T The Cheeger inequality Continued
Hwk 0 due (Solutions PDF)
13 Oct 22 T Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration Hwk-2 out [PDF]
14 Oct 27 T Conjugate Gradient Method and Steepest Descent
15 Oct 29 T Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees
16 Nov 03 T Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees, continued
17 Nov 05 T Support Tree Preconditioners
18 Nov 10 T Fiedler's Thm and Generalized Laplacian's
19 Nov 12 T Fiedler's Thm Continued and Planar Embeddings
20 Nov 17 T Eigenvalues and Vectors by Iterative Methods
21 Nov 19 T Arnoldi Iteration and Lanczos Algorithm
22 Nov 24 T Symmetric Diagonally Dominate Systems;
Spectral Rounding
Nov 26 T Thanksgiving
23 Dec 01 T Spectral Methods for Planar Separators
24 Dec 03 T The Stereographic Projection and Eigenvalues and Vectors for Symmetric Tridiagonal Systems
25 Dec 08 T Eigenvalues and Vectors for Symmetric Tridiagonal Systems by Divide-and-Conquer Room: GHC 6501
26 Dec 10 T Counting and Generating Random Spanning Trees Room: GHC 4303
27 Dec 15 T
Room: GHC 4303