Matrix Designs

17.1. Matrix Designs#

17.1.1. Sparse vs. structured vs. dense matrices#

A sparse matrix is a matrix with enough zeros that it is worth taking advantage of them [Wilkinson]

\[\begin{split} \begin{bmatrix} \bullet & & \bullet & \bullet & \bullet \\ & \bullet & & & \\ \bullet & & \bullet & & \\ \bullet & & & \bullet & \\ \bullet & & & & \bullet \end{bmatrix} \end{split}\]

A structured matrix has enough structure that it is worthwhile to use it (e.g. Toeplitz)

\[\begin{split} \begin{bmatrix} a & b & c & d & e \\ b & a & b & c & d \\ c & b & a & b & c \\ d & c & b & a & b \\ e & d & c & b & a \end{bmatrix} \end{split}\]

A dense matrix is neither sparse nor structured

\[\begin{split} \begin{bmatrix} \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet \\ \end{bmatrix} \end{split}\]

17.1.2. Sparse matrices, design considerations#

Most operations should give the same results for sparse and full matrices
Sparse matrices are never created automatically, but once created they propagate
Performance is important, but also usability, simplicity, completeness, and robustness
Storage for a sparse matrix should be propertional to the number of non-zeros
Time for a sparse operation should be close to the number of floating point operations required

17.1.2.1. Data structures for matrices#

As an example, consider storing the following matrix of size \(m-by-n\) with \(m=n=5\).

\[\begin{split} \begin{bmatrix} 5 & 0 & -3 & -2 & 7 \\ 0 & 5 & 0 & 0 & 0 \\ -2 & 0 & -1 & 0 & 0 \\ -4 & 0 & 0 & -1 0 & 0 \\ 0 & 0 & 0 & 0 & 9 \end{bmatrix} \end{split}\]

17.1.2.2. Full (dense) storage#

Used in the standard Array type
Stores all the matrix entries, including zeros
Memory usage \(\mathcal{O}(m\cdot n)\).

17.1.2.3. List of lists (LIL)#

Only store the non-zero values of the matrix
Store lists for each column, containing the row indices and the values:

  Column 1 -> Rows [1,3,4], Values [5,-2,-4]
  Column 2 -> Rows [2], Values [5]
  Column 3 -> Rows [1,3], Values [-3,-1]
  Column 4 -> Rows [1,4], Values [-2,-10]
  Column 5 -> Rows [1,5], Values [7,9]

This is essentially the adjacency list format for the graph represented by the matrix
Sort row indices for faster searching
Easy to insert new elements (increamental matrix construction)
Also possible to store the transpose (a list per row, with column indices)
Memory usage = \(\mathcal{O}(\mathrm{nnz} + n)\), where \(\mathrm{nnz}\) is the total number of non-zeros in the matrix

17.1.2.4. Coordinate list (COO)#

Store one list with (row, column, value) for each non-zero matrix entry:

  [1,1,5]
  [3,1,-2]
  [4,1,-4]
  [2,2,5]
  [1,3,-3]
  [3,3,-1]
  [1,4,-2]
  [4,4,-10]
  [1,5,7]
  [5,5,9]

Optionally sort by row indices first, then by column indices, for faster searching
Incremental construction possible, but might not preserve sorting
Memory usage = \(\mathrm{O}(\mathrm{nnz})\)

17.1.2.5. Compressed sparse column (CSC)#

Essentially the COO format, but compressing the column indices (that is, not storing them)
Instead, store pointers (or indices) to the first entry in each column

  nzval  = [5,-2,-4,5,-3,-1,-2,-10,7,9]   # Non-zero values
  rowval = [1,3,4,2,1,3,1,4,1,5]          # Row indices for each value
  colptr = [1,4,5,7,9,11]                 # Indices of first entry in each column

The colptr array contains \(n+1\) entries, and has the property that column k is stored between index colptr[k] and colptr[k+1]-1. Note that this allows for empty columns, and that colptr[n+1] equals nnz+1.
Not well-suited for incremental construction (insertion of new non-zeros expensive)
Cost of element look-up = \(\mathcal{O}(\#\text{elements in the column})\)
Efficient for arithmetic operations, column slicing, and matrix-vector products
Memory usage = \(\mathcal{O}(\mathrm{nnz} + n)\)