6. Variations of Gaussian elmination for special systems
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
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.