How to Minimize Fill-ins on Arbitrary Graphs

given a positive definite symmetric matrix,
a permutation of this matrix, such that
the number of zero entries that become non zero
entries is minimized if we apply Gauss elimination
along the diagonal. One is interested to keep a
matrix sparse if one applies Gauss elimination.

This problem translates into a graph problem.
We consider a graph (vertices correspond to
rows and columns) and numbering of the vertices
(the i-th vertex corresponds to the i-th row and column).
i and j are adjacent if the entry of the
i-th column and the j-th row is a non zero entry.
The Gauss elimination process along the diagonal
trans lates into making the neighbors
of the i-th vertex that have a greater number than i
pairwise adjacent where we start with the first vertex, continue
with the second vertex, and so on.

The additional edges are called the fill-in of the graph
and the particular numbering.

The problem is to find, given a graph, find a numbering
of the vertices, such that the fill-in is minimized.

The general problem is NP-complete.

In the first session (Tuesday), I will talk
about the following topics.

1) The problem of Minimum Fill-in

2) Structural Properties of the Fill-in Graph
and of Graphs with no Fill-in (''Chordal Graphs'')

3) NP-Completeness of Minimum Fill-in (Sketch)

4) Subset Minimal Fill-in, Trivial Algorithm and
Efficient Algorithm of Rose, Tarjan, and Lueker

5) Subset Minimal Fill-in can be Arbitrary Bad

6) Heuristics: -Minimum Degree Heuristics
-Nested Dissection(Sketch)

7) Results of Heuristics not Necessarily Minimal
(Examples)

8) Conversion of Orderings into Minimal Elimination Orderings
-Basic Strategy (quite inefficient)
-Improved Strategy by Blair, Heggerness and Telle

Second session, see July 22.