On the number of nonzeros added when Gaussian elimination is performed on sparse random matrices

Duff, I. S.

doi:10.1090/S0025-5718-1974-0331756-7

On the number of nonzeros added when Gaussian elimination is performed on sparse random matrices
HTML articles powered by AMS MathViewer

by I. S. Duff PDF

Math. Comp. 28 (1974), 219-230 Request permission

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.

References

Robert K. Brayton, Fred G. Gustavson, and Ralph A. Willoughby, Some results on sparse matrices, Math. Comp. 24 (1970), 937–954. MR 275643, DOI 10.1090/S0025-5718-1970-0275643-8

Analysis of Sparse Systems

Paul Erdős, Applications of probabilistic methods to graph theory, A Seminar on Graph Theory, Holt, Rinehart and Winston, New York, 1967, pp. 60–64. MR 0216973

A Set of SCRATCHPAD Examples

Frank Harary, A graph theoretic approach to matrix inversion by partitioning, Numer. Math. 4 (1962), 128–135. MR 139545, DOI 10.1007/BF01386304
Frank Harary, The determinant of the adjacency matrix of a graph, SIAM Rev. 4 (1962), 202–210. MR 144330, DOI 10.1137/1004057
Frank Harary, Robert Z. Norman, and Dorwin Cartwright, Structural models: An introduction to the theory of directed graphs, John Wiley & Sons, Inc., New York-London-Sydney, 1965. MR 0184874
B. R. Heap, Random matrices and graphs, Numer. Math. 8 (1966), 114–122. MR 194355, DOI 10.1007/BF02163181

Probabilistic Approach to Optimal Pivoting and Prediction of Fill-In for Random Sparse Matrices

The Distribution of Number and Size of Connected Components in Random Graphs of Medium Size

I. Palásti, On the strong connectedness of directed random graphs, Studia Sci. Math. Hungar. 1 (1966), 205–214. MR 207588
Ilona Palásti, On some structural properties of given types of random graphs, Magyar Tud. Akad. Mat. Fiz. Oszt. Közl. 19 (1970), 33–72 (Hungarian, with English summary). MR 0260612
S. Parter, The use of linear graphs in Gauss elimination, SIAM Rev. 3 (1961), 119–130. MR 143349, DOI 10.1137/1003021
Donald J. Rose and Ralph A. Willoughby (eds.), Sparse matrices and their applications, Plenum Press, New York-London, 1972. MR 0331743
R. P. Tewarson, The product form of inverses of sparse matrices and graph theory, SIAM Rev. 9 (1967), 91–99. MR 218003, DOI 10.1137/1009004
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422