Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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.

References [Enhancements On Off] (What's this?)

  • [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.)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F99

Retrieve articles in all journals with MSC: 65F99

Additional Information

Keywords: Sparse random matrix, Gaussian elimination, fill-in, random graphs, legal paths, error analysis
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society