5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ $|B|$ is likely the number of nonzero entries of $B$. $\endgroup$
    – Christian Clason
    Commented Dec 9, 2012 at 9:51
  • $\begingroup$ What is $n$ in this case? $\endgroup$
    – Mohammad Fawaz
    Commented Dec 9, 2012 at 19:35
  • $\begingroup$ @Fawaz - that would usually denote the number of rows. $\endgroup$
    – Christian Clason
    Commented Dec 9, 2012 at 22:51

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.