Support-Preconditioning Materials and Publications

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.

1. Introduction + Graphs/Matrices/Laplacians
   Exercise: An interesting application of Laplacians 
                    + first part of augmented spanning trees exercise
2. Iterative solvers
   Exercise: dropping a few edges
                    + second part of augmented spanning trees
3. Sparse direct solvers
   Exercise: banded and low-profile matrices
                    + third part of augmented spanning trees
4. Support theory and spectral bounds + graph embeddings + augmented spanning trees
   Exercise: last part of augmented spanning trees
5. Finite elements by element approximations + finite-elements by fretsaw + advanced topics
   excercise: diagonally-dominant approximations

Lecture Notes (please do not redistribute)

• 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)

Exercises

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

Core publications

• 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

Finite Elements

• 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

Matrices and Graphs

• 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.

Sophisticated Graph Algorithms for Constructing Preconditioners

• 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.

Some non-preconditioning applications

• 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.