Fundamental Study of the Fill-in Minimization Problem

In this paper the fill-in minimization problem which arises at the application of the sparse matrix method for a large sparse set of linear equations is discussed from the graph-theoretic viewpoint and also through the numerical experiments. Therefore, this investigation consists of two parts, and in the former part the author shows, at first, that the elimination process of a sparse matrix is equivalently replaced to the vertex eliminations for a graph obtained from the matrix, and by use of some concepts in the theory of graph he proves that the vertex elimination process for the minimum fill-in is equivalent to the vertex eliminations for vertices in each subgraph which is obtained by the appropriate dissection of whole graph, and that there are only two types of vertex eliminations through the process. This results in the proposal of a new model of the vertex elimination process. The latter part of this investigation is used for the verification of the results from the theoretic investigation. Through the numerical experiments he concludes that the new model of the vertex elimination process is valid, at least, for a graph like a regular finite element mesh. Furthermore, he shows that this model coincides with Nested Dissection Method which can give the minimum value of fill-in, at present.