# On the Computational Efficiency of SparseArrays

I am getting much more averaged computation time by using sparse matrices structure. Is there something wrong on my code? I used a quick test script to test multiplication of both data structure.

``````using SparseArrays, Statistics

n=1000
N=1000
T = 10

t1_hist = Array{Float64}(undef, 1, T)
t2_hist = Array{Float64}(undef, 1, T)

for i in 1:T

fmatrix_1 = [rand(n,n) zeros(n,N); zeros(N,n) zeros(N,N)]
fmatrix_2 = [rand(n,n) zeros(n,N); zeros(N,n) zeros(N,N)]

spmatrix_1 = sparse([rand(n,n) spzeros(n,N); spzeros(N,n) spzeros(N,N)])
spmatrix_2 = sparse([rand(n,n) spzeros(n,N); spzeros(N,n) spzeros(N,N)])

t1_hist[i] = @elapsed fmatrix_1 * fmatrix_2;
t2_hist[i] = @elapsed spmatrix_1 * spmatrix_2;

end

println("     Full Matrix Multiplication Avg. Elapsed Time = ", mean(t1_hist) )
println("Sparse Matrix Multiplication Avg. Elapsed Time = ", mean(t2_hist) )
``````

Because your matrices arenâ€™t sparse enough â€” they are actually 25% nonzero. Generic sparse-matrix data structures (as opposed to â€śstructuredâ€ť matrices with a very special nonzero pattern, e.g. upper-triangular matrices) are much less efficient than dense-matrix computations until only a tiny fraction of the matrix is nonzero (often < 1% in real applications).

For example, finite-element methods typically produce huge matrices (millions of rows or more) with < 50 nonzero elements per row, i.e. < 0.005% nonzero. In such cases, sparse-matrix data structures are a huge win.

7 Likes

Thanks for your reply @stevengj . In previous case 50% of the elements were nonzero, which is above the ratio of 25%. I changed the ratio by making n=100 and N=1000, which 9.9% of the elements are non zero. Using the sparse representation gave a way better average timing as

``````Avg. Elapsed Time:
Full Matrix Multiplication   =  0.0397137553
Sparse Matrix Multiplication  =  0.001416305
``````

If I understand your code correctly, only the upper-left `n`Ă—`n` corner is nonzero, so the fraction of nonzero elements is `n^2 / (N+n)^2 == 1 / (1 + N/n)^2`. That means 25% nonzero if `n==N`, and 0.83% nonzero (< 1%) when `n=100` and `N=1000`

Your ratio definition is correct. I used the term â€śnumber of elementsâ€ť incorrectly, just made a proportion of nzero/(nzero+zero).