A Note on Probabilistic Analysis of a Sparse Matrix Factorization Scheme and Random Graphs
David Aldous · Probability in the Engineering and Informational Sciences · 1993
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.