CS3414 Afterclass Notes --- 21 June, 2002
Linear Systems (Chapter 6)
- Direct methods: Gaussian elimination
- Symmetry (last time)
- Banded. If half-bandwidth is p, can reduce storage costs
to O(np) and work to O(p2n)
- General sparse
- Idea: avoid unnecessary storage and work involving lots of
zeros; the typical approach is to attempt to reorder the
rows/cols (equations/unknowns) so as to minimize fill-in
(defined as the introduction of non-zeros where there used to be
- Looked at a contrived example to illustrate the penalty of
fill-in and the possible benefits from reordering.
- Improvements in complexity depend completely on the nonzero
pattern of the matrix.
- There are many sophisticated methods based on graph-theory
to do this.
Spent the rest of the hour looking at the
and model description
for the bratwurst problem.