# Star Bicolouring of Bipartite Graphs
## 2 Sparse Jacobian Determination
#### An Illustrative Example  
To illustrate the main ideas in our graph colouring formulation of the sparse Jacobian matrix determination, we refer to Figure 1, where the matrix shown in (a) has six columns and seven rows. The corresponding bipartite graph associated with its sparsity pattern shown in (b) has \(|L|=6\) vertices for the columns and \(|R|=7\) vertices for the rows.  
Consider the following subsets of rows and columns:  
\[\left(\begin{array}{ccccc}a_{11}&&&&a_{14}&&&&\\ &a_{22}&&&&a_{25}&&\\ &&a_{33}&&&&a_{36}\\ &&&&a_{41}&a_{42}&a_{43}&&\\ a_{51}&&&&a_{55}&a_{56}\\ &&&&a_{62}&&a_{64}&a_{66}\\ &&&&a_{73}&a_{74}&a_{75}&\end{array}\right)\]  
where each subset (of rows/columns) is assigned a different colour, say, colour1, colour2, colour3, colour4, colour0, reading left to right, respectively. It can be verified that this is a valid star bicolouring. Furthermore, colour0 is redundant in that all the nonzero unknowns of the Jacobian are determined from the remaining colour groups. We construct the seed matrices \(S\) and \(W\),  
\[S=\left(\begin{array}{ccccc}1&0&0\\ 0&1&0\\ 0&0&1\\ 1&0&0\\ 0&1&0\\ 0&0&1\end{array}\right)\text{ and }W^{\top}=\left(\begin{array}{ccccc}1&1&1&0&0&0&0 &0\end{array}\right)\]  
from the colouring information, and we compute the respective compressed Jacobian.  
\[B=JS=\left(\begin{array}{ccccc}a_{11}+a_{14}&0&0\\ 0&a_{22}+a_{25}&0\\ 0&0&a_{33}+a_{36}\\ a_{41}&a_{42}&a_{43}\\ a_{51}&a_{55}&a_{56}\\ a_{64}&a_{62}&a_{66}\\ a_{74}&a_{75}&a_{73}\end{array}\right),\ \ \ C=W^{\top}J=\left(\begin{array}{ccccc}a_{11}&a_{22}&a_{33}&a_{14}&a_{25}& a_{36}\end{array}\right)\]  
As commented earlier, we have omitted the colouring information from colour0 in the seed matrix \(W\). It can be directly verified that each nonzero unknown appears unperturbed as an  
Figure 1: (a) An example sparse matrix. (b) Associated bipartite graph.  
entry in one of the two compressed matrices. Hence, the Jacobian is fully determined from the two compressed matrices with a prior knowledge of the sparsity pattern. The example matrix used here was originally proposed by [PERSON] and requires at least six Forward AD Passes in a one-sided compression, since the associated column intersection graph is a complete graph on six vertices [8]. Therefore, the bicolouring method saves two AD Passes.  
For column compression (of \(A\) or \(A^{\top}\)), a satisfactory lower bound on the number of matrix-vector products (or AD passes) is given by \(\max_{i}\rho_{i}\), where \(\rho_{i}\) denotes the number of nonzero entries in row \(i\). An easily computed lower bound on the number of \"positive\" colours has been derived in [16]\(\lceil\frac{\min_{i}}{\max\{m,n\}}\rceil\) by using a consistency argument in solving the system of linear equations defined by the products \(B=JS\) and \(C=W^{\top}J\). [PERSON] and [PERSON] derive the same bound using a graph theoretic argument [5]. The primary motivation for the current work is to derive a formal framework for the lower and upper bounds for the star bicolouring problem. Analogous to the work of [7], our ILP formulation of the star bicolouring does not distinguish between colours to keep the integer linear program simple.