On the Computational Efficiency of SparseArrays

General Usage Performance
,
1

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) )
2

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
3

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
4

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

5

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