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.
[ Dole and Snell: Random Walks and Electric Networks | Class Notes | Scribe:]
2 Sep 10 T Resistance, Energy and Rayleigh's Monotonicity Law.
[ Class Notes ]
3 Sep 15 T Random Walks the symmetric case.
[ Lovasz: Random Walks on Graphs: A Survey : | Class Notes ]
4 Sep 17 T Random Walks and Eigenvectors
[ Lovasz: Random Walks on Graphs: A Survey : | Class Notes ]
Sep 22 T No Class: Bill Gates visit
5 Sep 24 T Mixing Times for Random Walks
[ Class Notes]
6 Sep 29 T Spring-Mass Systems and Graph Laplacian's
[ Class Notes]
7 Oct 01 T Estimating Lambda_2 for Graph Laplacian's using path embedding.
[ Class Notes]
8 Oct 06 T Eigenvalues of directed graphs and the Perron-Frobenius Theorem
[ Godsil and Royle: | Class Notes]
Hwk-1 out [PDF]
9 Oct 08 T Solving Linear Systems and Nested Dissection
[ Class Notes]
10 Oct 13 T More Nested Dissection, Minimum Degree Heuristic, and Fractals
[ Gilbert and Tarjan | Lipton, Rose, and Tarjan | Class Notes]
11 Oct 15 T The Cheeger inequality
[ Guattery's Notes | Class Notes]
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
[ Hageman and Young Chapters 3-4 | Yousef Saad's Book | Class Notes]
Hwk-2 out [PDF]
14 Oct 27 T Conjugate Gradient Method and Steepest Descent
[ Trefethen and Bau Chapter 38 | Yousef Saad's Book Chap 5 | Class Notes]
15 Oct 29 T Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees
[ Spielman's Class Lecture 16 | Class Notes]
16 Nov 03 T Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees, continued
17 Nov 05 T Support Tree Preconditioners
[ Finding effective support-tree preconditioners | Class Notes]
18 Nov 10 T Fiedler's Thm and Generalized Laplacian's
[ Godsil Royle Chapter 13 | Class Notes ]
19 Nov 12 T Fiedler's Thm Continued and Planar Embeddings
[ Spielman's Tutorial | Class Notes ]
20 Nov 17 T Eigenvalues and Vectors by Iterative Methods
[ Trefethen and Bau Chapter 27 | Trefethen and Bau Chapter 33 | Inverse Powering, see page 19 | Class Notes ]
21 Nov 19 T Arnoldi Iteration and Lanczos Algorithm
[ Class Notes ]
22 Nov 24 T Symmetric Diagonally Dominate Systems;
Spectral Rounding
[ Class Notes on SDD | Class Notes on Spectral Rounding ]
Nov 26 T Thanksgiving
23 Dec 01 T Spectral Methods for Planar Separators
[ Spielman Teng | Class Notes ]
24 Dec 03 T The Stereographic Projection and Eigenvalues and Vectors for Symmetric Tridiagonal Systems
[ Class Notes ]
25 Dec 08 T Eigenvalues and Vectors for Symmetric Tridiagonal Systems by Divide-and-Conquer
[ Trefethen and Bau ]
Room: GHC 6501
26 Dec 10 T Counting and Generating Random Spanning Trees
[ Even: Trees Chapter 2 | Broder: Generating Random Spanning Trees | Class Notes ]
Room: GHC 4303
27 Dec 15 T
Room: GHC 4303