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 Free Access

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]**K. Brayton, F. G. Gustavson & R. A. Willoughby (1970), "Some results on sparse matrics,"*Math. Comp.*, v. 24, pp. 937-954. MR**43**#1396. MR**0275643 (43:1396)****[I]**S. Duff (1972),*Analysis of Sparse Systems*, D. Phil. Thesis, Oxford University.**[P]**Erdös (1967),*Applications of Probabilistic Methods to Graph Theory*, Seminar on Graph Theory (edited by F. Harary), Holt, Rinehart and Winston, New York, pp. 60-64. MR**36**#68. MR**0216973 (36:68)****[J]**H. Griesmer & R. D. Jenks (1971),*A Set of SCRATCHPAD Examples*, Publication of Thomas J. Watson Research Center, Yorktown Heights, N.Y.**[F]**Harary (1962a), "A graph theoretic approach to matrix inversion by partitioning,"*Numer. Math.*, v. 4, pp. 128-135. MR**25**#2977. MR**0139545 (25:2977)****[F]**Harary (1962b), "The determinant of the adjacency matrix of a graph,"*SIAM Rev.*, v. 4, pp. 202-210. MR**26**#1876. MR**0144330 (26:1876)****[F]**Harary, R. Z. Norman & D. Cartwright (1965),*Structural Models*:*An Introduction to the Theory of Directed Graphs*, Wiley, New York. MR**32**#2345. MR**0184874 (32:2345)****[B]**R. Heap (1966), "Random matrices and graphs,"*Numer. Math.*, v. 8, pp. 114-122. MR**33**#2565. MR**0194355 (33:2565)****[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]**Palásti (1966), "On the strong connectedness of directed random graphs,"*Studia Sci. Math. Hungar.*, v. 1, pp. 205-214. MR**34**#7403. MR**0207588 (34:7403)****[I]**Palásti (1970), "On some structured properties of given types of random graphs,"*Magyar Tud. Akad. Mat. Fiz. Oszt. Közl.*, v. 19, pp. 33-72. (Hungarian) MR**41**#5236. MR**0260612 (41:5236)****[S]**V. Parter (1961), "The use of linear graphs in Gauss elimination,"*SIAM Rev.*, v. 3, pp. 119-130. MR**26**#908. MR**0143349 (26:908)****[D]**J. Rose & R. A. Willoughby (Editors) (1972),*Sparse Matrices and their Applications*, Proc. Conf. IBM Research Center, Plenum Press, New York. MR**0331743 (48:10075)****[R]**P. Tewarson (1967), "On the product form of inverses of sparse matrices and graph theory,"*SIAM Rev.*, v. 9, pp. 91-99. MR**36**#1092. MR**0218003 (36:1092)****[J]**H. Wilkinson (1965),*The Algebraic Eigenvalue Problem*, Clarendon Press, Oxford. MR**32**#1894. MR**0184422 (32:1894)****[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