# What is the runtime complexity of MATLAB operation A*B where A and B are general sparse matrices?

I tried to search the answer and I found that method cs_multiply from this book has been adopted for the purpose of multiplication of two general sparse matrices in MATLAB.

In the book it says that "The time taken by this method (A * B) is O(n + f +|B|), where f is the number of floating-point operations performed (f dominates the run time unless A has one or more columns with no entries, in which case either n or |B| can be greater than f)"

So what does this |B| stand for? What should be the runtime complexity in Big-O notation?

Any help will be appreciated.Thanks in advance

• $|B|$ is likely the number of nonzero entries of $B$. – Christian Clason Dec 9 '12 at 9:51
• What is $n$ in this case? – Mohammad Fawaz Dec 9 '12 at 19:35
• @Fawaz - that would usually denote the number of rows. – Christian Clason Dec 9 '12 at 22:51

## 1 Answer

As a general rule, the by far dominant aspect of multiplying two sparse matrices is not actually any floating point computations, but it is forming and allocating the sparsity pattern of the resulting sparse matrix. If $A,B$ are two sparse matrices, then $AB$ is in general sparse as well, but far less so -- it will have many more entries per row, and there is significant work involved in determining which ones these are and in allocating the resulting memory. This will take far longer than actually multiplying out the respective elements unless $A,B$ were already pretty dense.

A second rule is to not form the product between two sparse matrices unless you can't help it. For example, if $X=AB$ and you later need $X$ to form products of the kind $b=Xa$ where $a,b$ are vectors, then you will almost always be better off by computing $b$ as $b=A(Ba)$, i.e., by using two matrix-vector products rather than one matrix-vector product with the product matrix $X$.