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

Author:
I. S. Duff

Journal:
Math. Comp. **28** (1974), 219-230

MSC:
Primary 65F99

DOI:
https://doi.org/10.1090/S0025-5718-1974-0331756-7

MathSciNet review:
0331756

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**[R]**Robert K. Brayton, Fred G. Gustavson, and Ralph A. Willoughby,*Some results on sparse matrices*, Math. Comp.**24**(1970), 937–954. MR**0275643**, https://doi.org/10.1090/S0025-5718-1970-0275643-8**[I]**S. Duff (1972),*Analysis of Sparse Systems*, D. Phil. Thesis, Oxford University.**[P]**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****[J]**H. Griesmer & R. D. Jenks (1971),*A Set of SCRATCHPAD Examples*, Publication of Thomas J. Watson Research Center, Yorktown Heights, N.Y.**[F]**Frank Harary,*A graph theoretic approach to matrix inversion by partitioning*, Numer. Math.**4**(1962), 128–135. MR**0139545**, https://doi.org/10.1007/BF01386304**[F]**Frank Harary,*The determinant of the adjacency matrix of a graph*, SIAM Rev.**4**(1962), 202–210. MR**0144330**, https://doi.org/10.1137/1004057**[F]**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]**B. R. Heap,*Random matrices and graphs*, Numer. Math.**8**(1966), 114–122. MR**0194355**, https://doi.org/10.1007/BF02163181**[H]**Y. Hsieh & M. S. Ghausi (1971),*Probabilistic Approach to Optimal Pivoting and Prediction of Fill-In for Random Sparse Matrices*, IBM Tech. Report TR 22.1248.**[J]**C. Ogilvie (1968),*The Distribution of Number and Size of Connected Components in Random Graphs of Medium Size*, Proc. IFIP Conf., Edinburgh. Applications 3, Booklet H, pp. 89-92.**[I]**I. Palásti,*On the strong connectedness of directed random graphs*, Studia Sci. Math. Hungar**1**(1966), 205–214. MR**0207588****[I]**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]**S. Parter,*The use of linear graphs in Gauss elimination*, SIAM Rev.**3**(1961), 119–130. MR**0143349**, https://doi.org/10.1137/1003021**[D]**Donald J. Rose and Ralph A. Willoughby (eds.),*Sparse matrices and their applications*, Plenum Press, New York-London, 1972. MR**0331743****[R]**R. P. Tewarson,*The product form of inverses of sparse matrices and graph theory*, SIAM Rev.**9**(1967), 91–99. MR**0218003**, https://doi.org/10.1137/1009004**[J]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422****[R]**A. Willoughby (1971), Talk at Computer Sci. Dept., Univ. of Waterloo. (Unpublished.)

Retrieve articles in *Mathematics of Computation*
with MSC:
65F99

Retrieve articles in all journals with MSC: 65F99

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1974-0331756-7

Keywords:
Sparse random matrix,
Gaussian elimination,
fill-in,
random graphs,
legal paths,
error analysis

Article copyright:
© Copyright 1974
American Mathematical Society