[1,] | | . . . . . . . . . . | | [2,] | | . . . . . . . . . . | | [3,] . . | | . . . . . . . . | | [4,] . . | | . . . . . . . . | | [5,] . . . . | | . . . . . . | | [6,] . . . . | | . . . . . . | | [7,] . . . . . . | | . . . . | | [8,] . . . . . . | | . . . . | | [9,] . . . . . . . . | | . . | | [10,] . . . . . . . . | | . . | | [11,] . . . . . . . . . . | | | | [12,] . . . . . . . . . . | | | | [13,] | | | | | | | | | | | | | | [14,] | | | | | | | | | | | | | | Figure 7: Example of sparsity pattern under conditional independence. gin each column. 5 Under the conditional independence assumption, the cross-partial derivatives between heterogeneous parameters across households are all zero. Thus, the Hessian becomes sparser as the size of the dataset increases. To illustrate, suppose we have a hierarchical model with six households, two heterogeneous parameters per household, and two population-level parameters, for a total of 14 parameters. Figure 7 is a schematic of the sparsity structure of the Hessian; the vertical lines are the non-zero elements, and the dots are the zeros. There are 196 elements in this matrix, but only 169 are non- zero, and only 76 values are unique. Although the savings in RAM is modest in this illustration, the efficiencies are much greater when we add more households. If we had 1,000 households, with k = 3 and p = 9, there would be 3009 parameters, and more than nine million elements in the Hessian, yet no more than 63,000 are non-zero, of which about 34,500 are unique. As we add households, the number of non-zero elements of the Hessian grows only linearly in N . The cost of estimating a dense Hessian using AD grows linearly with the number of variables (Griewank et al. 2008). When the Hessian is sparse, with a pattern similar to Figure 7, we can estimate the Hessian so that the cost is only a multiple of the cost of computing the log posterior. We achieve this by using a graph coloring algorithm to partition the variables into a small number of groups (or “colors” in the graph theory literature), such that a small change in the variable in one group does not affect the partial derivative of any other variable in the same group. This means we could perturb all of the variables in the same group at the same time, recompute the gradient, $^{5}$This storage scheme is known as the Compressed Sparse Column (CSC) format. This common format is used by the Matrix package in R , and the Eigen numerical library, but it is not the only way to store a sparse matrix. 22