{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Matrix Designs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sparse vs. structured vs. dense matrices\n",
"\n",
"- A *sparse matrix* is a matrix with enough zeros that it is worth taking advantage of them [Wilkinson]\n",
"\n",
"$$\n",
"\\begin{bmatrix}\n",
"\\bullet & & \\bullet & \\bullet & \\bullet \\\\\n",
" & \\bullet & & & \\\\\n",
" \\bullet & & \\bullet & & \\\\\n",
" \\bullet & & & \\bullet & \\\\\n",
" \\bullet & & & & \\bullet\n",
"\\end{bmatrix}\n",
"$$\n",
"\n",
"- A *structured matrix* has enough structure that it is worthwhile to use it (e.g. Toeplitz)\n",
"\n",
"$$\n",
"\\begin{bmatrix}\n",
"a & b & c & d & e \\\\\n",
"b & a & b & c & d \\\\\n",
"c & b & a & b & c \\\\\n",
"d & c & b & a & b \\\\\n",
"e & d & c & b & a\n",
"\\end{bmatrix}\n",
"$$\n",
"\n",
"- A *dense matrix* is neither sparse nor structured\n",
"\n",
"$$\n",
"\\begin{bmatrix}\n",
"\\bullet & \\bullet & \\bullet & \\bullet & \\bullet \\\\\n",
"\\bullet & \\bullet & \\bullet & \\bullet & \\bullet \\\\\n",
"\\bullet & \\bullet & \\bullet & \\bullet & \\bullet \\\\\n",
"\\bullet & \\bullet & \\bullet & \\bullet & \\bullet \\\\\n",
"\\bullet & \\bullet & \\bullet & \\bullet & \\bullet \\\\\n",
"\\end{bmatrix}\n",
"$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sparse matrices, design considerations\n",
"\n",
"- Most operations should give the same results for sparse and full matrices\n",
"- Sparse matrices are never created automatically, but once created they propagate\n",
"- Performance is important, but also usability, simplicity, completeness, and robustness\n",
"- Storage for a sparse matrix should be propertional to the number of non-zeros\n",
"- Time for a sparse operation should be close to the number of floating point\n",
" operations required"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Data structures for matrices\n",
"\n",
"As an example, consider storing the following matrix of size $m-by-n$ with $m=n=5$.\n",
"\n",
"$$\n",
"\\begin{bmatrix}\n",
"5 & 0 & -3 & -2 & 7 \\\\\n",
"0 & 5 & 0 & 0 & 0 \\\\\n",
" -2 & 0 & -1 & 0 & 0 \\\\\n",
" -4 & 0 & 0 & -1 0 & 0 \\\\\n",
" 0 & 0 & 0 & 0 & 9\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Full (dense) storage\n",
"\n",
"- Used in the standard `Array` type\n",
"- Stores all the matrix entries, including zeros\n",
"- Memory usage $\\mathcal{O}(m\\cdot n)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### List of lists (LIL)\n",
"\n",
"- Only store the non-zero values of the matrix\n",
"\n",
"- Store lists for each column, containing the row indices and the values:\n",
"\n",
"```\n",
" Column 1 -> Rows [1,3,4], Values [5,-2,-4]\n",
" Column 2 -> Rows [2], Values [5]\n",
" Column 3 -> Rows [1,3], Values [-3,-1]\n",
" Column 4 -> Rows [1,4], Values [-2,-10]\n",
" Column 5 -> Rows [1,5], Values [7,9]\n",
"```\n",
"\n",
"- This is essentially the adjacency list format for the graph represented\n",
" by the matrix\n",
" \n",
"- Sort row indices for faster searching\n",
" \n",
"- Easy to insert new elements (*increamental* matrix construction)\n",
"\n",
"- Also possible to store the transpose (a list per row, with column indices)\n",
"\n",
"- Memory usage = $\\mathcal{O}(\\mathrm{nnz} + n)$, where $\\mathrm{nnz}$ is the total\n",
" number of non-zeros in the matrix"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Coordinate list (COO)\n",
"\n",
"- Store one list with (row, column, value) for each non-zero matrix entry:\n",
"\n",
"```\n",
" [1,1,5]\n",
" [3,1,-2]\n",
" [4,1,-4]\n",
" [2,2,5]\n",
" [1,3,-3]\n",
" [3,3,-1]\n",
" [1,4,-2]\n",
" [4,4,-10]\n",
" [1,5,7]\n",
" [5,5,9]\n",
"```\n",
"\n",
"- Optionally sort by row indices first, then by column indices, for faster searching\n",
"\n",
"- Incremental construction possible, but might not preserve sorting\n",
"\n",
"- Memory usage = $\\mathrm{O}(\\mathrm{nnz})$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Compressed sparse column (CSC)\n",
"\n",
"- Essentially the COO format, but *compressing* the column indices (that is, not storing them)\n",
"\n",
"- Instead, store *pointers* (or indices) to the first entry in each column\n",
"\n",
"```\n",
" nzval = [5,-2,-4,5,-3,-1,-2,-10,7,9] # Non-zero values\n",
" rowval = [1,3,4,2,1,3,1,4,1,5] # Row indices for each value\n",
" colptr = [1,4,5,7,9,11] # Indices of first entry in each column\n",
"```\n",
"\n",
"- The `colptr` array contains $n+1$ entries, and has the property that\n",
" column `k` is stored between index `colptr[k]` and `colptr[k+1]-1`. Note that\n",
" this allows for empty columns, and that `colptr[n+1]` equals `nnz+1`.\n",
" \n",
"- Not well-suited for incremental construction (insertion of new non-zeros expensive)\n",
"\n",
"- Cost of element look-up = $\\mathcal{O}(\\#\\text{elements in the column})$\n",
"\n",
"- Efficient for arithmetic operations, column slicing, and matrix-vector products\n",
"\n",
"- Memory usage = $\\mathcal{O}(\\mathrm{nnz} + n)$"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Julia 1.9.2",
"language": "julia",
"name": "julia-1.9"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.9.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}