Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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

share|improve this question
3  
$|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
add comment

1 Answer 1

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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