show/hide this revision's text 2 interchanged the words "rows" and "columns" (since it is the rows which are expensive)

write down the $N^2$ pairs of integers $(n,m)$ with both $n$ and $m$ ranging from $1$ to $N$ ; randomly select a% of them; these are the nonzero elements $M_{nm}$ of your sparse matrix; then evaluate the column row with the largest number of nonzero elements, reflect in the diagonal to get the corresponding rowcolumn, continue with the column row that now has the largest number of nonzero elements, reflect in the diagonal, and so on until you have evaluated all nonzero elements.

note that diagonal elements appear with one half the probability of the offdiagonal elements, which may or may not be what you want; if it is not, just give the pairs $n=m$ double the weight when selecting the nonzero elements.
show/hide this revision's text 1

write down the $N^2$ pairs of integers $(n,m)$ with both $n$ and $m$ ranging from $1$ to $N$ ; randomly select a% of them; these are the nonzero elements $M_{nm}$ of your sparse matrix; then evaluate the column with the largest number of nonzero elements, reflect in the diagonal to get the corresponding row, continue with the column that now has the largest number of nonzero elements, reflect in the diagonal, and so on until you have evaluated all nonzero elements.

note that diagonal elements appear with one half the probability of the offdiagonal elements, which may or may not be what you want; if it is not, just give the pairs $n=m$ double the weight when selecting the nonzero elements.