.. _sparse-storage-formats:

Sparse Storage Formats
======================


Compressed Sparse Row (CSR)
---------------------------

There are a variety of matrix storage formats available for representing
the sparse matrix. One of the most popular is the CSR format that is
represented by three arrays: ``row_ptr``, ``col_ind`` and ``val``, and
the index parameter.


.. list-table::
   :header-rows: 1

   * -  CSR Matrix Elements
     -  Description
   * -  ``num_rows``
     -  Number of rows in the sparse matrix.
   * -  ``num_cols``
     -  Number of columns in the sparse matrix.
   * -  ``index``
     -  Parameter that is used to specify whether the matrix has zero or one-based indexing.
   * -  ``val``
     -  An array that contains the non-zero elements of the sparse matrix stored row by row.
   * -  ``col_ind``
     -  An integer array of column indices for non-zero elements stored in the ``val`` array, such that ``col_ind[i]`` is the 
        column number (using zero- or one-based indexing) of the element of the sparse matrix stored in ``val[i]``.
   * -  ``row_ptr``
     -  An integer array of size equal to ``num_rows`` + 1. Element j of this integer array gives the position of the element 
        in the ``val`` array that is first non-zero element in a row ``j`` of ``A``. Note that this position is equal to
        ``row_ptr[j]`` - ``index``. The last element of the ``row_ptr`` array (``row_ptr[num_rows]``) stores the sum of, number 
        of nonzero elements and ``index``\ \*(number of nonzero elements + ``index``\ \*).


Examples of CSR format
++++++++++++++++++++++

A sparse matrix can be represented in a CSR format in the following ways:


Case 1:
~~~~~~~

Assuming zero-based indexing and a real square matrix.


.. math::

   A = \left(
      \begin{array}{ccc}
        1.0 & 0.0  & 2.0 \\
        0.0 & -1.0 & 4.0 \\
        3.0 & 0.0  & 0.0
      \end{array}
   \right)



.. list-table::
   :header-rows: 0

   * -  ``num_rows``
     -  3
     -   
     -   
     -   
     -   
   * -  ``num_cols``
     -  3
     -   
     -   
     -   
     -   
   * -  ``index``
     -  0
     -   
     -   
     -   
     -  
   * -  ``row_ptr``
     -  0
     -  2
     -  4
     -  5
     -   
   * -  ``col_ind``
     -  0
     -  2
     -  1
     -  2
     -  0
   * -  ``val``
     -  1.0
     -  2.0
     -  -1.0
     -  4.0
     -  3.0

Case 2:
~~~~~~~

Assuming one-based indexing and real rectangular matrix with an empty row.

.. math::

   A = \left(
      \begin{array}{ccccc}
        1.0 & 0.0  & 2.0 & 0.0 & 0.0 \\
        0.0 & -1.0 & 4.0 & 0.0 & 1.0 \\
        0.0 & 0.0  & 0.0 & 0.0 & 0.0 \\
        3.0 & 0.0  & 0.0 & 1.0 & 0.0
      \end{array}
   \right)



.. list-table::
   :header-rows: 0

   * -  ``num_rows``
     -  4
     -   
     -   
     -   
     -   
     -   
     -   
   * -  ``num_cols``
     -  5
     -   
     -   
     -   
     -   
     -   
     -   
   * -  ``index``
     -  1
     -   
     -   
     -   
     -   
     -   
     -   
   * -  ``row_ptr``
     -  1
     -  3
     -  6
     -  6
     -  8
     -   
     -
   * -  ``col_ind``
     -  1
     -  3
     -  2
     -  3
     -  5
     -  1
     -  4 
   * -  ``val``
     -  1.0
     -  2.0
     -  -1.0
     -  4.0
     -  1.0
     -  3.0
     -  1.0