Search

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

The method recognizes that construction of a tree (and hence the pertinent graph) from a given matrix can be done by inspection once the pattern of its growth has been established. To this end it is only necessary that we have a mechanism, applicable to a given cut-set matrix, which sorts out those rows that correspond to the outermost twigs or tips of the tree, for we can then form an abbridged cut-set matrix corresponding to what is left of the total graph after the tree tips with their uniquely attached links are pruned away. This remainder again has tips which can be found and eliminated in the same way. Continuation thus reveals the desired growth pattern. Since the method cannot fail to yield a graph if its existence is compatible with the structure of the given matrix, it may be regarded as a constructive test for fulfillment of necessary and sufficient conditions.

A cellular array is a two-dimensional, checkerboard type interconnection of identical modules (or cells), where each cell contains a few bits of memory and a small amount of combinational logic, and communicates mainly with its immediate neighbors in the array. The chief computational advantage offered by cellular arrays is the improvement in speed achieved by virtue of the possibilities for parallel processing. In this paper it is shown that cellular arrays are inherently well suited for the solution of many graph problems. For example, the adjacency matrix of a graph is easily mapped onto an array; each matrix element is stored in one cell of the array, and typical row and column operations are readily implemented by simple cell logic. A major challenge in the effective use of cellular arrays for the solution of graph problems is the determination of algorithms that exploit the possibilities for parallelism, especially for problems whose solutions appear to be inherently serial. In particular, several parallelized algorithms are presented for the solution of certain spanning tree, distance, and path problems, with direct applications to wire routing, PERT chart analysis, and the analysis of many types of networks. These algorithms exhibit a computation time that in many cases grows at a rate not exceeding log 2 n , where n is the number of nodes in the graph. Straightforward cellular implementations of the well-known serial algorithms for these problems require about n steps, and noncellular implementations require from n 2 to n 3 steps.

Graph techniques together with the nonharmonic series representation of stationary Gaussian signals can be used in the analysis of a wide class of nonlinear systems. This point is illustrated by the derivation of the moments of a nenlinear functional of a Gaussian signal. A graphical method is developed for the derivation of the time average of products of functions of a stationary Gaussian signal without resort to any probability theory considerations. Consequently, the derivation of the moments of the functional reduces to a graph enumeration procedure and the computation of a finite number of integrals.

A simple algorithm for the simplification of signal-flow graphs is given, and an interesting connection with Rosen-brock's system matrix is shown.