1. A method comprising: receiving an input matrix containing a plurality of elements, wherein the elements are organized into one or more rows and one or more columns; partitioning the one or more columns of the input matrix into one or more sparse columns and one or more dense columns; determining whether a count of the one or more dense columns exceeds a specified threshold of dense columns; in response to determining that the count exceeds the specified threshold of dense columns, sparsifying the input matrix by at least: randomly selecting an element from the input matrix and, if the element is not already placed in a sparse matrix, placing the element in a corresponding position of the sparse matrix, and in response to a determination that a row of the sparse matrix to which the element belongs exceeds a threshold number of row elements, removing from the row a lowest value element that has a corresponding column of the sparse matrix that exceeds a threshold number of column elements or, if the row does not contain any element that has a corresponding column that exceeds the threshold number of column elements, the lowest value element of the row; repeating said sparsifying the input matrix until each row of the sparse matrix contains the threshold number of the row elements; and repeating said sparsifying the input matrix until a stopping condition has been met; and wherein the method is performed by one or more computing devices.