I am reading a paper on sparse matrices and there is an algorithm for sparse lower triangular systems. In the below pseudo-code $l$ is a sparse matrix and $x,b$ are sparse vectors.

for j=0 to n-1 do
    if x[j] != 0
        for i=j+1 to n-1 do
            if l[i][j] != 0
                ~5 operations.

The paper claims that this algorithm is $\mathcal{O}(n+|b|+f)$, where $|b|$ is the number of non-zero entries in $b$ and $f$ is the number of floating point operations carried out.

I do not understand why this algorithm is not $\mathcal{O}(n|b|f)$.

Reference: Chapter 3 - Section 2 of https://epubs.siam.org/doi/book/10.1137/1.9780898718881

Some context on sparse matrices: Sparse matrices usually appear when solving problems using numerical schemes such as the finite element method. These matrices usually have a very small number of non-zero entries per row. For instance, a $n$-by-$n$ matrix might only have $\mathcal{O}(1)$ entries per row. The situation might not be as good as this in the algorithm above (there is no mention of a definition of sparse matrices in the book, as far as I can see.)

  • $\begingroup$ Since the content is not freely available (one has to pay for it), is there any relevant context from the book you can provide us? It might be hard to answer this question without reading that chapter of the book. It's possible it is just a typo or an error; that happens. $\endgroup$ – D.W. Jul 6 '18 at 14:53
  • 1
    $\begingroup$ What is $l$? What is $b$? $\endgroup$ – orlp Jul 6 '18 at 15:13
  • $\begingroup$ I don't think it is a typo: The paragraph in which the statement arises refers the result two further times and a following paragraph once again. What other context would be needed? I am sorry if that comes across a bit obtuse, but I am not a computer scientist. $\endgroup$ – user88950 Jul 6 '18 at 16:11
  • $\begingroup$ @orlp I have update the post. $\endgroup$ – user88950 Jul 6 '18 at 16:12

They say the running time is $O(n+|b|+f)$, where $f$ is the number of floating point operations taken during the entire computation. This takes some careful reading to understand what they mean.

They mean, if you take the total number of floating-point operations that are performed inside the innermost loop, and call that $f$, then the running time is not too much more than $f$. In other words, they are saying we do $O(n+|b|)$ operations for updating the loop indices, plus the time taken by the body of the innermost loop (summed over all the iterations).

The body of the innermost loop might indeed take $5 n|b|$ operations in total (say), in which case the total running time would be $O(n + |b| + 5n|b|) = O(n|b|)$, as you had expected.

Note that $f$ is not the number of floating point operations in a single iteration of the innermost loop; it is the total across all iterations of the loop. So $f$ is not 5.

Why do they count it this way? Presumably, the floating point operations are ones that we'll have to do no matter what, because they are essential to the operation you're doing; they instead want to focus on the extra book-keeping needed to update loop indices etc. and make sure that doesn't add too much extra cost.

Finally, I'll note that you changed the pseudocode. The pseudocode they show is not the same as what you listed in the question. In the book the pseudocode of the innermost loop is not "for $i=j+1$ to...", but rather "for each $i>j$ for which $l_{ij}$". That's not the same. Since $l$ is a sparse matrix/vector, there are more efficient ways to iterate over the non-zero entries of $l$ than iterating over all possible values of $j$ and testing whether that element is non-zero. This also affects the running time.

  • $\begingroup$ Ahh yes I did change the pseudo-code. It was some odd way to get my head around what was going on. I have never seen this business of lumping all floating point operations together before. Thanks for your detailed response. $\endgroup$ – user88950 Jul 6 '18 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy