Sparsity Patterns
Why
Certain sparse matrices are easier to work with, especially those with chordal sparsity patterns.1
Definition
A sparsity pattern $E$ of order $n$ is a set of (unordered) pairs of $V = \set{1, \dots , n}$. A sparsity pattern is chordal if the undirected graph $(V, E)$ is chordal.
A symmetric matrix is said to have a sparsity pattern if its $ij$th entry is zero whenever $\set{i, j}$ is not in the sparsity pattern. The diagonal entries and off-diagonal entries for pairs appearing in the sparsity pattern may or may not be zero.
The graph whose vertices are one through $n$ and whose edge set is the sparsity patter is called the sparsity graph
A sparsity pattern is not a property of a matrix because it is not unique (unless all off-diagonal entries are non-zero). If a matrix has a particular sparsity pattern it has every sparsity pattern which is a superset of it. In other words, every matrix has the sparsity pattern which is the set of all pairs of integers.
Notation
Let $E \subset \Set*{\set{i, j}}{i, j \in \set{1, 2, \dots , n}}$. A symmetric matrix $A \in \mathbfsf{S} ^n$ is said to have sparsity pattern $E$ if $A_{ij} = A_{ji} = 0$ wheneer $i \neq j$ and $\set{i, j} \not\in E$. The graph $G = (V, E)$ where $V = \set{1, 2, \dots , n}$ is the sparsity graph associated with $E$.
We will denote the symmetric matrices of order $n$ with sparsity pattern $E$ by $\mathbfsf{S} ^n_{E}$.
Example
The figure above shows a sparsity graph for
the matrix
\[
A := \bmat{
A_{11} & A_{21} & A_{31} & 0 & A_{51} \\
A_{21} & A_{22} & 0 & A_{42} & 0 \\
A_{31} & 0 & A_{33} & 0 & A_{54} \\
0 & A_{42} & 0 & A_{44} & A_{45} \\
A_{51} & 0 & A_{53} & A_{54} & A_{55} \\
}.
\]
- Future editions will expand. ↩︎