Global vs. Local Sparsity

Let's motivate the difference between local and global sparsity patterns by taking a look at the function $f(\mathbf{x}) = x_1x_2$. The corresponding Jacobian is:

\[J_f = \begin{bmatrix} \frac{\partial f}{\partial x_1} & \frac{\partial f}{\partial x_2} \end{bmatrix} = \begin{bmatrix} x_2 & x_1 \end{bmatrix}\]

Depending on the values of $\mathbf{x}$, the resulting local Jacobian sparsity pattern could be either:

• $[1\; 1]$ for $x_1 \neq 0$, $x_2 \neq 0$
• $[1\; 0]$ for $x_1 = 0$, $x_2 \neq 0$
• $[0\; 1]$ for $x_1 \neq 0$, $x_2 = 0$
• $[0\; 0]$ for $x_1 = 0$, $x_2 = 0$

These are computed by TracerLocalSparsityDetector:

julia> using SparseConnectivityTracer
julia> detector = TracerLocalSparsityDetector();
julia> f(x) = x[1]*x[2];
julia> jacobian_sparsity(f, [1, 1], detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 2 stored entries:
 1  1
julia> jacobian_sparsity(f, [0, 1], detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 1 stored entry:
 1  ⋅
julia> jacobian_sparsity(f, [1, 0], detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 1 stored entry:
 ⋅  1
julia> jacobian_sparsity(f, [0, 0], detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 0 stored entries:
 ⋅  ⋅

In contrast to this, TracerSparsityDetector computes a conservative union over all sparsity patterns in $\mathbf{x} \in \mathbb{R}^2$. The resulting global pattern therefore does not depend on the input. All of the following function calls are equivalent:

julia> detector = TracerSparsityDetector()TracerSparsityDetector()
julia> jacobian_sparsity(f, [1, 1], detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 2 stored entries:
 1  1
julia> jacobian_sparsity(f, [0, 1], detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 2 stored entries:
 1  1
julia> jacobian_sparsity(f, [1, 0], detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 2 stored entries:
 1  1
julia> jacobian_sparsity(f, [0, 0], detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 2 stored entries:
 1  1
julia> jacobian_sparsity(f, rand(2), detector)1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 2 stored entries:
 1  1