1. On the number of nonzeros added when Gaussian elimination is performed on sparse random matrices
- Author
-
Iain S. Duff
- Subjects
Random graph ,Discrete mathematics ,Algebra and Number Theory ,Applied Mathematics ,Graph theory ,Combinatorics ,Computational Mathematics ,symbols.namesake ,Matrix (mathematics) ,Gaussian elimination ,Random regular graph ,symbols ,Graph (abstract data type) ,Adjacency matrix ,Random matrix ,Mathematics - Abstract
This paper studies the fill-in properties of Gaussian elimination on sparse random matrices. A theoretical study using the concept of random graphs yields formulae from which the fill-in can be evaluated. The predictions are examined for matrices of various orders and densities and are found to be in close agreement with experimental results. A possible consequence of the results of this paper relating to error analysis for sparse systems is given in the concluding section. 1. Introduction. This paper studies the fill-in properties of Gaussian elimina- tion on sparse random matrices. Graph theoretical ideas are introduced and the problem is examined using the concept of random graphs. This concept of using random graphs is not a new one. They are used as a tool in the development of existence theorems in graph theory (Erdos (1967)) and some work has been done on the structure of a graph where the number of lines is a function of the number of points, the analysis holding in the limit as the number of points tends to infinity (Palasti (1966, 1970)). Ogilvie (1968) has shown that these asymptotic results hold where the graph has only a small number of vertices (about 10) but none of this work is directly concerned with matrix decomposition or indeed with the adjacency matrix of the graph. Heap (1966) has extended the notion of random graphs to examine properties of their adjacency matrices. However, his Tesults on matrix reducibility are only valid for comparatively dense matrices (prob- ability density > 0.15). A serious attempt to tackle the problem of this paper has been made by Hsieh and Ghausi (1971) where they have tried to make theoretical predictions on the results of Brayton et al. (1970). Their work has, however, several serious defects. Although they make more allowance for interaction than the discus- sion in Section 2, their formulae only include correlation between elements in the same column ignoring the correlation which exists between elements in the same row. In addition, some of their formulae break down if the density of the matrix increases above 20% and their correlation factor H is chosen empirically to obtain a fit with Brayton's data rather than determined theoretically. The impetus for writing this paper came from remarks by Robert Brayton in the panel at the end of the IBM symposium (Rose and Willoughby (1972)) when he stated that the above problem, although itself not perhaps of devastating importance, has consumed vast
- Published
- 1974