Exercises

1. Another important optimization that can be used to improve algorithm 4.3 is to skip over rows or columns that are entirely zero.

   For example, in the current algorithm, even if a row is completely zero, the inner two loops are run over it anyway, even though no non-zero values can possibly result- work that accomplishes nothing. In the very worst case, multiplying two sparse matrices that are both entirely zero will require operations (or , if the solution to the previous problem is used).

   Improve the algorithm so that it handles rows or columns that are entirely zero in a more efficient manner. Discuss any tradeoffs that you make between efficiency and simplicity.

2. Extend the ideas in section 4.4.3 to work when B is a sparse array with common value (where ).