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 
SpringMass 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 PerronFrobenius Theorem 
Hwk1 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 
Hwk2 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
DivideandConquer 
Room: GHC 6501

26 
Dec 10 
T 
Counting and Generating Random Spanning Trees 
Room: GHC 4303

27 
Dec 15 
T 

Room: GHC 4303 