Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T10:12:41.234Z Has data issue: false hasContentIssue false
  • English
  • Français

A Note on Probabilistic Analysis of a Sparse Matrix Factorization Scheme and Random Graphs

Published online by Cambridge University Press:  27 July 2009

David Aldous
David Aldous
Affiliation:
Department of Statistics, University of California, Berkeley, California 94720
Get access Rights & Permissions [Opens in a new window]

Abstract

Known results in random graph theory lead easily to a quantitative result on the number of multiplications needed in a matrix factorization algorithm, under the assumption that non-zero entries are randomly distributed.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 7 , Issue 4 , October 1993 , pp. 465 - 469
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Bollobas, B. (1985). Random graphs. London: Academic Press.Google Scholar
2.Lipton, R.J., Rose, D.J., & Tarjan, R.E. (1979). Generalized nested dissection. SIAM Journal of Numerical Analysis 16: 346–358.CrossRefGoogle Scholar
3.Liu, J.W.H. (1992). The multifrontal method for sparse matrix solution: Theory and practice. SIAM Review 34: 82–109.CrossRefGoogle Scholar
4.Rose, D.J., Tarjan, R.E., & Lueker, G.S. (1976). Algorithmic aspects of vertex elimination on graphs. SIAM Journal of Computing 5: 266–283.CrossRefGoogle Scholar