Ctrl+K

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)\)

Contents