# On the Computational Efficiency of SparseArrays

**URL:** <https://discourse.julialang.org/t/on-the-computational-efficiency-of-sparsearrays/34531>\
**Category:** Performance\
**Tags:** performance, linearalgebra\
**Created:** [February 12, 2020, 6:31pm UTC](https://discourse.julialang.org/t/on-the-computational-efficiency-of-sparsearrays/34531 "2020-02-12T18:31:40Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![asavasci](https://avatars.discourse-cdn.com/v4/letter/a/eb8c5e/32.png) [@asavasci](https://discourse.julialang.org/u/asavasci)\
**Post date:** [February 12, 2020, 6:31pm UTC](https://discourse.julialang.org/t/on-the-computational-efficiency-of-sparsearrays/34531/1 "2020-02-12T18:31:40Z")

</div>

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.

```julia
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) )

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 12, 2020, 6:50pm UTC](https://discourse.julialang.org/t/on-the-computational-efficiency-of-sparsearrays/34531/2 "2020-02-12T18:50:58Z")

</div>

> [@asavasci](#):
>
> I am getting much more averaged computation time by using sparse matrices structure.

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.

---

<div class="post-metadata">

**Author:** ![asavasci](https://avatars.discourse-cdn.com/v4/letter/a/eb8c5e/32.png) [@asavasci](https://discourse.julialang.org/u/asavasci)\
**Post date:** [February 12, 2020, 7:14pm UTC](https://discourse.julialang.org/t/on-the-computational-efficiency-of-sparsearrays/34531/3 "2020-02-12T19:14:22Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 12, 2020, 7:18pm UTC](https://discourse.julialang.org/t/on-the-computational-efficiency-of-sparsearrays/34531/4 "2020-02-12T19:18:07Z")

</div>

> [@asavasci](#):
>
> I changed the ratio by making n=100 and N=1000, which 9.9% of the elements are non zero.

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`

---

<div class="post-metadata">

**Author:** ![asavasci](https://avatars.discourse-cdn.com/v4/letter/a/eb8c5e/32.png) [@asavasci](https://discourse.julialang.org/u/asavasci)\
**Post date:** [February 12, 2020, 7:27pm UTC](https://discourse.julialang.org/t/on-the-computational-efficiency-of-sparsearrays/34531/5 "2020-02-12T19:27:16Z")

</div>

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