# 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)$$