Here is a tentative agenda for the five days of the course.
The list
includes the topics that I plan to cover each day (this corresponds to
the lecture notes) and the exercise for that day.

- Introduction + Graphs/Matrices/Laplacians

Exercise: An interesting application of Laplacians

+ first part of augmented spanning trees exercise - Iterative solvers

Exercise: dropping a few edges

+ second part of augmented spanning trees - Sparse direct solvers

Exercise: banded and low-profile matrices

+ third part of augmented spanning trees - Support theory and spectral bounds + graph embeddings +
augmented spanning trees

Exercise: last part of augmented spanning trees - Finite elements by element approximations + finite-elements
by fretsaw + advanced topics

excercise: diagonally-dominant approximations

- Introduction
- Iterative Solvers
- Sparse Direct Solvers
- Graphs, Matrices, Laplacians
- Support Theory and Spectral Bounds
- Graph Embeddings and Combinatorial Support Bounds
- Augmented Spanning-Tree Preconditioners
- We will also cover advanced material from the two papers listed in red below.
- (Appendix: definitions of eigenvalues, singular values, and generalized eigenvalues)

Here are the Matlab files that you will need for the exercises.

- An Interesting Application of Laplacians
- Dropping a Few Edges from a Graph Preconditioner
- The exercise on banded and profile matrices in the lecture notes on direct solvers.
- Constructing Augmented Spanning Trees
- Diagonally-Dominant Approximations of Finite-Element Matrices

- Erik G. Boman and Bruce Hendrickson

Support Theory for Preconditioning

SIAM Journal on Matrix Analysis and Applications 25 (3): 694--717, (2003). - Marshall Bern, John R. Gilbert, Bruce
Hendrickson, Nhat Nguyen, and Sivan Toledo.

Support-graph preconditioners.

*SIAM Journal on Matrix Analysis and Applications*, 27:930-951, 2006. - Doron Chen, John R. Gilbert, and Sivan Toledo.

Obtaining bounds on the two norm of a matrix from the splitting lemma.

*Electronic Transactions on Numerical Analysis*, 21:28-46, 2005. - Doron Chen and Sivan Toledo.

Vaidya's preconditioners: Implementation and experimental study.

*Electronic Transactions on Numerical Analysis*, 16:30-49, 2003. - Anil Joshi

Topics in Optimization and Sparse Linear Systems.

Ph.D. Thesis, University of Illinois at Urbana-Champaign, 1997 - Keith D. Gremban

Combinatorial Preconditioners for Sparse, Diagonally Dominant Linear Systems.

Ph.D. Thesis, Carnegie Mellon University, 1996 - John Reif

Efficient Approximate Solution of Sparse Linear Systems + errata

Computers and Mathematics with Applications 36(9): 37--58 (1998) - Vicki Howle and Stephen Vavasis

Preconditioning Complex-Symmetric Layered Systems Arising in Electrical Power Modeling

- Haim Avron, Doron
Chen, Gil Shklarski, and Sivan
Toledo.

Combinatorial preconditioners for scalar elliptic finite-elements problems.

Submitted to*SIAM Journal on Matrix Analysis and Applications*, November 2006. - Gil Shklarski and
Sivan Toledo.

Rigidity in finite-element matrices: Sufficient conditions for the rigidity of structures and substructures.

Submitted to*SIAM Journal on Matrix Analysis and Applications*, January 2006. - Erik G. Boman, Bruce Hendrickson and Stephen Vavasis

Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners

Manuscript, Sandia National Lab. and Cornell

- Erik G. Boman, Doron Chen, Ojas Parekh, and
Sivan Toledo.

On the factor-width and symmetric H-matrices.

*Numerical Linear Algebra with Applications*, 405:239-248, 2005. - Erik G. Boman, Doron Chen, Bruce Hendrickson,
and Sivan Toledo.

Maximum-weight-basis preconditioners.

*Numerical Linear Algebra with Applications*, 11:695-721, 2004. - Doron Chen and Sivan Toledo.

Combinatorial characterization of the null spaces of symmetric H-matrices.

*Linear Algebra and its Applications*, 392:71-90, 2004.

- Daniel A. Spielman and Shang-Hua Teng

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in time**O(m**.^{1.31})

In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 416--427, Cambridge, MA, October 2003. - Daniel A. Spielman and Shang-Hua Teng

Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems

In Proceedings of the 36th ACM Symposium on Theory of Computing, pages 81--90, 2004. - Michael Elkin, Yuval Emek, Daniel A. Spielman and
Shang-Hua Teng

Lower-Stretch Spanning Trees

Proceedings of the 37th annual ACM symposium on Theory of computing, Baltimore, pages 494--503, 2005 - Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan
Leung Maverick Woo

Finding Effective Support-Tree Preconditioners

In Proceedings of the 17th ACM Symposium on Parallel Algorithms and Architectures, Las Vegas, 2005.

- Olga Sorkine, Daniel Cohen-Or, Dror Irony, and Sivan
Toledo.

Geometry-aware bases for shape approximation.

*IEEE Transactions on Visualization and Computer Graphics*, 11:171-180, 2005. - Olga Sorkine, Doron Chen, Daniel Cohen-Or, , and Sivan
Toledo.

Algebraic analysis of high-pass quantization.

*ACM Transactions on Graphics*, 34 pages, to appear, September 2003.