- Direct methods: Gaussian elimination
- Symmetry (last time)
- Banded. If half-bandwidth is p, can reduce storage costs
to O(np) and work to O(p
^{2}n) - 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 zeros). - 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.

- 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

Continuing with ...

6. Variations of Gaussian elmination for special systems

- Symmetry (last time)

Spent the rest of the hour looking at the problem statement and model description for the bratwurst problem.