The purpose of this research project is to discover the magical world of the sparse matrix.
Many mathematical ideas can be represented by matrices (the plural of matrix). And, since science is just applied mathematics and engineering is just applied science and economics is just... Well, there are a LOT of matrix-based applications out there. However, it turns out that many of these matrices are not dense — as in they do not have non-zero values in every position. Such matrices are called sparse.
Of course, we don't want to waste our time storing all those zeros in a sparse matrix. It would also cost money to buy more RAM or disk space. So special methods have been developed to store sparse matrix data more compactly if not more simply.
Research 3-5 of these methods of sparse matrix storage — especially Compressed Row Storage (CRS). Describe how each works. Also describe several applications where sparse matrices crop up (make your examples as diverse as possible).
Then the fun can begin. Even though data is stored in such a fashion, our common algorithms still work with normal matrix layout ideals. We either have to convert the algorithm equivalently to a new data usage or translate the new storage back to standard coordinates within the original matrix.
Support code must include an implementation of CRS and of two forms of matrix multiplication by a vector. The first will multiply the CRS matrix by the vector with transformation back to standard coordinates. The second will be an algorithm specially designed for CRS-matrix by vector multiplication. Time these two functions (see the notes elsewhere on the site for more on timing) and make a decision as to which algorithm transformation process should be used.
This assignment is (Level 6). (If you wish to implement any other storage techniques and perform similar algorithm transformation tests with them or if you wish to perform algorithm transformations and tests on other matrix operations, negotiate some extra level amount to be added to this base.)