BAP: Lecture 6 (Feb 28, 2002)
The notes for this lecture are available in
In this lecture, we
We finished class with a display of spectral embeddings of graphs.
To try it out yourself, download the code in
the BAP matlab code directory, and type
- saw an example on which partial pivoting has large growth factor.
kahan.m, and stated that this example
remains bad under zero-preserving perturbations, if one modifies
it slightly, kahan2.m.
- proved a bound on the growth factor of total pivoting, which
may be found in Wilkinson's
"Error Analysis of Direct Methods of Matrix Inversion", J ACM 8,
pp. 281-330. (available at JSTOR).
Note that I dropped a log(n)/2 term at the end of the proof.
We briefly discussed the Cuthill-McKee bandwith heuristic and
Turner's ("On the Probable
Performance of Heuristics for Bandwidth Minimization" in SIAM
J. Comput, Vol 15, No 2, May 1986.)
and Feige-Krauthgamer's ('98) smoothed analysis of this heuristic.
- We stated the Lipton-Tarjan planar separator theorem, and discussed how
Lipton-Rose-Tarjan used this separator theorem to speed up Gaussian Elimination
of linear systems with families of separators, such as planar linear systems.
(Generalized nested dissection. SIAM J. on Numerical Analysis, 16:346--358, 1979).
- Finally, we introduced spectral partitioning heuristics, and the spectral
embeddings of graphs from which we may draw some intuition.