A sparse matrix is a matrix that allows special techniques to take advantage of the large number of "background" (commonly zero) elements. The number of zeros a matrix needs in order to be considered "sparse" depends on the structure of the matrix and the desired operations to perform on it. For example, a randomly generated sparse n×n matrix with c n entries scattered randomly throughout the matrix is not sparse in the sense of Wilkinson (for direct methods) since it takes O(n^3) time to factor (with high probability and for large enough c; Gilbert et al. 1992).