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