Sparse Matrix

Computers are only able to manipulate data of type bit. This means that the only understandable information that can be handled by CPU is 0 or 1.

With the improvement of programming languages and the appearance of new generations as the low-level, high-level programming paradigms and the Object oriented; developers needed to design new data types to handle their variables and perform the appropriate operations. String, float, integer, char …etc. are examples of data types and were enough for long time in programming field.

Later more complex structures for specific operations and difficult manipulations have been created as List, Array, Matrix, Stack …etc.
Theses data structures have been built upon the basic data types and provide more flexibility and enhancement in data manipulation.

Although, these new data types have responded to many requirements, they still get improved. For example new kinds of lists have been designed as a double-linked lists.

Focusing on matrix, let’s first provide a brief description of matrix;
Matrix [n,m] is a two dimensional table with n rows and m columns and is widely used in nowadays applications specially in graphic and scientific applications.
The beauty of this complex data structure is the fact that it handle and manipulate data as a two dimensional array and it provides support for related operations. Matrices are implemented as a collection of arrays with the same size. Arrays are considered as ‘Static’ data structure because the size of the array has to be defined at the beginning and this size is fixed during the execution of the program, i.e. this means that if we define for example an array of 10 integers in a program, we are limited with this size and the needed memory to host this array is pre-allocated, even if we do not use the hole 10 cells of the array they occupy the memory. [1]
Counterpart, lists are considered as ‘Dynamic’ because the size of this last can change during the execution; we are able to add dynamically elements to the list or remove if we no longer need them.

Back to the matrices, a specific kind of matrix called Sparse Matrix is a matrix that holds a lot of zeros (or empty cells)[2], the pre-allocation of memory for this type of matrix will end with a lost of memory cells (allocated and useless). In order to optimize the allocation of memory, this technique stores only non-zero values.
Different implementations of Sparse Matrices exist; the LIL (List of List) or COO (Coordinate list) are examples of implementations [3].
In the COO implementation of the Sparse Matrix, a list stores only the non-zero values with their respective row and columns indices in what is called a tuples (data structure with three elements).

As shown in the figure 1, the sparse matrix is implemented as a COO list; this structure is similar to lists in the following properties:
– The way list is browser and accessed.
– The implementation is the exact as a list (with pointers).
– It has a head and a tail.

However, it differs from lists in the following properties:
– The content of each element is a tuple.
– Accessing the content of the list must be in sequential order and not a direct (as in matrix with indices).

References:
[1] J.G Brookshear ‘Computer science 10th Edition’, 2010 P377, ISBN : 978-0-321-52403.

[2] Davis, Tim. “Sparse Matrix.” From MathWorld–A Wolfram Web Resource, created by Eric W. Weisstein.
http://mathworld.wolfram.com/SparseMatrix.html

[3] Wikipedia, ‘Sparse Matrix’, http://en.wikipedia.org/wiki/Sparse_matrix