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.
- 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
Lecture Notes (please do not redistribute)
Exercises
Here are the Matlab files that you will need for the exercises.
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
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(m1.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.