# Sparse matrix multiplication complexity

**URL:** <https://discourse.julialang.org/t/sparse-matrix-multiplication-complexity/1776>\
**Category:** General Usage\
**Created:** [January 29, 2017, 11:28pm UTC](https://discourse.julialang.org/t/sparse-matrix-multiplication-complexity/1776 "2017-01-29T23:28:05Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![WenlongGong](https://avatars.discourse-cdn.com/v4/letter/w/3d9bf3/32.png) [@WenlongGong](https://discourse.julialang.org/u/WenlongGong)\
**Post date:** [January 29, 2017, 11:28pm UTC](https://discourse.julialang.org/t/sparse-matrix-multiplication-complexity/1776/1 "2017-01-29T23:28:05Z")

</div>

I’m trying to confirm the spmatmul() function in julia, for sparse matrix multiplication, has the same complexity (using big O notation) with Matlab sparse matrix multiplication(by Dr. Tim Davis). For A\*B, A is m by n, B is n by n, according to Davis’s book, it has O(m+n+flops+nnz(B)) complexity with his code. Does Julia’s spmatmul() has the same complexity?

All comments are welcome.

---

<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:** [January 29, 2017, 11:30pm UTC](https://discourse.julialang.org/t/sparse-matrix-multiplication-complexity/1776/2 "2017-01-29T23:30:57Z")

</div>

> [@WenlongGong](#):
>
> I’m trying to confirm the spmatmul() function in julia, for sparse matrix multiplication, has the same complexity (using big O notation) with Matlab sparse matrix multiplication(by Dr. Tim Davis). For A\*B, A is m by n, B is n by n, according to Davis’s book, it has O(m+n+flops+nnz(B)) complexity with his code. Does Julia’s spmatmul() has the same complexity?

It should, especially since Julia uses Tim Davis’ SuiteSparse code.

---

<div class="post-metadata">

**Author:** ![tkelman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkelman/32/692_2.png) [@tkelman](https://discourse.julialang.org/u/tkelman)\
**Post date:** [January 30, 2017, 11:45pm UTC](https://discourse.julialang.org/t/sparse-matrix-multiplication-complexity/1776/3 "2017-01-30T23:45:25Z")

</div>

I don’t think we call into suitesparse for spmm though, IIRC there’s a pure Julia implementation of the Gustavson algorithm. [http://dl.acm.org/citation.cfm?id=355796](http://dl.acm.org/citation.cfm?id=355796)